1.什么是堆疊？

假如有一天你下課去小店，買了一條曼妥思準備回去上課的時候偷偷吃，你的同桌看見你的嘴巴一直在嚼，這時你小心翼翼的拿出一顆遞給他，這時你就完成了一組出堆疊功能，如下圖，右邊就像你的曼妥思，你拿給同桌的肯定是從上往下的第一顆，也就是最上面的這顆糖，如果你下課還要給其他同學那你肯定是順著往下繼續給直到吃完為止，

這種只能從一端進行元素的添加和洗掉的操作受限的線性表，我們就稱之為堆疊，當然這只是簡易的單純從資料結構的說法，我們的計算機記憶體中還有堆疊區，如果你想了解更多當然可以去自己了解，這里我只以最快的方式告訴你堆疊的邏輯結構

PS：堆疊的實作可以通過順序表或鏈表實作，剛開始接觸資料結構的同學不要思維定式，看著圖里好像元素都靠在一起就像陣列就得用順序表，堆疊只要求我們只能在一端進行操作，保存資料的方式無論你選順序表還是鏈表都是可以的，這里我更推薦使用鏈表實作，因為能用鏈表實作肯定也能用順序表實作，我也以鏈表來演示，對于順序表和鏈表不熟的同學推薦看看我的前三篇文章

1、java資料結構---順序表

2、java資料結構---單鏈表

3、 java資料結構---雙向鏈表

2.堆疊的基本功能和結構

public class Stack<T> implements Iterable {
    //記錄首節點
    private Node head;
    //記錄堆疊中元素個數
    private int N;
    private class Node{
        public T item;
        private Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    public Stack(){
        this.head=new Node(null,null);
        this.N=0;
    }

因為是以鏈表存盤，同樣需要一個內部類Node表示結點，堆疊成員屬性有Node頭結點head以及一個int型別變數N計算存盤元素個數，構造方法中，new出一個stack（堆疊）時，需要初始化一個值為空（頭結點不存盤元素），next也為空，因為我們此時堆疊還是空的，千萬別寫成this.head=null，這是完全不同的，這樣寫代表根本沒有頭結點，

ps：在這我們要注意，因為堆疊的操作都是在一端，所以為了我們操作方便，我們的頭結點是在進行操作的這一端，而且堆疊頂的元素不是頭結點，而是我們頭結點的next，有人說這樣頭結點不是好像一直隨著壓堆疊出堆疊的操作一直動嗎？我把頭結點放堆疊底那它不是不用動更好嗎，但是我們資料結構追求的是效率呀，如果你的頭結點是在堆疊低，那每次對堆疊頂進行操作，你都要通過遍歷去找到堆疊頂的結點，這耗費的時間是巨大的，

public boolean isEmpty()	判斷堆疊是否為空
public int getLength()	獲取堆疊中元素的個數
public void push(T t)	壓堆疊（向堆疊頂放入元素）
public T pop()	出堆疊（拿出堆疊頂元素，并得到它的值）
public T getHeadNext()	獲取堆疊頂元素（未拿出）
public boolean contains(T t)	判斷堆疊中是否包含該元素

3.堆疊的基本功能詳細代碼實作

1. 判斷堆疊是否為空

public boolean isEmpty(){
        return N==0;
    }

決議：因為我們有N統計堆疊中元素的個數，所以判斷是否為空時，我們只需要回傳N是否等于0即可，

2.獲取堆疊中元素的個數

 public int getLength(){
        return N;
    }

決議：同樣是設計到元素的個數，需要獲得堆疊中元素的個數，我們只需要回傳N即可，感覺到這個N的好處了嗎？

3.壓堆疊（向堆疊頂放入元素）

/壓堆疊
    public void push(T t){
        if(N==0){
            Node newNode = new Node(t, null);
            head.next=newNode;
        }else {
            //獲取堆疊頂元素
            Node a = head.next;
            //創建新結點
            Node newNode = new Node(t, a);
            head.next = newNode;
        }
        N++;
    }

決議：首先對于壓堆疊操作，我們需要有兩種情況區分，第一種情況此時堆疊中是否有元素，如果此時N==0，代表無元素，那我們需要new出一個新結點，保存T的值，然后將其放在head的next，因為是第一個進入的所以為堆疊頂元素，第二種情況此時堆疊中有元素，即head的next是存在結點的，因為壓堆疊是在堆疊頂加入元素，這就需要我們在頭結點和原堆疊頂元素之間插入新元素，所以我們先獲取原堆疊頂元素a，new出的新結點保存T的值，同時next指向原堆疊頂元素，這時再讓頭結點不指向a轉而指向新結點newNode，這樣我們就成功壓堆疊，最后不要忘了無論第一種還是第二種情況我們都需要讓N加1，

4.出堆疊（拿出堆疊頂元素，并得到它的值）

 //出堆疊
    public T pop(){
        if(head.next==null){
            return null;
        }
        Node a=head.next;
        Node b=head.next.next;
        head.next=b;
        N--;
        return a.item;
    }

決議：同樣需要進行對堆疊是否為空的判斷，如果為空，我們回傳null就好，如果不為空，我們首先獲取堆疊頂結點并命名為a，再獲取堆疊頂第二結點b，因為如果a出堆疊以后，b就變為堆疊頂元素了，我們直接讓頭結點head不指向a轉而轉向b即可，然后讓N--，最后別忘記回傳a.item，回傳原堆疊頂結點的值，

ps:不難發現，出堆疊和壓堆疊都與鏈表的插入和洗掉操作幾乎一樣，大家可以去對比一下，熟悉鏈表操作，對我們后續的各種資料結構的學習都是必要的

5.獲取堆疊頂元素（未拿出）

//獲取堆疊頂元素
    public T getHeadNext() {
        return head.next.item;
    }

決議：因為只需要得到堆疊頂元素不需要拿出，所以直接回傳即可，注意不是回傳head.next，我們需要的是值而不是結點，

6.判斷堆疊中是否包含該元素

//判斷堆疊中是否包含該元素
    public boolean contains(T t){
        Node a=head;
        while (a.next!=null){
            a=a.next;
            if(a.item==t) return true;
        }
        return false;
    }

決議：因為堆疊是只能在一端進行操作的操作受限的線性表，所以想實作這個功能，我們只能通過回圈遍歷判斷是否有需要找的元素，有則回傳true，回圈遍歷結束還沒找到，說明堆疊中沒有，回傳false即可

總結：堆疊的邏輯結構比較簡單，實作也容易，如果成功用鏈表實作了，那么也請用順序表去實作堆疊結構，堆疊用的雖然少，但也是我們必須掌握的基礎資料結構，

水平尚欠，有錯誤請指出，多謝

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/337746.html

標籤：其他

上一篇：MySQL面試奪命連環24問

下一篇：集合全套以及知識點整合

Java資料結構----------------堆疊（性質、介紹、圖解代碼）