剑指offer之面试题22栈的压入、弹出序列

一时失言乱红尘 2022-08-22 03:49 16阅读 0赞

**问题描述**：

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

例如：

序列1，2，3，4，5是某栈的压栈顺序，序列4，5，3，2，1是该压栈序列的一个弹出序列，但是4，3，5，1，2就不是该压栈序列的弹出序列。

**实现代码**如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include<math.h>
    int N;
    struct StackIn{
    	int array[100];
    	int top;
    };
    typedef struct StackIn StackIn;
    
    void initStackIn(StackIn *S){
    	S->top=0;
    	S->array[0]=100;
    }
    void pushIn(StackIn *S,int value){
    	S->array[(S->top)++]=value;
    }
    int popIn(StackIn *S){
    	return S->array[--(S->top)];
    }
    
    int getIn(StackIn *S){
    	int i =S->top-1;
    	return S->array[i];
    }
    
    bool doJudge(StackIn *S,int *pushOrder,int *popOrder){
    	int i,j=0;
    	if(S==NULL || pushOrder==NULL || popOrder==NULL){
    		return false;
    	}
    	for(i=0;i<N;i++){
    		pushIn(S,pushOrder[i]);
    		while(getIn(S)==popOrder[j] && j<N){
    			popIn(S);
    			j++;
    		}
    	}
    	if(j!=N){
    		return false;
    	}
    	return true;
    }
    
    
    int main(int argc, char *argv[])
    {
    	int pushOrder[]={
    		1,2,3,4,5
    	};
    	int popOrder[]={
    		4,3,5,1,2
    	};
    	N=sizeof(pushOrder)/sizeof(int);
    	StackIn *S=malloc(sizeof(StackIn));;
    	initStackIn(S);
    	bool b = doJudge(S,pushOrder,popOrder);
    	printf(b==true?"true":"false");
    	return 0;
    }

**参考资料**：  
剑指offer  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51372357  
作者：WSYW126