App下載

動圖演示：手?jǐn)]堆棧的兩種實現(xiàn)方法！

猿友 2020-09-23 11:31:53 瀏覽數(shù) (3406)
反饋

文章來源于公眾號：Java中文社群 作者：磊哥

隨著軟件開發(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）又叫堆棧（簡稱棧），它是在同一端進(jìn)行插入和刪除數(shù)據(jù)的線性表。

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

棧的數(shù)據(jù)結(jié)構(gòu)和操作流程

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

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

棧是后進(jìn)先出的線性表

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

在手?jǐn)]算法之前，我們先來認(rèn)識一下數(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)了。

物理結(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 {
    private Object[] value = null; // 棧存儲容器
    private int top = -1; // 棧頂（的指針）
    private int maxSize = 0; // 棧容量


    // 構(gòu)造函數(shù)（初始化默認(rèn)容量）
    MyStack() {
        this.maxSize = 10;
    }


    // 有參構(gòu)造函數(shù)
    MyStack(int initSize) throws Exception {
        if (initSize  Hello


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


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


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


![鏈表的數(shù)據(jù)結(jié)構(gòu)](https://atts.w3cschool.cn/attachments/image/20200923/1600831705876009.png "鏈表的數(shù)據(jù)結(jié)構(gòu)")


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


![鏈表實現(xiàn)棧的流程](https://atts.w3cschool.cn/attachments/image/20200923/1600831725907957.gif "鏈表實現(xiàn)棧的流程")


也就是說，入棧時我們將數(shù)據(jù)存儲在鏈表的頭部，出棧時我們從頭部進(jìn)行移除，并將棧頂指針指向原頭部元素的下一個元素，實現(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 = maxSize;
    }


    /**
     * 是否為空
     * @return
     */
    public boolean isEmpty() {
        return leng  Java
>
> Hello


## 總結(jié)


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


## 最后


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


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


以上就是`W3Cschool編程獅`關(guān)于**動圖演示：手?jǐn)]堆棧的兩種實現(xiàn)方法！**的相關(guān)介紹了，希望對大家有所幫助。
Java

0 人點贊