本文將介紹一個重要的數據結構—棧，和之前講到的

棧

如上就是棧的概念圖，現在存儲在棧中的只有數據 Blue。往棧中添加數據的時候，新數據被放在最上面。

然後，我們往棧中添加了數據 Green。往棧中添加數據的操作叫作入棧。

接下來，數據 Red 入棧。

從棧中取出數據時，是從最上面，也就是最新的數據開始取出的，即 Red。從棧中取出數據的操作叫作出棧。

如果再進行一次出棧操作，取出的就是 Green 了。

像棧這種最後添加的數據最先被取出，即後進先出的結構，我們稱為 Last In First Out，簡稱

與鏈表和數組一樣，棧的數據也是線性排列，但在棧中，添加和刪除數據的操作只能在一端進行，訪問數據也只能訪問到頂端的數據，想要訪問中間的數據時，就必須通過出棧操作將目標數據移到棧頂才行。

介紹完棧的基本知識後，接下來舉一個例子，比如大家正在看公眾號文章，那我就拿微信的訂閱號為例。

如何理解棧？

首先你打開訂閱號，是一個公眾號列表，之後你點擊了一個公眾號-武培軒，進入了相應的文章列表界面，之後你點擊了文章-https://www.tianheyu.top/archives/what-is-array，進入了文章詳情頁面。

好了，現在你想返回訂閱號怎麼辦呢？向右滑兩次吧，第一次回到文章列表界面，第二次回到訂閱號界面。

這時候你就發現了，這些界面的儲存結構可以說是一個棧結構，你打開文章詳情頁面，必須經過兩次入棧才能達到，你想回到訂閱號界面（位於棧底），必須經歷兩次出棧把前面兩個界面移除。

棧的實現

看到這裡，相信你已經對棧有了初步的理解，棧主要包含兩個操作，入棧和出棧，也就是在棧頂插入一個數據和從棧頂刪除一個數據。光理解還不夠，我們還要動手去實現棧，接下來讓我們來看一看如何用代碼實現一個棧。

棧有兩種存儲結構，即順序存儲和鏈式存儲，也就是說棧既可以用數組來實現，也可以用鏈表來實現。用數組實現的棧，我們叫作順序棧，用鏈表實現的棧，我們叫作鏈式棧。

首先來看下用數組實現的棧是怎麼樣的，其實現如下圖所示：

那麼我先用 Java 語言來實現下順序棧，代碼如下：

<code>/** * 基於數組實現的順序棧 * * @author wupx * @date 2020/02/11 */public class ArrayStack {    /**     * 數組     */    private String[] items;    /**     * 棧中元素個數     */    private int count;    /**     * 棧的大小     */    private int n;    /**     * 初始化數組，申請一個大小為 n 的數組空間     *     * @param n     */    public ArrayStack(int n) {        this.items = new String[n];        this.n = n;        this.count = 0;    }    /**     * 入棧     *     * @param item     * @return     */    public boolean push(String item) {        // 數組空間不夠了，直接返回 false，入棧失敗。        if (count == n) {            return false;        }        // 將 item 放到下標為 count 的位置，並且 count 加一        items[count] = item;        ++count;        return true;    }    /**     * 出棧     *     * @return     */    public String pop() {        // 棧為空，則直接返回 null        if (count == 0) {            return null;        }        // 返回下標為 count-1 的數組元素，並且棧中元素個數 count 減一        String tmp = items[count - 1];        --count;        return tmp;    }}/<code> 

另外一種就是鏈式棧，它的實現如下圖所示：

再用鏈表去實現棧，代碼如下：

<code>/** * 基於鏈表實現的鏈式棧 * * @author wupx * @date 2020/02/11 */public class LinkedListStack {    private Node top = null;    /**     * 入棧     *     * @param value     */    public void push(int value) {        Node newNode = new Node(value, null);        // 判斷是否棧空        if (top != null) {            newNode.next = top;        }        top = newNode;    }    /**     * 出棧     *     * @return     */    public int pop() {        if (top == null) {            // -1 表示棧中沒有數據            return -1;        }        int value = top.data;        top = top.next;        return value;    }    public void printAll() {        Node p = top;        while (p != null) {            System.out.print(p.data + " ");            p = p.next;        }        System.out.println();    }    private static class Node {        private int data;        private Node next;        public Node(int data, Node next) {            this.data = data;            this.next = next;        }        public int getData() {            return data;        }    }}/<code>

在對棧有了更深一步的理解和實踐後，讓我們來看下它的空間、時間複雜度各是多少呢？

不管是順序棧還是鏈式棧，我們存儲數據只需要一個大小為 n 的數組就夠了。在入棧和出棧過程中，只需要一兩個臨時變量存儲空間，所以

入棧和出棧只會影響到最後一個元素，不涉及其他元素的整體移動，所以無論是以數組還是以鏈表實現，入棧、出棧的時間複雜度都是 O(1)。

總結

看完之後，相信大家都對棧有了一定的瞭解，讓我們總結下這篇文章的內容，棧是一種線性邏輯結構，只支持入棧和出棧操作，遵循後進先出的原則（FILO）。棧既可以通過數組實現，也可以通過鏈表來實現，不管基於數組還是鏈表，入棧、出棧的時間複雜度都為 O(1)。

參考

《我的第一本算法書》

《算法圖解》

閱讀更多 武培軒 的文章

關鍵字: 鏈表 數據結構 數據