面试题 22

1 题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

2 解法描述

如果下一个弹出的数字刚好是栈顶数字，那么直接弹出。如果下一个弹出的数字不在栈顶，把压栈序列中还没有入栈的数字压入辅助栈，直到拔下一个需要弹出的数字压入栈顶为止，如果所有的数字都压入了栈，仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列

3 C 语言实现

#include<stdio.h>
typedef int ElemType;
typedef struct node{
    ElemType data;
    struct node *next;
}SNode,*Stack;
//初始化头结点
void initStack(Stack* stack){
    (*stack)=(SNode*)malloc(sizeof(SNode));
    (*stack)->data=0;
    (*stack)->next=NULL;
}
//所有操作都在表头进行,头插法
int push(Stack stack,ElemType data){
    SNode *push;
    //如果Stack尚未初始化
    if(stack==NULL) return 0;
    push=(SNode*)malloc(sizeof(SNode));
    push->data=data;
    push->next=stack->next;
    stack->next=push;
}
//出栈
int pop(Stack stack,ElemType* popVlaue){
    //如果Stack为空
    if(isEmpty(stack)) return 0;
    SNode *pop=stack->next;
    *popVlaue=pop->data;
    stack->next=pop->next;
    free(pop);
    return 1;
}
//获得栈顶元素
int getTop(Stack stack,ElemType* topVlaue){
    //如果Stack为空
    if(isEmpty(stack)) return 0;
    *topVlaue=stack->next->data;
    return 1;
}
//判断是否为空
int isEmpty(Stack stack){
    return stack!=NULL&&stack->next==NULL?1:0;
}

int isPopOrder(int *pushOrder,int *popOrder,int length){
    int* popend=popOrder;
    int* pushend=pushOrder;
    int data;
    Stack stack=NULL;
    initStack(&stack);
     if(pushOrder==NULL||popOrder==NULL||length<=0) return 0;
    //直到所有的代建序列都完成出栈
    while(popend-popOrder<length){
        //如果栈为空，那么持续入栈，直到入栈数字与待检序列当前数字一致，或者压栈序列全部入栈。
        if(isEmpty(stack)){
            while((*pushend)!=(*popend)&&pushend-pushOrder<length){
                push(stack,*pushend);
                pushend=pushend+1;
            }
            if(pushend-pushOrder<length){
            push(stack,*pushend);
            pushend=pushend+1;
        }
        }else{
            getTop(stack,&data);
            while(data!=(*popend)&&pushend-pushOrder<length){
                push(stack,*pushend);
                printf("noempty:push=%d\n",*pushend);
                pushend=pushend+1;
                getTop(stack,&data);
            }
        }
        getTop(stack,&data);
        if(data!=(*popend)){
            break;
        }else{
            pop(stack,&data);
            popend=popend+1;
        }
    }
    if(isEmpty(stack)&&pushend-pushOrder==length){
        return 1;
    }
    return 0;
}
void main(){
    int pushOrder[]={1,2,3,4,5};
    int popOrder[]={4,5,3,2,1};
    printf("%d",isPopOrder(pushOrder,popOrder,5));
}