输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
方法一：迭代入栈序列，循环中，每次入栈一个元素，再内嵌一个循环，如果入栈元素与弹出序列的第一个元素相同，则将入栈元素出栈，同时弹出序列减少一个元素，直至栈为空或者栈顶元素与弹出序列首元素不相等，当全部元素入栈后，等循环结束时判断栈是否为空，且弹出序列是否为空
方法二：迭代弹出序列，针对每个弹出序列元素，如果栈为空，或者栈顶元素不等于弹出序列首元素，从入栈序列入栈元素，如果栈顶元素等于出栈序列首元素，则出栈，同时出栈序列首元素为下一个，当入栈序列为空时，即所有元素都入栈了，判断弹出序列是否全部弹出。
class Solution { public: //方法一 bool IsPopOrder(vector<int> pushV,vector<int> popV) { vector<int> stack; for(int i = 0, j = 0; i < pushV.size(); i++){ stack.push_back(pushV[i]); while(j < popV.size() && stack.back() == popV[j]){ stack.pop_back(); j++; //讨论中没有这行代码，但我觉得没有这行代码的话，当pushV和popV都是1、2、3、4、5时会出错 //当1入栈后，while的第一次循环会把1出栈，while的第二次条件判断时j < popV.size()满足 //但此时栈以经是空的，stack.back()会出错！！！添加下面的条件判断，当stack为空时，退出 //while循环，不继续判断是否满足出栈的条件 if(stack.size() == 0) break; } } //&& j == popV.size() 是为了处理pushV:1、2、3 popV:1、2、3、4这种情况，入栈元素要和出栈元素 //数量相同且相等，也可以在程序开头判断两个序列长度是否相等 return stack.empty() && j == popV.size(); } //方法二：与一类似，使用辅助栈 bool IsPopOrder(vector<int> pushV,vector<int> popV) { vector<int> stack; //判断两个序列长度是否相等 if(pushV.size() != popV.size()) return false; for(int i = 0, j = 0; i < popV.size();){ if(j == pushV.size()) return false; //stack为空，或者stack的栈顶元素不等于popV[i]，同时必须满足j < pushV.size()，则元素入栈 //stack的栈顶元素不为空，且栈顶元素等于popV[i]时退出while循环 while(stack.empty() || stack[stack.size() - 1] != popV[i]){ if(j == pushV.size()) break; stack.push_back(pushV[j]); j++; } //不用判断i < popV.size()，因为当i = popV.size()时，stack已经为空 while(!stack.empty() && popV[i] == stack[stack.size() - 1]){ stack.pop_back(); i++; } } //for循环正常结束，即i = popV.size()，说明入栈序列中的元素都已按照入栈序列入栈，并且按照弹出序列出栈 return true; } //方法三：参考《剑指offer》，与方法二思路一样 bool IsPopOrder(vector<int> pushV,vector<int> popV) { bool bPossible = false; if(pushV.size() != 0 && popV.size() != 0 && pushV.size() == popV.size()){ std::stack<int> stackData; int i = 0, j = 0; for(; i < popV.size();){ while(stackData.empty() || stackData.top() != popV[i]){ if(j == pushV.size()) break; stackData.push(pushV[j]); j++; } //这里i满足i < popV.size()，说明popV中还有元素，说明stack或者pushV中也还有元素 //所以不会出现stack为空，且pushV中也没有元素的情况，上述while循环退出后，stack中 //一定有元素，可能是stackData.top() == popV[i]导致退出 //也可能是stackData.top() != popV[i] 且 j == pushV.size()导致退出 if(stackData.top() != popV[i]) break; stackData.pop(); i++; } //for循环退出也分两种情况，break退出，循环条件不满足退出 if(i == popV.size()) bPossible = true; } return bPossible; } };
