Java堆棧

介紹

棧是一種后進先出的線性表數據結構，分為棧頂和棧底兩端，僅允許在表的一端插入元素，這一端被稱為棧頂，另外一端稱之為棧底。棧，只有兩種操作，分為入棧(壓棧)和出棧(退棧);向棧中添加元素的操作叫做入棧，相反從棧中刪除元素叫做出棧。

特點

• 只能從棧頂添加元素或者刪除元素

• 后進先出的數據結構，Last In First Out(LIFO)

為了大家更好的形象了解我們通過示意圖來看一下棧的入棧和出棧操作

1. 入棧操作示意圖

2. 出棧操作示意圖(后進的元素先出)

棧的基本操作

• 向棧中添加一個元素(入棧)

void push(E e)

• 從棧中刪除一個元素(出棧)

E pop()

• 查看棧頂元素

E peek()

• 查看棧中元素個數

int getSize()

• 判斷棧是否為空

boolean isEmpty()

實現棧的方式，實際上底層有多種實現方式，比如：動態數組等，這里我們使用Java語言本身為我們提供的集合LinkedList

1. 接口定義：Stack<E>

public interface Stack<E> {

    /**
     * 向棧中添加元素
     *
     * @param e
     */
    void push(E e);

    /**
     * 從棧中刪除元素
     */
    void pop();

    /**
     * 獲取棧頂元素
     *
     * @return
     */
    E peek();

    /**
     * 獲取棧中元素個數
     *
     * @return
     */
    int getSize();

    /**
     * 判斷棧中是否為空
     *
     * @return
     */
    boolean isEmpty();

}

2. LinkedListStack<E> 類實現接口Stack<E>

public class LinkedListStack<E> implements Stack<E> {
    /**
     * 存放棧元素
     */
    LinkedList<E> list;

    /**
     * 構造棧結構
     */
    public LinkedListStack() {
        list = new LinkedList<>();
    }

    @Override
    public void push(E e) {
        list.addLast(e);
    }

    @Override
    public void pop() {
        list.removeLast();
    }

    @Override
    public E peek() {
        return list.getLast();
    }

    @Override
    public int getSize() {
        return list.size();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public String toString() {
        return "LinkedListStack{" +
                "list=" + list +
                '}';
    }
}

3. 測試類：LinkedListStackTest

@Test
public void testLinkedListStack() {
    // 棧
    Stack<String> stack = new LinkedListStack<>();
    // 準備入棧元素
    List<String> prepareElements = Arrays.asList("A", "B", "C", "D", "E");
    // 入棧
    prepareElements.forEach(x -> {
        stack.push(x);
        System.out.println("入棧操作：" + stack);
    });
    // 出棧
    stack.pop();
    System.out.println("出棧操作：" + stack);
    // 獲取棧頂元素
    String peekElement = stack.peek();
    System.out.println("棧頂元素：" + peekElement);
    // 獲取棧中元素的個數
    int stackSize = stack.getSize();
    System.out.println("棧中元素個數：" + stackSize);
}

4. 運行結果

入棧操作：LinkedListStack{list=[A]}
入棧操作：LinkedListStack{list=[A, B]}
入棧操作：LinkedListStack{list=[A, B, C]}
入棧操作：LinkedListStack{list=[A, B, C, D]}
入棧操作：LinkedListStack{list=[A, B, C, D, E]}
出棧操作：LinkedListStack{list=[A, B, C, D]}
棧頂元素：D
棧中元素個數：4

棧的應用

虛擬機棧的入棧和出棧操作

在Java虛擬機運行時數據區有一塊被稱之為：虛擬機棧，它是線程私有的，聲明周期與線程相同。

我們編寫的每個Java方法，每個方法都會在執行的時候同時都會創建一個棧幀(Stack Frame)用于存儲局部變量表、操作數棧、動態鏈接、方法出口等信息。每一個方法從調用直至執行完成的過程，就對應這一個棧幀在虛擬機棧中入棧到出棧的過程。

現在我們假設有A、B、C三個方法，在A方法中調用B方法(A->B)，在B方法中調用C方法(B->C)，C方法執行本方法業務邏輯。

當程序執行到A()方法的中的第二行時，此時程序會中斷A()方法并開始調用B()方法，然后會在虛擬機棧中記錄調用B()方法的棧幀，我這里暫且稱之為A2(實際存儲的并不是O(∩_∩)O哈!)示意圖如下：

同理，當程序執行到B()方法中第二行時，此時程序也會中斷B()方法開始調用C()方法，然后同樣地會在虛擬機棧中生成調用C()方法的棧幀并記錄，我這里暫且稱之為B2，示意圖如下：

當程序開始執行到C()方法時，直到執行完C()方法時，這時候，程序該如何執行呢?

此時就要查看一下虛擬機棧了，發現虛擬機棧，棧中棧頂的元素是B2，我們的程序就知道了，它是執行到B()方法的B2位置就中斷了，去執行C()方法了;現在C()方法執行完成之后，它就可以跳回到B2的位置繼續執行了，當B()方法執行完之后，虛擬機棧中的B2棧幀也就可以出棧了，依次類推....

如果一個方法，使用遞歸調用，若遞歸臨界點判斷有誤，則方法就會一直的被進行入棧操作，如果超過虛擬機棧的默認容量大小，則會出現我們常見的StackOverflowError 異常。