c++实现栈的出栈验证思路总结

Leetcode946题是一道关于栈的出栈顺序验证的一道题，问题叙述如下：

问题描述：给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

示例1：输入pushed = [1,2,3,4,5],poped = [1,2,3,4,5],输出true

示例分析：我们对栈进行如下操作：push(1),pop(1),push(2),pop(2),push(3),pop(3),push(4),pop(4),push(5),pop(5),最后栈是一个空栈。

示例2：输入pushed = [1,2,3,4,5],poped = [4,3,5,1,2],输出false

示例分析：我们对栈进行如下操作：push(1),push(2),push(3),push(4),pop(4),pop(3),push(5),pop(5),到这一步出现错误，因为1不可能在2之前出栈。

问题分析：对于栈的出栈验证问题，常采用的一种方法是辅助栈法，即采用一个栈来模拟压栈和出栈。这个方法的具体思路是这样的：(1)检查辅助栈栈顶元素与poped组当前元素是否相等，若相等，栈顶元素出栈，与poped组的下一个元素重新进行步骤（1），若不相等，进行步骤(2);(2)压push组元素入栈，转入步骤(1);最后检查辅助栈是否是空栈，若是空栈，说明是一个正确的出栈顺序，否则是错误的。

以输入pushed[1,2,3,4,5],poped[4,5,3,2,1]为例，一开始辅助栈为空栈，与poped组的第一个元素4不相等，所以在栈中压入1，2，3，4，这时4出栈，用来比较的poped组元素变为5；这时栈顶元素3与5不相等，所以压5入栈，然后5出栈，后面以此类推3，2，1出栈，最后辅助栈变为了一个空栈，说明这个出栈顺序是正确的。

代码实现如下：

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.empty() && popped.empty())
            return true;//若均为空操作，返回true
        stack<int> s;
        s.push(-1);//预先压入一个负数
        size_t j = 0;
        for(size_t i = 0;i < popped.size();++i)
        {
            while(s.top() != popped[i])
            {
                if(j >= pushed.size()) //若j>=pushed.size()继续压入
                    break;
                else
                    s.push(pushed[j++]);
            }
            if(s.top() == popped[i])//这个判断是为了防止s的不正确弹出
                s.pop();
        }
        if(s.top() == -1 )//若栈顶元素为-1，说明是空栈，因为poped和pushed的元素都是非负的
            return true;
        else
            return false;      
    }
};

这道题还可以增加一点难度，那就是限定栈的大小为M，然后向栈中压入N个数字，数字大小为1，2，3，...N，然后随机出栈，然后判定一个出栈顺序是否合理。如顺序1，2，3，4，5，6，7是合理的，我们每次压入一个元素然后立即弹出，可以得到这个序列。而序列3，2，1，7，5，6，4是不合理的，因为5不可以比6先出栈。

现在有K组数据，判定每组数据是否合理，若合理，输出"YES",否则输出"NO";

思路分析：核心思路是与上题一样的，同样是要使用一个辅助栈，只是我们在给栈添加元素结束后要检查是否爆栈。代码如下：

#include<iostream>
#include<vector>
#include<stack>

using namespace std;

int main()
{
    size_t m,n,k,count = 0;
    vector<int>vec;
    stack<int> s;
    cin >> m >> n >> k;//输入栈的容量，要要入栈的数目，数据组数
    for(size_t i = 0; i < k; ++i)
    {
        vec.resize(0);
        s.push(0);
        count = 1;
        for(size_t j = 0; j < n; ++j)
        {
            int num;
            cin >> num;
            vec.push_back(num);
        }
        for(size_t j = 0;j < n; ++j)
        {
            while(s.top() != vec[j] && count <= n)
                s.push(count++);
            if(count > n + 1 || s.size() - 1 > m)//检查爆栈
                break;
            if(s.top() == vec[j])
                s.pop();
        }
        s.top() == 0 ? cout << "YES" << endl : cout << "NO" << endl;
        while(!s.empty())
            s.pop();    //判定结束后清空辅助栈，进行下一轮检查
    }
}