本文將介紹一個重要的數據結構—棧，和之前講到的鏈表、數組一樣也是一種數據呈線性排列的數據結構，不過在這種結構中，我們只能訪問最新添加的數據。棧就像是一摞書，拿到新書時我們會把它放在書堆的最上面，取書時也只能從最上面的新書開始取。

棧

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

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

接下來，數據 Red 入棧。

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

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

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

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

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

如何理解棧？

首先你打開訂閱號，是一個公眾號列表，之後你點擊了一個公眾號-武培軒，進入了相應的文章列表界面，之後你點擊了文章-什麼是數組？，進入了文章詳情頁面。

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

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

棧的實現

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

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

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

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

/**
 * 基於數組實現的順序棧
 *
 * @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;
    }
}

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

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

/**
 * 基於鏈表實現的鏈式棧
 *
 * @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;
        }
    }
}

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

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

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

總結

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

參考

《我的第一本演算法書》

《演算法圖解》