[[343379]]

本文轉載自微信公眾號「Java中文社群」，作者磊哥  。轉載本文請聯系Java中文社群公眾號。  

正式開始之前，先和各位朋友聊聊公眾號后期的一些打算，后面的文章計劃寫一些關于數據結構和算法的內容，原因很簡單「底層結構決定上層建筑嘛」，對于框架滿天飛的今天，我們不止要學習如何使用框架，更要了解它的原理以及底層數據結構，只有這樣我們才能更好的應用它。

當然，除了上述原因之外，還有一個重要因素是為了搞定面試。

隨著軟件開發行業競爭的日益激烈，面試的難度也在逐漸增加，因為企業要從眾多的面試人中選出最優秀的人，只能提高面試的難度，而算法和數據結構比較燒腦的硬核技能之一，自然也就成了面試的首選科目。并且隨著時間的推移，算法和數據結構出現的頻率和占比也會不斷增加，因此為了順應時代發展的潮流，我們也要做一些調整，所以在后面的一些文章中，我會陸續更新一些關于算法和數據結構的文章，希望大家能夠喜歡。

PS：當然隨著智能系統的普及(如今日頭條和抖音)，算法和數據結構在企業中應用也越來越多，因此學習算法和數據結構也是迫在眉睫的事了。

棧定義

棧(Stack)又叫堆棧(簡稱棧)，它是在同一端進行插入和刪除數據的線性表。

棧是最基礎也是最常見的數據結構之一，它的數據結構和操作流程如下圖所示：

其中，允許進行插入和刪除的一端叫作棧頂(Top)，另一端叫作棧底(Bottom)，棧底固定，棧頂浮動。

當棧中的元素為零時，該棧叫作空棧。添加數據時一般叫作入棧或進棧(Push)，刪除數據叫作出棧或退棧(Pop)。棧是后進先出(Last In First Out，LIFO)的線性表。

物理結構 & 邏輯結構

在手擼算法之前，我們先來認識一下數據結構中的兩個重要概念：物理結構和邏輯結構。

當談到“物理”和“邏輯”一詞時，我們可以會想到數據庫中的邏輯刪除和物理刪除。

所謂的物理刪除是指通過刪除命令真實的將數據從物理結構中刪除的過程;而邏輯刪除是指通過修改命令將數據更改為“已刪除”的狀態，并非真實的刪除數據。

這里的邏輯結構和物理結構和上面的概念類似，所謂的物理結構是指可以將數據存儲在物理空間中，比如數組和鏈表都屬于物理數據結構;而邏輯結構則是用于描述數據間的邏輯關系的，比如本文要講的棧就屬于邏輯結構。

可能有些人看到這里就蒙了，沒關系，我這里舉一個例子你就明白了。

如果用人來表示物理結構和邏輯結構的話，那么真實存在的有血有肉的人就屬于物理結構，而人的思想和信念就屬于邏輯結構了。

自定義棧I：數組實現

通過上面的內容，我們知道了棧屬于邏輯結構，因此它的實現方式就可以有很多種了，比如數組的實現方式或者是鏈表的實現方式。那么我們就先用數組實現一下，棧的主要方法有：

① 定義結構

那么我們先來定義它的結構：

public class MyStack<E> { 
    private Object[] value = null; // 棧存儲容器 
    private int top = -1; // 棧頂（的指針） 
    private int maxSize = 0; // 棧容量 
 
    // 構造函數（初始化默認容量） 
    MyStack() { 
        this.maxSize = 10; 
    } 
 
    // 有參構造函數 
    MyStack(int initSize) throws Exception { 
        if (initSize <= 0) { 
            throw new Exception("棧容量必須大于 0"); 
        } else { 
            value = new Object[initSize]; 
            maxSize = initSize; 
            top = -1; 
        } 
    } 
} 

其中棧中數據會存儲在 Object[] value 數組中，top 變量代表棧頂的指針，它其實存儲的是棧頂元素的下標，會隨著入棧不斷變化(后進先出)，maxSize 表示棧的最大容量。

② 入棧

此方法是給棧添加數據的，實現代碼如下：

// 入棧（數據添加） 
public boolean push(E e) throws Exception { 
    if (maxSize - 1 == top) { 
        throw new Exception("入棧失敗，棧已滿"); 
    } else { 
        value[++top] = e; 
        return true; 
    } 
} 

每次當有數據插入時，只需在數組中添加一個值，并將棧頂的下標 +1 即可。

入棧操作如下圖所示：

③ 出棧

此方法是刪除棧中的數據的，實現代碼如下：

// 數據移除（出棧） 
public E pop() throws Exception { 
    if (top <= -1) { 
        throw new Exception("移除失敗，棧中已無數據"); 
    } else { 
        return (E) value[top--]; 
    } 
} 

