判断:
如果下一个弹出的数字刚好是栈顶元素,那么直接弹出
如果下一个弹出的数字不在栈顶,我们要把压栈序列中,还没有入栈的数字压入辅助栈,知道把下一个需要弹出的数字压入栈顶
如果所有的数字都入栈,但是仍然没有找到下一个弹出的数字,那么该序列不可能为弹出序列。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | class Solution { public : bool IsPopOrder(vector< int > pushV,vector< int > popV) { int pushi=0; int popi=0; int pushSize=pushV.size(); int popSize=popV.size(); if (popSize!=pushSize) return false ; stack< int > mystack; while (pushi<pushSize) { mystack.push(pushV[pushi++]); while (popi<popSize&&mystack.top()==popV[popi]) { mystack.pop(); popi++; } } if (popi==pushi) return true ; else return false ; } }; |