Java版-數據結構-棧

voidking 發布于2019-08-16 16:10 / 1678人閱讀

摘要：介紹棧是一種后進先出的線性表數據結構，分為棧頂和棧底兩端，僅允許在表的一端插入元素，這一端被稱為棧頂，另外一端稱之為棧底。

介紹

棧是一種后進先出的線性表數據結構，分為棧頂和棧底兩端，僅允許在表的一端插入元素，這一端被稱為棧頂，另外一端稱之為棧底。棧，只有兩種操作，分為入棧（壓棧）和出棧（退棧）；向棧中添加元素的操作叫做入棧，相反從棧中刪除元素叫做出棧。

特點

只能從棧頂添加元素或者刪除元素

后進先出的數據結構，Last In First Out（LIFO）

為了大家更好的形象了解我們通過示意圖來看一下棧的入棧和出棧操作

入棧操作示意圖

出棧操作示意圖（后進的元素先出）

棧的基本操作

向棧中添加一個元素（入棧）

void push(E e)

從棧中刪除一個元素（出棧）

E pop()

查看棧頂元素

E peek()

查看棧中元素個數

int getSize()

判斷棧是否為空

boolean isEmpty()

實現棧的方式，實際上底層有多種實現方式，比如：動態數組等，這里我們使用Java語言本身為我們提供的集合LinkedList

接口定義：Stack

public interface Stack {

    /**
     * 向棧中添加元素
     *
     * @param e
     */
    void push(E e);

    /**
     * 從棧中刪除元素
     */
    void pop();

    /**
     * 獲取棧頂元素
     *
     * @return
     */
    E peek();

    /**
     * 獲取棧中元素個數
     *
     * @return
     */
    int getSize();

    /**
     * 判斷棧中是否為空
     *
     * @return
     */
    boolean isEmpty();

}

LinkedListStack 類實現接口Stack

public class LinkedListStack implements Stack {
    /**
     * 存放棧元素
     */
    LinkedList list;

    /**
     * 構造棧結構
     */
    public LinkedListStack() {
        list = new LinkedList<>();
    }

    @Override
    public void push(E e) {
        list.addLast(e);
    }

    @Override
    public void pop() {
        list.removeLast();
    }

    @Override
    public E peek() {
        return list.getLast();
    }

