首页 > 代码库 > 21、剑指offer--栈的压入、弹出序列

21、剑指offer--栈的压入、弹出序列

题目描述
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)
 
解题思路:首先该题采用辅助栈来实现,j记录弹出元素处理到的位置
1)将待压入栈中的数据,先压入辅助栈
2)然后循环判断判断辅助栈栈顶是否等于待弹出栈的相应元素,相等,就弹出,并且j++,若不等进行下一数据的压入,直至无数据压入
3)全部处理完j=popV.size()此时break循环,并将返回结果置为真
 1 class Solution {
 2 public:
 3     //借助辅助栈实现
 4     bool IsPopOrder(vector<int> pushV,vector<int> popV) {
 5         bool result = false;
 6         int length1 = pushV.size();
 7         int length2 = popV.size();
 8         if(!pushV.empty() && !popV.empty() && length1 == length2)
 9         {
10             stack<int> tmp;
11             int j = 0;
12             for(int i=0;i<length1;i++)
13             {
14                 tmp.push(pushV[i]);
15                 while((!tmp.empty())&&(tmp.top() == popV[j]))
16                 {
17                     tmp.pop();
18                     j++;
19                     if(j == length2)
20                     {
21                         result = true;
22                         break;
23                     }
24                 }
25             }
26 
27         }
28         return result;
29     }
30 };

 

21、剑指offer--栈的压入、弹出序列