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

堆疊

如上就是堆疊的概念圖，現在存盤在堆疊中的只有資料 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 = https://www.cnblogs.com/wupeixuan/p/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 = https://www.cnblogs.com/wupeixuan/p/data;
            this.next = next;
        }

        public int getData() {
            return data;
        }
    }
}

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

不管是順序堆疊還是鏈式堆疊，我們存盤資料只需要一個大小為 n 的陣列就夠了，在入堆疊和出堆疊程序中，只需要一兩個臨時變數存盤空間，所以空間復雜度是 O(1)，

入堆疊和出堆疊只會影響到最后一個元素，不涉及其他元素的整體移動，所以無論是以陣列還是以鏈表實作，入堆疊、出堆疊的時間復雜度都是 O(1)，

總結

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

參考

《我的第一本演算法書》

《演算法圖解》

標籤：其他

上一篇：leetcode| 56. 合并區間

下一篇：復雜度