PAT A1051：Pop Sequence（模拟堆栈）

良心！认真记录模拟堆栈操作的思考过程

本文作者：MowChan · 发布日期：2021/01/15 · 阅读时长：5 分钟

题目内容

Given a stack which can keep $M$ numbers at most. Push $N$ numbers in the order of 1, 2, 3, …, $N$ and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if $M$ is 5 and $N$ is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): $M$ (the maximum capacity of the stack), $N$ (the length of push sequence), and $K$ (the number of pop sequences to be checked). Then $K$ lines follow, each contains a pop sequence of $N$ numbers. All the numbers in a line are separated by a space.

Output Specification:

For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.

Sample Input:

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

Sample Output:

YES
NO
NO
YES
NO

题目要点

本题 25 分，模拟堆栈入栈出栈过程，难度较大，考虑的细节问题比较多，核心问题是抓住哪组数据在进行比较，入栈队列、待判断的出栈队列和空堆栈之间是什么关系。

首先，新建一个空的堆栈，模拟整个入栈出栈的过程。入栈顺序与数据由入栈队列一步一步无脑给出，因此外层一个大的循环。

堆栈要与待判断的出栈队列相比较。自然，直接看堆栈看到的是入栈的顺序，题目是对比的出栈顺序，因此必然要用到pop()，出栈队列依次与弹出的元素相比较，完全符合且当入栈的大循环结束后堆栈为空，那么打印YES。然而使用pop()来比较有诸多不便，大部分堆栈的pop()方法是不返回值，那么应该使用top()方法取得栈顶元素，如果栈顶元素满足上述要求，那么执行pop()。

弹出元素后要以出栈队列的下一个元素为基准，继续判断。因此出栈队列元素需要有一个指针来标注当前的基准元素，最初指针为0，在pop()后指针+1。弹出元素后指针和栈顶元素都不同了，那么就存在这时的栈顶元素可能会满足更新后的基准元素，那么应该继续弹出，指针继续+1，直到二者不相等。那么这样的过程就可以用while语句描述，构成内部的一个循环。

需要指出的是，涉及到堆栈时，一定要考虑两个边界问题。第一，栈是否为空，若为空，那么无法执行pop()/top()指令；第二，栈是否有容量，容量为多大，若当前的size()超过了栈的容量，那么无法执行push()指令。

有了这两个边界问题，再来看上面的分析过程。

  • while循环中涉及到pop()，那么就要有个判空的条件，只要堆栈不空，那么循环可以继续，否则，循环终止。
  • 大循环中将遍历的入栈元素push()，那么压栈后若堆栈size()大于容量，就说明无法模拟待判断的出栈顺序，直接返回非。

在大循环结束后，也就是元素全部入栈后，要对堆栈判空。如果堆栈是空的，说明入栈的所有元素已经按照待判断的出栈顺序依次pop()，可以打印YES，否则，说明堆栈现有的元素顺序无法满足，因此堆在堆栈里弹不出去，打印NO。另外一个角度，判断出栈队列的指针也是等价的。如果出栈队列的指针越界，那么说明待比较的元素都已经找到满足要求的入栈元素，此时堆栈为空。

AC 源代码

class Stack(object):
    def __init__(self):
        self.stack = []
    def push(self, data):
        self.stack.append(data)
    def pop(self):
        return self.stack.pop()
    def top(self):
        return self.stack[-1]
    def size(self):
        return len(self.stack)
    def empty(self):
        return not bool(self.stack)

def judge(cap, std, ins):
    ptr = 0
    for e in std:
        s.push(e)
        if s.size() > cap: 
            return False
        while (not s.empty()) and (s.top() == ins[ptr]):
            p = s.pop()
            ptr += 1
    if s.empty():
        return True
    else:
        return False

m, n, count = map(int, input().split())
std = [i+1 for i in range(n)]

for _ in range(count):
    s = Stack()
    ins = list(map(int, input().split()))
    if judge(m, std, ins):
        print('YES')
    else:
        print('NO')

参考来源

https://blog.csdn.net/Wonz5130/article/details/79894496

https://blog.csdn.net/lianwaiyuwusheng/article/details/83543999

https://www.liuchuo.net/archives/2232

← 上一篇 下一篇 →