001什么是棧？

棧是一種后進(jìn)先出（Last in First Out）的數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)稱 LIFO。棧是一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱為棧頂，另一端稱為棧底。

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
    //再?gòu)椧淮危藭r(shí)棧頂元素為5了，如下。
    System.out.println(stack.pop());
    //獲取棧頂元素但不刪除,這時(shí)的棧頂元素以及是4了
    System.out.println(stack.peek());
    //判斷棧頂元素是否為空
    System.out.println(stack.empty());
    Stack < Integer > stack1 = new Stack < > ();
    System.out.println(stack1.empty());
    //獲取棧中的元素的位置，棧頂為1號(hào)，此時(shí)stack中有3,4兩個(gè)元素，所以4元素的位置為1號(hào)
    System.out.println(stack.search(4));
    //使用父類的方法，stack繼承自Vector
    System.out.println(stack.isEmpty());
}

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

A. 棧頂元素最先能被刪除
B. 棧頂元素最后才能被刪除
C. 棧底元素永遠(yuǎn)不能被刪除
D. 棧底元素最先被刪除
答案: A    
解析：棧里面的元素都有被刪除的機(jī)會(huì)，只不過(guò)棧頂?shù)脑刈钕葎h除，棧底的元素最后刪除。

004一個(gè)棧的輸入序列為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先進(jìn)入，所以1在3之后出來(lái)。

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

A. 棧的頂
B. 棧的底
C. 棧指針
D. 棧中的數(shù)據(jù)
答案: B   
解析：暫無(wú)解析。

006new 創(chuàng)建對(duì)象時(shí)，對(duì)象的內(nèi)存和指向?qū)ο蟮闹羔樂(lè)謩e分配在( ).

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

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

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

008設(shè)若入棧序列的元素順序?yàn)閄,Y,Z，判斷下列哪一個(gè)出棧序列是不可能的( )。

A. XYZ
B. YZX
C. ZXY
D. ZYX
答案: C   
解析：因?yàn)闂Ｊ窍冗M(jìn)后出，X在Y之前進(jìn)入，所以X肯定在Y之后出來(lái)，所以ZXY不可能。

009設(shè)計(jì)一個(gè)獲取棧中最小元素的棧

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判斷某個(gè)數(shù)組是否是正確的出棧順序。

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();
    }
}