这个题目，其实考的是栈的本质问题，也就是它的压入和弹出的顺序。首先我们分析题目
中所给的那几个例子，也就是数据的压入顺序是1、2、3、4、5。但是弹出的顺序是4、5、
3、2、1。这个好办啦，猜都能猜到它是如何操作的。
我们直观上看是这样，但是实际上，给你一个压入数组，一个弹出的数组，如何去判断它
的正确性呢？
其实我们可以根据这两个数组进行分析：
从上面可以看到，首先弹出的是4，因此栈顶肯定是4啦，但是此时栈里只有4吗？
肯定不是，因为先入先出嘛，看第一个数组，先压入了1、2、3.再压入了4，下
面的数组则先弹出了4.，而且第二个数组中，3、2、1在4后面。因此，此时栈里至少
有1、2、3.但是5呢？
第一个数组中，5在四后面才压入，因此里面肯定没有5.但是第二个数组中，5在4后面弹出
则知，5压入后就弹出了。
#ifndef STACK_PUSH_POP_SEQ_H#define STACK_PUSH_POP_SEQ_H#include<iostream>#include<stack>bool stackPPseq(const int *pPussh,const int *pPop,int nLength){ int pushIndex=0; int popIndex=0; std::stack<int> m_stack; if(pPussh==NULL||pPop==NULL||nLength==0){ return false; } while(pushIndex<nLength&&popIndex<nLength){ if(m_stack.empty()){ //如果栈为空，则一直从题目给的压栈顺序数组中提取元素压入栈中，直到碰到一个与弹出数组相等的元素。 while(pPussh[pushIndex]!=pPop[popIndex]){ m_stack.push(pPussh[pushIndex]); ++pushIndex; } m_stack.push(pPussh[pushIndex]); } if(m_stack.top()==pPop[popIndex]){ //如果弹出栈的数组元素与栈顶的元素相等，则一直弹。 while(m_stack.top()==pPop[popIndex]){ m_stack.pop(); popIndex++; if(popIndex==nLength){ return true; } } } if(m_stack.top()!=pPop[popIndex]){//如果栈顶没有与弹出数组元素相等的，则再压。 while(m_stack.top()!=pPop[popIndex]){ pushIndex++; if(pushIndex==nLength){ break; } m_stack.push(pPussh[pushIndex]); } } } if(pPop[popIndex]==m_stack.top()){ m_stack.pop(); popIndex++; if(popIndex>=nLength){ return true; } } return false; }#endif
来自为知笔记(Wiz)
转载于:https://www.cnblogs.com/yml435/p/4655486.html
