摘要：介紹棧是一種后進(jìn)先出的線性表數(shù)據(jù)結(jié)構(gòu)，分為棧頂和棧底兩端，僅允許在表的一端插入元素，這一端被稱為棧頂，另外一端稱之為棧底。

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

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

后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，Last In First Out（LIFO）

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

入棧操作示意圖

出棧操作示意圖（后進(jìn)的元素先出）

向棧中添加一個(gè)元素（入棧）

void push(E e)

從棧中刪除一個(gè)元素（出棧）

E pop()

查看棧頂元素

E peek()

查看棧中元素個(gè)數(shù)

int getSize()

判斷棧是否為空

boolean isEmpty()

實(shí)現(xiàn)棧的方式，實(shí)際上底層有多種實(shí)現(xiàn)方式，比如：動態(tài)數(shù)組等，這里我們使用Java語言本身為我們提供的集合LinkedList

接口定義：Stack

public interface Stack {

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

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

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

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

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

}

LinkedListStack 類實(shí)現(xiàn)接口Stack

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

    /**
     * 構(gòu)造棧結(jié)構(gòu)
     */
    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 +
                "}";
    }
}

測試類：LinkedListStackTest

@Test
public void testLinkedListStack() {
    // 棧
    Stack stack = new LinkedListStack<>();
    // 準(zhǔn)備入棧元素
    List 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);
    // 獲取棧中元素的個(gè)數(shù)
    int stackSize = stack.getSize();
    System.out.println("棧中元素個(gè)數(shù)：" + stackSize);
}

運(yùn)行結(jié)果

入棧操作：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
棧中元素個(gè)數(shù)：4

虛擬機(jī)棧的入棧和出棧操作

在Java虛擬機(jī)運(yùn)行時(shí)數(shù)據(jù)區(qū)有一塊被稱之為：虛擬機(jī)棧，它是線程私有的，聲明周期與線程相同。

我們編寫的每個(gè)Java方法，每個(gè)方法都會在執(zhí)行的時(shí)候同時(shí)都會創(chuàng)建一個(gè)棧幀（Stack Frame）用于存儲局部變量表、操作數(shù)棧、動態(tài)鏈接、方法出口等信息。每一個(gè)方法從調(diào)用直至執(zhí)行完成的過程，就對應(yīng)這一個(gè)棧幀在虛擬機(jī)棧中入棧到出棧的過程。

現(xiàn)在我們假設(shè)有A、B、C三個(gè)方法，在A方法中調(diào)用B方法（A->B），在B方法中調(diào)用C方法（B->C），C方法執(zhí)行本方法業(yè)務(wù)邏輯。

當(dāng)程序執(zhí)行到A()方法的中的第二行時(shí)，此時(shí)程序會中斷A()方法并開始調(diào)用B()方法，然后會在虛擬機(jī)棧中記錄調(diào)用B()方法的棧幀，我這里暫且稱之為A2（實(shí)際存儲的并不是O(∩_∩)O哈?。┦疽鈭D如下：

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

當(dāng)程序開始執(zhí)行到C()方法時(shí)，直到執(zhí)行完C()方法時(shí)，這時(shí)候，程序該如何執(zhí)行呢？

此時(shí)就要查看一下虛擬機(jī)棧了，發(fā)現(xiàn)虛擬機(jī)棧，棧中棧頂?shù)脑厥?b>B2，我們的程序就知道了，它是執(zhí)行到B()方法的B2位置就中斷了，去執(zhí)行C()方法了；現(xiàn)在C()方法執(zhí)行完成之后，它就可以跳回到B2的位置繼續(xù)執(zhí)行了，當(dāng)B()方法執(zhí)行完之后，虛擬機(jī)棧中的B2棧幀也就可以出棧了，依次類推....

如果一個(gè)方法，使用遞歸調(diào)用，若遞歸臨界點(diǎn)判斷有誤，則方法就會一直的被進(jìn)行入棧操作，如果超過虛擬機(jī)棧的默認(rèn)容量大小，則會出現(xiàn)我們常見的 StackOverflowError 異常

完整版代碼GitHub倉庫地址：Java版數(shù)據(jù)結(jié)構(gòu)-棧 歡迎大家【關(guān)注】和【Star】

本次我們完成的是基于Java自身自帶的集合LinkedList來實(shí)現(xiàn)棧，有興趣的童鞋，可以使用動態(tài)數(shù)組方式來實(shí)現(xiàn)；接下來，筆者還會一一的實(shí)現(xiàn)其它常見的數(shù)組結(jié)構(gòu)。

靜態(tài)數(shù)組

動態(tài)數(shù)組

棧

隊(duì)列

鏈表

循環(huán)鏈表

二分搜索樹

優(yōu)先隊(duì)列

堆

線段樹

字典樹

AVL

紅黑樹

哈希表

....

持續(xù)更新中，歡迎大家關(guān)注公眾號：小白程序之路（whiteontheroad），第一時(shí)間獲取最新信息！??！

筆者博客地址：http:www.gulj.cn