歡迎光臨Java中的客“棧”

就目前而言，相信大家對數組、鏈表還有棧都基本已經有了一些了解，本篇文章將以棧為主體，探究棧和數組，棧和鏈表之間的一些聯系。

當然在開始對棧的學習之前，我們先回顧有關數組、鏈表的基礎知識點。

學習代碼就是一個不斷遺忘且鞏固的過程，如何讓敲出來的代碼在心中印象更為深刻呢？不妨為這些有規律的字母的排列組合賦予一些當下事物的靈動性。

在這里我不得不提到當下的熱梗：諸如來自歌手2024中的“五旬老太守國門”、“葉赫那拉氏大戰八國聯軍”等等，既然咱們英子在這期舞臺上是那么的孤單無助，在本篇代碼里我將在循環取出棧中元素時，為英子來點助力，畢竟，57歲正是拼搏的年齡，咱們英子不能輸，一個不夠就來倆，兩個不夠我就來N個，真舞臺咱也上不去，那就只能在代碼里為我們的歌手們吶喊助威了！（見三）

天天抖手，精神抖擻！

一、鏈表與數組（Array and LinkedList）

1.關于數組 Array

2.關于鏈表 LinkedList

二、棧（Stack）

1.泛型簡介

2.什么是棧

3.數組與棧

1）棧的存與取

2）數組和棧刪除之間的區別

3）代碼實現

4.鏈表與棧

1）棧中數據的插入與刪除

2）基本代碼實現

3）頭插法與尾插法

三、整體代碼

一、鏈表與數組（Array and LinkedList）

1.關于數組 Array

數組在內存中是一段連續的空間，每段的編號都是從0開始的，依次遞增，也稱為數組的下標。

數組可以通過索引（下標）訪問其任意位置的元素。

數組不能夠自動擴容且長度固定不可變。

除了掌握數組的創建，還需要會使用的就是數組的存和取。

int[] array1 = new int[10];//動態初始化
int[] array2 = {1,2,3,4,5};//靜態初始化

在整數型數組的動態初始化里，每個元素的初始值都為0，不同類型的數組初始值不同。

public class Test {//存public static void main(String[] args) {int[] array = new int[5];for (int i = 0; i < array.length; i++) {array[i] = i * 2 + 1;}for (int i = 0; i < array.length; i++) {System.out.println("array[" + i + "] = " + array[i]);}}
}

