編程題 Pop Sequence

題目

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

題目的大意就是說，給你第一行數(shù)據(jù)分別表示棧的容量，入棧數(shù)的總數(shù)，那些數(shù)按順序入棧，需要判斷的sequence的數(shù)目，讓你判斷下面的那些sequence是不是可能的出棧序列，如果是，輸出 YES，否則，輸出 NO。

乍一看的時(shí)候一點(diǎn)思路都沒有，然后開始在草稿紙上寫，想著如果是錯(cuò)誤的出棧序列該滿足什么，然后發(fā)現(xiàn)第一個(gè)數(shù)據(jù)必須是 <= 棧的容量的，第二個(gè)應(yīng)該是 <= n+1的，然后后面的數(shù)就判斷不出來了，無奈之下去網(wǎng)上找了找大神的解答，終于有了點(diǎn)思路。參照博客

總體思路就是按照給你的序列，模擬一個(gè)棧，一個(gè)個(gè)出棧比較，如果錯(cuò)誤，就判斷 NO，否則判斷 YES。更具體的來說，按照給你的信息，構(gòu)造一個(gè)容量和輸入的第一行信息所給的一樣的棧，然后一行一行地，對數(shù)據(jù)進(jìn)行判斷：當(dāng)棧為空或者棧不空，但是棧頂元素小于序列對應(yīng)的元素且棧未滿，就按順序把數(shù)字入棧，然后判斷棧頂元素和序列對應(yīng)的元素，如果相等，說明正確，出棧；如果棧頂大于對應(yīng)元素，說明不可能出現(xiàn)對應(yīng)出棧隊(duì)列，直接判斷為 NO；如果棧頂小于對應(yīng)元素但是棧已經(jīng)滿了，說明不可能再將其入棧，也不會(huì)出現(xiàn)所示序列，直接判斷為 NO。

比如說序列 3 2 1 7 5 6 4 ，第一個(gè)數(shù)據(jù)是3，此時(shí)棧為空，按順序把1 2 3入棧，之后棧頂為3等于3，出棧，繼續(xù)，2等于2，出棧，繼續(xù)，1等于1，出棧，此時(shí)棧為空了，遇到7，接著順序，把4 5 6 7入棧，7等于7，出棧，繼續(xù)，6大于5，說明棧不可能彈出5，所以判斷為 NO。

完整代碼如下：

import java.util.Scanner;
public class PopSequence {

    private class Stack{
        int N;
        Node top;
        class Node{
            int data;
            Node next;
        }

        int length(){
            return N;
        }

        boolean isEmpty(){
            return top==null;
        }

        int top(){
            return top.data;
        }

        void push(int data){
            Node oldTop = top;
            top = new Node();
            top.data = data;
            top.next = oldTop;
            N = N + 1;
        }

        int pop(){
            int data = top.data;
            top = top.next;
            N = N - 1;
            return data;
        }
    }

    public void start(){
        Scanner in = new Scanner(System.in);
        Stack s;
        String[] line = in.nextLine().split(" ");
        int beginNum;
        int stackSize = Integer.parseInt(line[0]); // 棧的大小
        int sumOfNum = Integer.parseInt(line[1]); // 數(shù)的總數(shù)
        int sequences = Integer.parseInt(line[2]); // 需要判斷的隊(duì)列總數(shù)
        boolean[] judge = new boolean[sequences]; // 對整個(gè)sequence的判斷結(jié)果

        A:for (int i=0; i<sequences; i++){
            s = new Stack();
            beginNum = 1;
            line = in.nextLine().split(" ");
            // 遍歷sequence數(shù)列
            for (int j=0; j<sumOfNum; j++){
                int temp = Integer.parseInt(line[j]);
                // 當(dāng)棧為空或棧頂元素小于當(dāng)前要比較的元素時(shí)且棧不滿，將元素入棧
                while (s.isEmpty() || s.top()<temp&&(s.length()<stackSize)){
                    s.push(beginNum++);
                }
                if (s.top() == temp){
                    s.pop();
                    continue;
                }
                if (s.top()<temp && s.length()==stackSize || s.top()>temp){
                    judge[i] = false;
                    continue A;
                }
            }
            judge[i] = true;
        }

        for (int i=0; i<sequences; i++){
            if (judge[i]){
                System.out.println("YES");
            } else{
                System.out.println("NO");
            }
        }
    }

    public static void main(String[] args) {
        PopSequence p = new PopSequence();
        p.start();
    }
}