    @Override
    public int getSize() {
        return list.size();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public String toString() {
        return "LinkedListStack{" +
                "list=" + list +
                "}";
    }
}

測試類：LinkedListStackTest

@Test
public void testLinkedListStack() {
    // 棧
    Stack stack = new LinkedListStack<>();
    // 準備入棧元素
    List prepareElements = Arrays.asList("A", "B", "C", "D", "E");
    // 入棧
    prepareElements.forEach(x -> {
        stack.push(x);
        System.out.println("入棧操作：" + stack);
    });
    // 出棧
    stack.pop();
    System.out.println("出棧操作：" + stack);
    // 獲取棧頂元素
    String peekElement = stack.peek();
    System.out.println("棧頂元素：" + peekElement);
    // 獲取棧中元素的個數
    int stackSize = stack.getSize();
    System.out.println("棧中元素個數：" + stackSize);
}

運行結果

入棧操作：LinkedListStack{list=[A]}
入棧操作：LinkedListStack{list=[A, B]}
入棧操作：LinkedListStack{list=[A, B, C]}
入棧操作：LinkedListStack{list=[A, B, C, D]}
入棧操作：LinkedListStack{list=[A, B, C, D, E]}
出棧操作：LinkedListStack{list=[A, B, C, D]}
棧頂元素：D
棧中元素個數：4

棧的應用

虛擬機棧的入棧和出棧操作

在Java虛擬機運行時數據區有一塊被稱之為：虛擬機棧，它是線程私有的，聲明周期與線程相同。

我們編寫的每個Java方法，每個方法都會在執行的時候同時都會創建一個棧幀（Stack Frame）用于存儲局部變量表、操作數棧、動態鏈接、方法出口等信息。每一個方法從調用直至執行完成的過程，就對應這一個棧幀在虛擬機棧中入棧到出棧的過程。

現在我們假設有A、B、C三個方法，在A方法中調用B方法（A->B），在B方法中調用C方法（B->C），C方法執行本方法業務邏輯。

當程序執行到A()方法的中的第二行時，此時程序會中斷A()方法并開始調用B()方法，然后會在虛擬機棧中記錄調用B()方法的棧幀，我這里暫且稱之為A2（實際存儲的并不是O(∩_∩)O哈！）示意圖如下：

同理，當程序執行到B()方法中第二行時，此時程序也會中斷B()方法開始調用C()方法，然后同樣地會在虛擬機棧中生成調用C()方法的棧幀并記錄，我這里暫且稱之為B2，示意圖如下：

當程序開始執行到C()方法時，直到執行完C()方法時，這時候，程序該如何執行呢？

此時就要查看一下虛擬機棧了，發現虛擬機棧，棧中棧頂的元素是B2，我們的程序就知道了，它是執行到B()方法的B2位置就中斷了，去執行C()方法了；現在C()方法執行完成之后，它就可以跳回到B2的位置繼續執行了，當B()方法執行完之后，虛擬機棧中的B2棧幀也就可以出棧了，依次類推....

如果一個方法，使用遞歸調用，若遞歸臨界點判斷有誤，則方法就會一直的被進行入棧操作，如果超過虛擬機棧的默認容量大小，則會出現我們常見的 StackOverflowError 異常

完整版代碼GitHub倉庫地址：Java版數據結構-棧歡迎大家【關注】和【Star】

本次我們完成的是基于Java自身自帶的集合LinkedList來實現棧，有興趣的童鞋，可以使用動態數組方式來實現；接下來，筆者還會一一的實現其它常見的數組結構。

靜態數組

動態數組

棧

隊列

鏈表

循環鏈表

二分搜索樹

優先隊列

堆

線段樹

字典樹

AVL

紅黑樹

哈希表

....

持續更新中，歡迎大家關注公眾號：小白程序之路（whiteontheroad），第一時間獲取最新信息！！！

筆者博客地址：http:www.gulj.cn

云服務器 GPU云服務器 c語言版數據結構棧設計棧java java單調棧 java線程棧

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73943.html

Java版-數據結構-隊列（數組隊列）

摘要：隊列的操作方式和棧類似，唯一的區別在于隊列只允許新數據在后端進行添加。前言看過筆者前兩篇介紹的Java版數據結構數組和棧的盆友，都給予了筆者一致的好評，在這里筆者感謝大家的認可！！！由于本章介紹的數據結構是隊列，在隊列的實現上會基于前面寫的動態數組來實現，而隊列又和棧不論是從特點上和操作上都有類似之處，所以在這里對這兩種數據結構不了解的朋友，可以去看一下筆者前兩篇文章介紹的數據結...

khs1994 2019-08-16 16:10 評論0 收藏0
屌炸天，Oracle 發布了一個全棧虛擬機 GraalVM，支持 Python！

摘要：前陣子，發布了一個黑科技，號稱是一個全新的通用全棧虛擬機，并具有高性能跨語言交互等逆天特性，真有這么神奇簡介是一個跨語言的通用虛擬機，不僅支持了等基于的語言，以及等基于的語言，還支持其他像和語言等。原生鏡像加速來看這段代碼，同樣來自官網。前陣子，Oracle 發布了一個黑科技 GraalVM，號稱是一個全新的通用全棧虛擬機，并具有高性能、跨語言交互等逆天特性，真有這么神奇？ Graa...

hiYoHoo 2019-08-19 10:49 評論0 收藏0
數據結構之棧（java版）

摘要：本文力求簡潔，只包含基礎的棧功能，不想將大片的代碼展示出來，讓讀者興趣索然，閱讀起來也十分費力，如有需要可以自行添加相關功能比如包中的類包含的，等等函數能力有限，有誤之處還請不吝賜教定義內部類用于存儲棧元素指向下一個棧元素的泛型元素方法方法本文力求簡潔，只包含基礎的棧功能，不想將大片的代碼展示出來，讓讀者興趣索然，閱讀起來也十分費力，如有需要可以自行添加相關功能比如java.util...

hizengzeng 2019-08-14 18:03 評論0 收藏0
《JavaScript快速全棧開發》作者Azat Mardanov：現在是擁抱Node技術棧的最佳時

摘要：長期以來，他都是和等機構的講師，其技術課程獲得一致好評。但是，如果讓我預測的話，我認為未來是很光明的，而現在就是擁抱技術棧的最佳時機。所以在瀏覽器和服務器之間代碼不需要上下文切換。如果沒有上下文切換，那么生產力也會更高。非商業轉載請注明作譯者、出處，并保留本文的原始鏈接：http://www.ituring.com.cn/article/195742 Azat Mardan...

Rango 2019-08-21 10:28 評論0 收藏0