public class Test {//取public static void main(String[] args) {int[] arr1 = {1,2,3,4,5};for (int i = 0; i < arr1.length; i++) {System.out.print(arr1[i]+" ");}System.out.print("\n");int[] arr2 = new int[5];for (int j  = 0;j < arr2.length; j++){int value = arr2[j];System.out.print(value+" ");}}}

運行結果：

1 2 3 4 5?
0 0 0 0 0?

2.關于鏈表 LinkedList

這里主要回顧單向鏈表。鏈表長度可變，且可以實現自動擴容，但不能通過下標進行訪問。

鏈表使用節點對象儲存數據，節點之間相互存儲地址建立連接。

鏈表主要幾個概念：頭節點和尾結點。

頭節點（head）：鏈表的第一個節點稱為頭節點，通常用來表示整個鏈表的起始位置。

尾節點（last）：鏈表的最后一個節點稱為尾節點，其指針通常指向 null，表示鏈表的結束。

但與數組不同，鏈表中的元素在內存中不是連續存儲的，而是通過指針（引用）相互連接起來。??

圖示的為鏈表的一個節點node，value是這個節點的所存儲的數據值，next為下一節點的地址。

二、棧（Stack）

1.泛型簡介

為什么叫泛型？一般提到關于“泛”的都是聯想到廣泛、寬泛、空泛、泛泛之交等詞語、所以不難得出泛具有適用性廣、通用性強等特征。所以在Java中的泛型一般用在尚不確定的數據類型中，可以暫替多種數據類型，以下段代碼為例。

public class pandora_box<T> {private T value;public void setValue(T value){this.value=value;System.out.println(value);}public T getValue(){System.out.println(value);return value;}public static void main(String[] args) {pandora_box<String> box1 = new pandora_box<>();box1.getValue();box1.setValue("潘多拉魔盒");pandora_box<Integer> box2 = new pandora_box<>();box2.setValue(111);box2.getValue();}
}

輸出結果：

null
潘多拉魔盒
111
111

2.什么是棧

?棧是一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。?

底層可以使用數組或鏈表進行實現。

采取先進后出（LIFO：last in first of）原則: 即先存入的數據,最后才能取出

類比：放羽毛球的盒子，最先放進去的是最后一個拿出來的，或一個單向閉口的管道（最先存入的為棧底、最后一個存入的為棧頂）。

總結：棧的操作只涉及棧頂元素，而不會涉及棧底或中間的元素。

3.數組與棧

數組可以理解成為一種固定長度的棧。

1）棧的存與取

存：按照下標正常存入

取：從最后的元素開始依次向前

2）數組和棧刪除之間的區別

數組：找到對應的下標，將改下標后一位置的元素逐一向前挪一個

棧：倒著一一取出直至找到需要刪除的數據

對于插入數據數據呢？會很麻煩，一旦越過最后一個要取前面的步驟就會很繁瑣。

3）代碼實現

Object[ ]是一個數組，其中每個元素的類型都是Object。在 Java 中，Object?是所有類的祖先，因此 Object[ ]?數組可以存儲任何類型的對象，包括基本數據類型的包裝類對象和用戶自定義的類對象。

由于Object是所有類的直接或間接父類，因此 Object[ ]?數組可以存儲任意類型的對象，例如String、Integer、Double?等。當你不確定數組中需要存儲哪種類型的對象時，可以使用? ? ? ? ?Object[ ]?數組作為一種通用的容器。（類比泛型的思想）

public class ArrayStack<E> {Object[] stackArr = new Object[10];int size=0;public void add(E e){//定義了一個公有的方法 add，用于向棧中添加元素//該方法使用泛型類型 T 作為參數類型，表示可以接受任意類型的對象(即傳入)if (stackArr.length==size){System.out.println("小二提示：您的客棧已滿！");return;}stackArr[size++]=e; //這行代碼相當于stackArr[size]=e;size++;//將傳入的元素 t 添加到棧頂（數組中的下一個空位置），并將 size 自增//這里利用 size 變量來記錄當前棧中元素的個數，并在添加元素后更新 size}public E get(){//當你從棧中取出元素時，根據棧的特性，應當從棧頂開始取出元素!!!E element =(E)stackArr[size-1];//具體理解見wordstackArr[size-1]=null;size--;return element;}public String toString() {StringBuilder sb = new StringBuilder();sb.append("stackArr:{ ");for (int i = 0; i < size; i++) {sb.append(stackArr[i]).append(" "); // 將每個元素的值拼接到 str 中}sb.append("}");return sb.toString();}public static void main(String[] args) {ArrayStack<Object> arrStack = new ArrayStack<>();for (int i = 0; i < 10; i++){arrStack.add(i);}System.out.println("存-"+arrStack.toString());for (int i = 0; i < 10; i++){System.out.print("取-"+arrStack.get()+" ");}}
}

輸出結果：

存-stackArr:{ 0 1 2 3 4 5 6 7 8 9 }
取-9 取-8 取-7 取-6 取-5 取-4 取-3 取-2 取-1 取-0?

4.鏈表與棧

鏈表可以理解為實現一種長度不固定的棧。

1）棧中數據的插入與刪除

由于棧只能從棧頂開始對其中的數據進行取出，所以我們只能倒著一一取出直至找到需要刪除的數據，那么對于插入數據數據呢？一樣也很麻煩，一旦越過最后一個數據要取出前面的就會很麻煩。

2）基本代碼實現

鏈表通過將數據存入節點對象中，而節點類的構造一般包括屬性、數據變量、下一個節點對象變量（其中存儲的為地址）。

添加或查找數據都可以通過一個頭節點依次向下找。

class Node<E>{E value;//數據變量Node<E> next;public Node(E value){this.value=value;}public Node<E> setNext(){return next;}public void getNext(){this.next=next;}}public class myLinkedList<E> {Node<E> head;int size;public void add(E e){Node<E> node = new Node<>(e);//如果頭節點為空if(head==null){head=node;size++;return;}else{//遍歷鏈表找到最后一個節點，將新節點掛在最后一個節點上//利用遞歸的思想Node<E> current = head;while (current.next != null){current=current.next;}current.next=node;size++;}}public static void main(String[] args) {myLinkedList<Integer> myll = new myLinkedList<>();long startTime = System.currentTimeMillis();for (int i = 0; i<100000;i++){myll.add(i);}long endTime = System.currentTimeMillis();System.out.println("人工鏈表用時："+(endTime-startTime)+"ms");LinkedList<Integer> linkedList = new LinkedList<>();long startTime1 = System.currentTimeMillis();for (int i = 0; i<100000;i++){linkedList.add(i);}long endTime1 = System.currentTimeMillis();System.out.println("系統鏈表用時："+(endTime1-startTime1)+"ms");}}

運行結果：

人工鏈表用時：5728ms

系統鏈表用時：4ms

思考：為何自制的鏈表與java系統自帶的耗時差異如此之大？

可能的原因：在遍歷上耗時過多。

3）頭插法與尾插法

So如果我們不是通過找到頭節點后再遍歷循環掛到末尾上，直接讓新節點成為頭節點是不是就可以略去遍歷循環的時間了呢？（頭插法）

public void addFirst(E e){Node<E> node = new Node<>(e);if(head==null){head=node;size++;return;}else{node.next=head;//此時假設新節點node已經成為頭節點，則當時的頭節點的位置處于新節點的下一個head=node;//原本頭節點的位置size++;}
}

運行結果

人工鏈表用時：98ms

系統鏈表用時：33ms

下面是尾插法的代碼實現部分。

public void addLast(E e) {Node<E> node = new Node<>(e);if (head == null) {head = node;last = node;//此時頭結點也是尾結點size++;return;} else {last.next = node;//此時假設新節點node已經成為頭節點，則當時的頭節點的位置處于新節點的下一個last = node;//原本頭節點的位置size++;}
}

運行結果：

人工鏈表用時：94ms

系統鏈表用時：96ms

不難看出：尾插法的運行速度甚至比頭插法還有java自帶的耗時更少。

三、整體代碼（葉赫那拉大戰八國聯軍）

class Node<E>{E value;//數據變量Node<E> next;public Node(E value){this.value=value;}public void setNext(Node<E> next){this.next=next;}public Node<E> getNext(){return next;}}public class myLinkedList<E> {Node<E> head;Node<E> last;int size;public void addFirst(E e){Node<E> node = new Node<>(e);if(head==null){head=node;size++;return;}else{node.next=head;//此時假設新節點node已經成為頭節點，則當時的頭節點的位置處于新節點的下一個head=node;//原本頭節點的位置size++;}}public void addLast(E e) {Node<E> node = new Node<>(e);if (head == null) {head = node;last = node;//此時頭結點也是尾結點size++;return;} else {last.next = node;//此時假設新節點node已經成為頭節點，則當時的頭節點的位置處于新節點的下一個last = node;//原本頭節點的位置size++;}}public void add(E e){Node<E> node = new Node<>(e);//如果頭節點為空if(head==null){head=node;size++;return;}else{//遍歷鏈表找到最后一個節點，將新節點掛在最后一個節點上//利用遞歸的思想Node<E> current = head;while (current.next != null){current=current.next;}current.next=node;size++;}}@Overridepublic String toString(){String str = "{";Node<E> current = head;while (current.next!=null){str+=current.value+",";current=current.next;}str+=current.value+"}";return str;}public E get(int point){if(point<0 || point>=size){System.out.println("不好意思這位大人您越界了");return null;}Node<E> current = head;for (int i =0; i<point;i++){current=current.next;}return current.value;}public static void main(String[] args) {myLinkedList<String> stringList = new myLinkedList<>();for (int i=0;i<6;i++){stringList.addLast("葉赫那拉"+i);}for (int i=0;i<2;i++){stringList.addFirst("八國聯軍"+i);}//注意順序不能調換！！！System.out.println(stringList.toString());System.out.println(stringList.get(3));}public static void test(){myLinkedList<Integer> myll = new myLinkedList<>();long startTime = System.currentTimeMillis();for (int i = 0; i<1000000;i++){//myll.add(i);myll.addFirst(i);//myll.addLast(i);}long endTime = System.currentTimeMillis();System.out.println("人工鏈表用時："+(endTime-startTime)+"ms");LinkedList<Integer> linkedList = new LinkedList<>();long startTime1 = System.currentTimeMillis();for (int i = 0; i<1000000;i++){linkedList.add(i);}long endTime1 = System.currentTimeMillis();System.out.println("系統鏈表用時："+(endTime1-startTime1)+"ms");}}

運行結果：

{八國聯軍1,八國聯軍0,葉赫那拉0,葉赫那拉1,葉赫那拉2,葉赫那拉3,葉赫那拉4,葉赫那拉5}
葉赫那拉1

寫到最后發現這篇的結構與內容有點雜亂，可能是因為有段時間沒有寫博客的原因，讓我逐漸調整調整，爭取下一篇是那種短小精悍的小短篇，后續關于鏈表、數組、棧的內容還會出現，這次就當做一個初步了解啦。