【100题】第二十九 栈的push、pop序列

一，题目：输入两个整数序列。其中一个序列表示栈的push顺序，判断另一个序列有没有可能是对应的pop顺序。

如果我们希望pop的数字正好是栈顶数字，直接pop出栈即可；
如果希望pop的数字目前不在栈顶，我们就到push序列中还没有被push到栈里的数字中去搜索这个数字，并把在它之前的所有数字都push进栈。
如果所有的数字都被push进栈仍然没有找到这个数字，表明该序列不可能是一个pop序列。

其实这是一个计算机考研时经常遇到的一道选择题，题目给定一个压栈序列，然后找出选项中哪一个一定不是可能的出栈序列。
二，分析

例如输入顺序为1 2 3 4 5不可能输出顺序为： <1 4 23 5> <4 2 3 5 1 > <1 5 2 3 4 > <3 4 1 2 5>……

可能输出顺序为： <1 2 3 4 5 ><5 4 3 2 1 ><2 1 3 4 5> <3 2 1 5 4 >……

如何判定输出顺序<1 4 2 3 5 >为不可能顺序?

新建一个栈m_stack push[]={1 2 3 4 5} pop[]={1 4 2 3 5}

第一轮 m_stack.push(push[0]); pop[0]=m_stack.top--->m_stack.pop;

第二轮 m_stack.push(push[1]); pop[1]!=m_stack.top--->m_stack.push[2] m_stack.push[3] ----pop[1]=m_stack.top--->m_stack.pop

第三轮 m_stack.push[4]; pop[2]!=m_stack.top ---->push 中没有全部pop出来 所以不是正确的输出序列

三，源码

#include<iostream> 
#include<stack> 
const int SIZE=5; //定义长度  
using namespace std; 
bool judge(int Spush[],int Spop[])
{    
  stack<int> my_stack;    
  int iPush=0,iPop=0;
  while(iPush<SIZE)
  {              
        
    cout<<"push "<<Spush[iPush]<<endl; //当栈顶和pop相等时，将pop后的栈顶与pop之后的元素相比，直到不等       
     my_stack.push(Spush[iPush]);     //测试  
     while(!my_stack.empty()&&iPop!=5&&my_stack.top()==Spop[iPop]) //小心数组越界 
	 {       
         cout<<"pop "<<Spop[iPop]<<endl;               
 	     iPop++;       
         my_stack.pop();    
     }        
     iPush++;  
   }  
 	if(iPop==SIZE) 
		return true;  
 	else 
	 	return false;
 } 
int main(void)
{ 
 	int Spush[SIZE]={1,2,3,4,5};
    int Spop[SIZE]={1,2,3,4,5};
 	if(judge(Spush,Spop))
 		cout<<"Yes"<<endl;  
 	else cout<<"No"<<endl; 
 	
 	system("pause");   
 	return 0; 
 }