001什么是棧？

棧是一種后進先出（Last in First Out）的數據結構，簡稱 LIFO。棧是一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。

002棧的基本使用

public static void main(String[] args) {
    Stack < Integer > stack = new Stack < Integer > ();
    //入棧
    stack.push(3); //棧底
    stack.push(4);
    stack.push(5);
    stack.push(7); //棧頂
    //出棧：彈出棧頂元素
    System.out.println(stack.pop()); //7
    //再彈一次，此時棧頂元素為5了，如下。
    System.out.println(stack.pop());
    //獲取棧頂元素但不刪除,這時的棧頂元素以及是4了
    System.out.println(stack.peek());
    //判斷棧頂元素是否為空
    System.out.println(stack.empty());
    Stack < Integer > stack1 = new Stack < > ();
    System.out.println(stack1.empty());
    //獲取棧中的元素的位置，棧頂為1號，此時stack中有3,4兩個元素，所以4元素的位置為1號
    System.out.println(stack.search(4));
    //使用父類的方法，stack繼承自Vector
    System.out.println(stack.isEmpty());
}

003下列關于棧敘述正確的是( )。

A. 棧頂元素最先能被刪除
B. 棧頂元素最后才能被刪除
C. 棧底元素永遠不能被刪除
D. 棧底元素最先被刪除
答案: A    
解析：棧里面的元素都有被刪除的機會，只不過棧頂的元素最先刪除，棧底的元素最后刪除。

004一個棧的輸入序列為1 2 3 4 5，則下列序列中不可能是棧的輸出序列的是 ( )。

A. 2 3 4 1 5
B. 5 4 1 3 2
C. 2 3 1 4 5
D. 1 5 4 3 2
答案: B   
解析：B中1比3先進入，所以1在3之后出來。

005在棧中,( )保持不變。

A. 棧的頂
B. 棧的底
C. 棧指針
D. 棧中的數據
答案: B   
解析：暫無解析。

006new 創建對象時，對象的內存和指向對象的指針分別分配在( ).

A. 堆區，棧區
B. 常量區，堆區
C. 全局區，棧區
D. 棧區，堆區
答案: A   
解析：對象放在堆去，引用放在棧區。

007假設用S表示進棧操作，用X表示出棧操作。如果元素的進棧順序是abcd，為了得到出棧序列abcd，則相應的S和X的操作序列為( )？

A. SSSSXXXX
B. SSSXXSXX
C. SXSSXXSX
D. SXSXSXSX
答案：D
解析：按照選項中的操作會得到的出棧順序如下
選項A中，abcd進棧，依次出棧，得到出棧順序是dcba；
選項B中，abc進棧，cb出棧，d進棧，da出棧，得到出棧順序是cbda；
選項C中，a進棧，a出棧，bc進棧，cb出棧，d進棧，d出棧，中得到出棧順序是acbd；
選項D中，a進棧，a出棧，b進棧，b出棧，c進棧，c出棧，d進棧，d出棧，中得到出棧順序是abcd；所以正確選項為D。

008設若入棧序列的元素順序為X,Y,Z，判斷下列哪一個出棧序列是不可能的( )。

A. XYZ
B. YZX
C. ZXY
D. ZYX
答案: C   
解析：因為棧是先進后出，X在Y之前進入，所以X肯定在Y之后出來，所以ZXY不可能。

009設計一個獲取棧中最小元素的棧

class MinStack {
    private Stack < Integer > stack;
    private Stack < Integer > minStack;

    public MinStack() {
        stack = new Stack < > ();
        minStack = new Stack < > ();
    }

    public void push(int val) {
        stack.push(val);
        if (!minStack.empty()) {
            int top = minStack.peek();
            if (val <= top) {
                minStack.push(val);
            }
        } else {
            minStack.push(val);
        }
    }

    public void pop() {
        int popVal = stack.pop();
        if (!minStack.empty()) {
            int top = minStack.peek();
            if (top == popVal) {
                minStack.pop();
            }
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

010判斷某個數組是否是正確的出棧順序。

public class Demo5 {
    public static void main(String[] args) {
        int[] A = {
            1, 2, 3, 4, 5
        };
        int[] B = {
            4, 5, 3, 2, 1
        };
        System.out.println(IsPopOrder(A, B));
    }
    public static boolean IsPopOrder(int[] pushA, int[] popA) {
        Stack < Integer > stack = new Stack < > ();
        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (j < popA.length && !stack.empty() && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}