题目内容

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" if it is indeed a possible pop sequence of the stack, or "NO" if not.

Sample Input:

Sample Output:

题目要点

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

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

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

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

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

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

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

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

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

AC 源代码