出棧只需刪除數組中棧頂數據(最后加入的數據)，并修改棧頂下標 -1 即可。

出棧操作如下圖所示：

④ 數據查詢

除了以上操作方法之外，我們還需要添加一個查詢棧頂數據的方法：

// 數據查詢 
public E peep() throws Exception { 
    if (top <= -1) { 
        throw new Exception("移除失敗，棧中已無數據"); 
    } else { 
        return (E) value[top]; 
    } 
} 

⑤ 代碼測試

到此為止棧的數據結構就已經實現完了，接下來我們來測試一下：

// 代碼測試 
public static void main(String[] args) throws Exception { 
    MyStack stack = new MyStack(10); 
    stack.push("Hello"); 
    stack.push("Java"); 
    System.out.println(stack.peep()); 
    stack.pop(); 
    System.out.println(stack.pop()); 
} 

以上程序的執行結果為：

Java

Hello

從上述代碼可以看出，我們添加棧的順序是 Hello、Java 而輸出的順序是 Java、 Hello 符合棧的定義(后進先出)。

自定義棧II：鏈表實現

除了數組之外，我們可以還可使用鏈表來實現棧結構，它的實現稍微復雜一些，我們先來看鏈表本身的數據結構：

使用鏈表實現棧的流程如下：

也就是說，入棧時我們將數據存儲在鏈表的頭部，出棧時我們從頭部進行移除，并將棧頂指針指向原頭部元素的下一個元素，實現代碼如下。

我們先來定義一個鏈表節點：

public class Node { 
    Object value; // 每個節點的數據 
    Node next; // 下一個節點 
 
    public Node(Object value) { 
        this(value, null); 
    } 
 
    /** 
     * 創建新節點 
     * @param value 當前節點數據 
     * @param next  指向下一個節點（頭插法） 
     */ 
    public Node(Object value, Node next) { 
        this.value = value; 
        this.next = next; 
    } 
} 

接下來我們使用鏈表來實現一個完整的棧：

public class StackByLinked { 
 
    private Node top = null; // 棧頂數據 
    private int maxSize = 0; // 棧最大容量 
    private int leng = 0; // 棧實際容量 
 
    public StackByLinked(int initSize) throws Exception { 
        if (initSize <= 0) { 
            throw new Exception("棧容量不能小于等于0"); 
        } 
        top = null; 
        maxSize = initSize; 
        leng = 0; 
    } 
 
    /** 
     * 容量是否已滿 
     * @return 
     */ 
    public boolean isFull() { 
        return leng >= maxSize; 
    } 
 
    /** 
     * 是否為空 
     * @return 
     */ 
    public boolean isEmpty() { 
        return leng <= 0; 
    } 
 
    /** 
     * 入棧 
     * @param val 
     * @return 
     * @throws Exception 
     */ 
    public boolean push(Object val) throws Exception { 
        if (this.isFull()) { 
            // 容量已滿 
            throw new Exception("容量已滿"); 
        } 
        top = new Node(val, top); // 存入信息，并將當前節點設置為頭節點 
        leng++; 
        return true; 
    } 
 
    /** 
     * 出棧（移除） 
     * @return 
     * @throws Exception 
     */ 
    public Node pop() throws Exception { 
        if (this.isEmpty()) { 
            throw new Exception("棧為空，無法進行移除操作"); 
        } 
        Node item = top; // 返回當前元素 
        top = top.next; 
        leng--; 
        return item; 
    } 
 
    /** 
     * 查詢棧頂信息 
     * @return 
     */ 
    public Node peek() throws Exception { 
        if (isEmpty()) { 
            throw new Exception("你操作的是一個空棧"); 
        } 
        return top; 
    } 
 
    // 代碼測試 
    public static void main(String[] args) throws Exception { 
        StackByLinked stack = new StackByLinked(10); 
        stack.push("Hello"); 
        stack.push("Java"); 
        System.out.println(stack.peek().value); 
        stack.pop(); 
        System.out.println(stack.pop().value); 
    } 
} 

以上程序的執行結果是：

Java

Hello

總結

本文我們使用了數組和鏈表等物理結構來實現了棧，當然我們也可以使用其他容器來實現，比如 Java 中的 List，我們只需要保證在操作棧時是后進先出的執行順序，并且至少包含 3 個重要方法：入棧、出棧和查詢棧頂元素就可以了。

最后

算法和數據結構的學習是 3 分學 7 分練，只看不練是沒辦法學好算法的，而且學習算法和數據結構是一個循序漸進的過程，短時間內不會有明顯的收效。因為這些算法經過了幾百年的發展和積累才得以流傳下來的，所以想要“玩得轉”還需要一點耐心。

這里給你講一個學習算法的“秘訣”：看不懂的知識要反復看，如果反復看還是看不懂，那么別著急，休息一下再繼續看!相信我，對于學習算法這件事，所有人的過程都是一樣的。