面试题之判断栈的入栈和出栈序列的合法性

完整题目是这样的：给我们两个序列，第一个序列表示栈的压入顺序，然后让判断第二个序列是不是是否是该栈的弹出序列。现设第一个序列为[1,2,3,4,5],第二个序列为[3,2,5,4,1],可以看出这个出栈顺序是合法的，那么我们怎么通过程序来验证呢？既然是判断栈的出栈顺序，那么我们肯定得有一个辅助栈，来帮助我们做这样的题。我们把第一个序列中的数字一次压入栈中，压入的过程中按照第二个序列的顺序依次从栈中弹出数字。我采用的是用vector来存放两个序列，判断当栈为空或者栈顶元素和V2[i]不相等，就继续压栈。第一次1压入栈，一直满足上面说的压栈条件，所以压入了1,2,3，此时栈顶的3和V2第一个元素相等，则进行出栈操作，i++即下次比较V2的下一个元素。这个循环的操作，重要的是判断结束的条件。下面是代码： 1 #include<stack> 2 bool CheckOutStackOrder（const vector<int>& v1, const vector<int>& v2） 3 { 4 if （v1.size（）！= v2.size（）） 5 return false; 6 stack<int> s; 7 size_t idex1 = 0, idex2 = 0; 8 while （idex2 < v2.size（）） 9 {10 while （s.empty（） || s.top（）！=v2[idex2]）11 {12 if （idex1 < v1.size（））13 {14 s.push（v1[idex1++]）;15 }16 else17 return false;18 }19 idex2++;20 s.pop（）;21 }22 return true;23 }24 void funtest（）25 {26 vector<int> v1;27 vector<int> v2;28 v1.push_back（1）;29 v1.push_back（2）;30 v1.push_back（3）;31 v1.push_back（4）;32 v1.push_back（5）;33 34 v2.push_back（3）;35 v2.push_back（2）;36 v2.push_back（5）;37 v2.push_back（4）;38 v2.push_back（1）;39 bool a = CheckOutStackOrder（v1, v2）;40 }本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-08/134743.htm