栈的压入、弹出序列
题目描述：
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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) {
// 设置一个辅助栈，以及一个辅助变量来记录此时需要得到的栈顶弹出值
stack<int> stackData;
int data;
//
if (pushV.empty() || popV.empty()) {
return false;
}
if (pushV.size() != popV.size()) {
return false;
}
stackData.push(pushV[0]);
int j = 1;
for (int i = 0; i < popV.size(); ++i) {
// 取弹出序列最前面的值
data = popV[i];
// 如果弹出序列的值等于此时栈顶的值，则弹出栈顶值
// 并进入下一次的for循环，开始下一次的检视
if (data == stackData.top()) {
stackData.pop();
}
// 如果栈顶的数值与弹出的序列不相等
// 则将此数值压入辅助栈中，并检视之后的待入栈值
else {
// 直到找到入栈序列中可以被弹出的那个值
while (j < pushV.size() && pushV[j] != data) {
stackData.push(pushV[j]);
++j;
}
// 退出while循环之后有两种可能
// 1.j已经遍历完了入栈序列的所有值
if (j >= pushV.size()) {
return false;
}
// 2.找到了与待弹出元素相等的数值
// 将此数值压入辅助栈，接着马上弹出辅助栈（相当于没有做任何操作）
else if (pushV[j] == data) {
++j;
}
}
}
// 如果顺利进行完了上述的过程而且没有返回false
// 则说明匹配成果
return true;
}
};
2018.10.11
