[[343379]]

本文轉(zhuǎn)載自微信公眾號「Java中文社群」，作者磊哥  。轉(zhuǎn)載本文請聯(lián)系Java中文社群公眾號。  

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

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

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

PS：當(dāng)然隨著智能系統(tǒng)的普及(如今日頭條和抖音)，算法和數(shù)據(jù)結(jié)構(gòu)在企業(yè)中應(yīng)用也越來越多，因此學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)也是迫在眉睫的事了。

棧定義

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

棧是最基礎(chǔ)也是最常見的數(shù)據(jù)結(jié)構(gòu)之一，它的數(shù)據(jù)結(jié)構(gòu)和操作流程如下圖所示：

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

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

物理結(jié)構(gòu) & 邏輯結(jié)構(gòu)

在手擼算法之前，我們先來認識一下數(shù)據(jù)結(jié)構(gòu)中的兩個重要概念：物理結(jié)構(gòu)和邏輯結(jié)構(gòu)。

當(dāng)談到“物理”和“邏輯”一詞時，我們可以會想到數(shù)據(jù)庫中的邏輯刪除和物理刪除。

所謂的物理刪除是指通過刪除命令真實的將數(shù)據(jù)從物理結(jié)構(gòu)中刪除的過程;而邏輯刪除是指通過修改命令將數(shù)據(jù)更改為“已刪除”的狀態(tài)，并非真實的刪除數(shù)據(jù)。

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

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

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

自定義棧I：數(shù)組實現(xiàn)

通過上面的內(nèi)容，我們知道了棧屬于邏輯結(jié)構(gòu)，因此它的實現(xiàn)方式就可以有很多種了，比如數(shù)組的實現(xiàn)方式或者是鏈表的實現(xiàn)方式。那么我們就先用數(shù)組實現(xiàn)一下，棧的主要方法有：

① 定義結(jié)構(gòu)

那么我們先來定義它的結(jié)構(gòu)：

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

其中棧中數(shù)據(jù)會存儲在 Object[] value 數(shù)組中，top 變量代表棧頂?shù)闹羔槪鋵嵈鎯Φ氖菞ｍ斣氐南聵?biāo)，會隨著入棧不斷變化(后進先出)，maxSize 表示棧的最大容量。

② 入棧

此方法是給棧添加數(shù)據(jù)的，實現(xiàn)代碼如下：

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

每次當(dāng)有數(shù)據(jù)插入時，只需在數(shù)組中添加一個值，并將棧頂?shù)南聵?biāo) +1 即可。

入棧操作如下圖所示：

③ 出棧

此方法是刪除棧中的數(shù)據(jù)的，實現(xiàn)代碼如下：

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

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

出棧操作如下圖所示：

④ 數(shù)據(jù)查詢

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

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

⑤ 代碼測試

到此為止棧的數(shù)據(jù)結(jié)構(gòu)就已經(jīng)實現(xiàn)完了，接下來我們來測試一下：

// 代碼測試 
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()); 
} 

以上程序的執(zhí)行結(jié)果為：

Java

Hello

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

自定義棧II：鏈表實現(xiàn)

除了數(shù)組之外，我們可以還可使用鏈表來實現(xiàn)棧結(jié)構(gòu)，它的實現(xiàn)稍微復(fù)雜一些，我們先來看鏈表本身的數(shù)據(jù)結(jié)構(gòu)：

使用鏈表實現(xiàn)棧的流程如下：

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

我們先來定義一個鏈表節(jié)點：

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

接下來我們使用鏈表來實現(xiàn)一個完整的棧：

public class StackByLinked { 
 
    private Node top = null; // 棧頂數(shù)據(jù) 
    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); // 存入信息，并將當(dāng)前節(jié)點設(shè)置為頭節(jié)點 
        leng++; 
        return true; 
    } 
 
    /** 
     * 出棧（移除） 
     * @return 
     * @throws Exception 
     */ 
    public Node pop() throws Exception { 
        if (this.isEmpty()) { 
            throw new Exception("棧為空，無法進行移除操作"); 
        } 
        Node item = top; // 返回當(dāng)前元素 
        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); 
    } 
} 

以上程序的執(zhí)行結(jié)果是：

Java

Hello

總結(jié)

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

最后

算法和數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)是 3 分學(xué) 7 分練，只看不練是沒辦法學(xué)好算法的，而且學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)是一個循序漸進的過程，短時間內(nèi)不會有明顯的收效。因為這些算法經(jīng)過了幾百年的發(fā)展和積累才得以流傳下來的，所以想要“玩得轉(zhuǎn)”還需要一點耐心。

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