[PAT] 1051. Pop Sequence (25)

题目链接

分析

对于每一行的出栈序列pos 1 --> n,首先设置一个变量push,用来记录压入栈的值

  • 如果当前栈顶元素小于读入的元素值,在栈中元素个数小于等于指定值的时候压栈;如果栈中元素大于指定值,那么错误,输出NO;
  • 如果当前栈顶元素等于读入的值,那么pop(), 并且break以读入下一个元素;

代码样例

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    int m, n, k;
    cin >> m >> n >> k;

    for (int ii = 0; ii < k; ii++)//process each line 0 --> k-1
    {
        stack<int> s;
        int push = 1,input;
        bool overflow = false;
        for (int jj = 0; jj < n; jj++)
        {
            cin >> input;
            while (s.size() <= m && !overflow)//stack not exceeded the max size, and currently no statk overflow
            {
                if (s.size() == 0 || s.top() != input)
                    s.push(push++);
                else if (s.top() == input)
                {
                    s.pop();
                    break;
                }
            }
            if (s.size() > m) //mark stack overflow as true
            {
                overflow = true;
            }
        }
        if (!overflow)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}