题目内容

Given a stack which can keep  numbers at most. Push   numbers in the order of 1, 2, 3, ...,  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  is 5 and  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) : (the maximum capacity of the stack), (the length of push sequence), and (the number of pop sequences to be checked). Then lines follow, each contains a pop sequence ofnumbers. All the numbers in a line are separated by a space.

Output Specification:

For each pop sequence, print in one line "YES&#​34; if it is indeed a possible pop sequence of the stack, or "NO&#​34; 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 分，模拟堆栈入栈出栈过程，难度较大，考虑的细节问题比较多，核心问题是抓住哪组数据在进行比较，入栈队列、待判断的出栈队列和空堆栈之间是什么关系。

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

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

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

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

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

• while循环中涉及到pop()，那么就要有个判空的条件，只要堆栈不空，那么循环可以继续，否则，循环终止。

• 大循环中将遍历的入栈元素push()，那么压栈后若堆栈size()大于容量，就说明无法模拟待判断的出栈顺序，直接返回非。

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

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')