[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;
}
  • 阿莱 2013-10-31 18:04:26

    评论测试!

  • 阿莱 2013-10-31 18:04:34

    评论测试!

  • 阿莱 2013-10-31 18:06:37

    nice to meet you!

  • 阿莱 2014-01-30 22:43:36

    这次发一个长一点的评论,要多长就有多长
    ,长的不得了
    嘿嘿