題目內(nèi)容

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 分，模擬堆棧入棧出棧過程，難度較大，考慮的細節(jié)問題比較多，核心問題是抓住哪組數(shù)據(jù)在進行比較，入棧隊列、待判斷的出棧隊列和空堆棧之間是什么關(guān)系。

首先，新建一個空的堆棧，模擬整個入棧出棧的過程。入棧順序與數(shù)據(jù)由入棧隊列一步一步無腦給出，因此外層一個大的循環(huán)。

堆棧要與待判斷的出棧隊列相比較。自然，直接看堆?？吹降氖侨霔５捻樞颍}目是對比的出棧順序，因此必然要用到pop()，出棧隊列依次與彈出的元素相比較，完全符合且當入棧的大循環(huán)結(jié)束后堆棧為空，那么打印YES。然而使用pop()來比較有諸多不便，大部分堆棧的pop()方法是不返回值，那么應(yīng)該使用top()方法取得棧頂元素，如果棧頂元素滿足上述要求，那么執(zhí)行pop()。

彈出元素后要以出棧隊列的下一個元素為基準，繼續(xù)判斷。因此出棧隊列元素需要有一個指針來標注當前的基準元素，最初指針為0，在pop()后指針+1。彈出元素后指針和棧頂元素都不同了，那么就存在這時的棧頂元素可能會滿足更新后的基準元素，那么應(yīng)該繼續(xù)彈出，指針繼續(xù)+1，直到二者不相等。那么這樣的過程就可以用while語句描述，構(gòu)成內(nèi)部的一個循環(huán)。

需要指出的是，涉及到堆棧時，一定要考慮兩個邊界問題。第一，棧是否為空，若為空，那么無法執(zhí)行pop()/top()指令；第二，棧是否有容量，容量為多大，若當前的size()超過了棧的容量，那么無法執(zhí)行push()指令。

有了這兩個邊界問題，再來看上面的分析過程。

• while循環(huán)中涉及到pop()，那么就要有個判空的條件，只要堆棧不空，那么循環(huán)可以繼續(xù)，否則，循環(huán)終止。

• 大循環(huán)中將遍歷的入棧元素push()，那么壓棧后若堆棧size()大于容量，就說明無法模擬待判斷的出棧順序，直接返回非。

在大循環(huán)結(jié)束后，也就是元素全部入棧后，要對堆棧判空。如果堆棧是空的，說明入棧的所有元素已經(jīng)按照待判斷的出棧順序依次pop()，可以打印YES，否則，說明堆?，F(xiàn)有的元素順序無法滿足，因此堆在堆棧里彈不出去，打印NO。另外一個角度，判斷出棧隊列的指針也是等價的。如果出棧隊列的指針越界，那么說明待比較的元素都已經(jīng)找到滿足要求的入棧元素，此時堆棧為空。

AC 源代碼