StackQueue+泛型簡單理解

🍁?個人主頁：愛編程的Tom
💫 本篇博文收錄專欄：Java專欄
👉?目前其它專欄：c系列小游戲?????c語言系列--萬物的開始_??? ? ? ? ? ? ?
🎉 歡迎 👍點贊?評論?收藏💖三連支持一下博主🤞
🧨現在的沉淀就是對未來的鋪墊🎨?

前言

棧（Stack）

棧的定義

棧的使用?

棧的模擬實現?

棧的應用場景

改變元素的序列 ?

將遞歸轉化為循環?

隊列(Queue)?

隊列的定義?

隊列的使用?

隊列模擬實現?

循環隊列?

雙端隊列 (Deque)?

泛型

前言

本篇文章將帶你深入了解棧和隊列的底層知識和基礎架構，學會使用對數據的組織和運用！

棧（Stack）

棧的定義

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

進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。

棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則。 ?

壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。

出棧：棧的刪除操作叫做出棧。出數據在棧頂。

下面結合圖片給出具體的理解：

棧的使用?

下面給出代碼的運用加以理解：?

public static void main(String[] args) {Stack<Integer> s = new Stack();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size()); ? // 獲取棧中有效元素個數---> 4System.out.println(s.peek()); ? // 獲取棧頂元素---> 4s.pop(); ? // 4出棧，棧中剩余1 ? 2 ? 3，棧頂元素為3System.out.println(s.pop()); ? // 3出棧，棧中剩余1 2 ? 棧頂元素為3if(s.empty()){System.out.println("棧空");}else{System.out.println(s.size());}
}

棧的模擬實現?

從上圖中可以看到，Stack繼承了Vector，Vector和ArrayList類似，都是動態的順序表，不同的是Vector是線程安全的。?

Stack的具體模擬實現如下：?

public class MyStack {public int[] elem;public int usedSize;public static final int DEFAULT_CAPACITY = 10;public MyStack() {this.elem = new int[DEFAULT_CAPACITY];}//壓棧public void push(int val) {if (isFull()) {this.elem = Arrays.copyOf(elem,2*elem.length);}elem[usedSize++] = val;}public boolean isFull() {return usedSize == elem.length;}//出棧public int pop() {if (isEmpty()) {throw new EmptyStackException("棧為空！！！！");}int oldVal = elem[usedSize-1];usedSize--;//elem[usedSize] = null;return oldVal;}public boolean isEmpty() {return usedSize == 0;}public int peek() {if(isEmpty()) {throw new EmptyStackException("棧為空！！！！！");}return elem[usedSize - 1];}
}

棧的應用場景

改變元素的序列 ?

如上圖兩題在棧的理解上，解決可得選項為 C 和 B.

將遞歸轉化為循環?

這里給大家提供一個例子：逆序打印鏈表?

// 遞歸方式
void printList(Node head){if(null != head){printList(head.next);System.out.print(head.val + " ");}
}// 循環方式
void printList(Node head){if(null == head){return;}Stack<Node> s = new Stack<>();// 將鏈表中的結點保存在棧中Node cur = head;while(null != cur){s.push(cur);cur = cur.next;}
// 將棧中的元素出棧while(!s.empty()){System.out.print(s.pop().val + " ");}
}

這里還有一些練習的題目：如果想更深入了解棧的相關機理，可以嘗試做一做

1.括號匹配

2.逆波蘭表達式?

3.出棧入棧次序匹配?

4.最小棧?

這里提出一個思考題：棧、虛擬機棧、棧幀有什么區別呢？

棧：棧是一種數據結構，具有后進先出（LIFO）的特性，用于存儲函數調用、局部變量等數據。在計算機中，棧通常是指操作系統管理的內存區域，用于存儲函數調用時的參數、返回地址、局部變量等。

虛擬機棧：虛擬機棧是指在Java虛擬機中用來執行Java方法的內存區域，用于存儲方法的局部變量、操作數棧、動態鏈接、方法出口等信息。虛擬機棧與操作系統的棧類似，但是在Java虛擬機中，每個線程都有自己的虛擬機棧，用于執行方法時的數據存儲。

棧幀：棧幀是指在方法調用時壓入虛擬機棧中的數據結構，用于存儲方法的局部變量、操作數棧、動態鏈接、方法出口等信息。每個方法調用都會創建一個對應的棧幀，用于存儲該方法執行時需要的數據。棧幀是虛擬機棧中的一個重要組成部分，用于支持方法的執行和調用。

隊列(Queue)?

隊列的定義?

隊列：只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表，

隊列具有先進先出FIFO(First In First Out)

入隊列：進行插入操作的一端稱為隊尾（Tail/Rear）

出隊列：進行刪除操作的一端稱為隊頭（Head/Front） ?

隊列的使用?

在Java中，Queue是個接口，底層是通過鏈表實現的。 ?

注意：

Queue是個接口，在實例化時必須實例化LinkedList的對象(因為LinkedList實現了Queue接口)

public static void main(String[] args) {Queue<Integer> q = new LinkedList<>();q.o?er(1);q.o?er(2);q.o?er(3);q.o?er(4);q.o?er(5); ? ? ? ? ? ? ? ? ?// 從隊尾入隊列System.out.println(q.size());System.out.println(q.peek()); ?// 獲取隊頭元素q.poll();System.out.println(q.poll()); ?// 從隊頭出隊列，并將刪除的元素返回if(q.isEmpty()){System.out.println("隊列空");}else{System.out.println(q.size());}
}

隊列模擬實現?

隊列中既然可以存儲元素，那底層肯定要有能夠保存元素的空間

常見的空間類型有兩種：順序結構和鏈式結構。

思考題：隊列的實現使用順序結構還是鏈式結構好？?

順序結構：

優點：順序結構的隊列使用數組實現，插入和刪除操作的時間復雜度為O(1)，在空間上比較節省。

缺點：在插入和刪除元素時，需要移動其他元素，可能會導致性能下降。而且順序結構的隊列有容量限制，當隊列滿時需要進行擴容操作。

鏈式結構：

優點：鏈式結構的隊列使用鏈表實現，插入和刪除操作的時間復雜度為O(1)，不需要移動其他元素。而且鏈式結構的隊列沒有容量限制，可以動態增加或減少元素。

缺點：鏈式結構的隊列在內存占用上比順序結構更大，因為每個節點都需要額外的指針指向下一個節點。

總結：如果對內存占用要求比較高，且隊列的大小是固定的，可以選擇順序結構實現隊列；如果對插入和刪除操作的性能要求比較高，且隊列的大小是動態變化的，可以選擇鏈式結構實現隊列。

隊列實現場景圖：

下面給出模擬實現的代碼（僅供參考）：?

public class Queue {// 雙向鏈表節點public static class ListNode{ListNode next;ListNode prev;int value;ListNode(int value){this.value = value;}}ListNode ?rst; ? // 隊頭ListNode last; ? ?// 隊尾int size = 0;// 入隊列---向雙向鏈表位置插入新節點public void o?er(int e){ListNode newNode = new ListNode(e);if(?rst == null){?rst = newNode;// last = newNode;}else{last.next = newNode;newNode.prev = last;// last = newNode;}last = newNode;size++;}// 出隊列---將雙向鏈表第一個節點刪除掉public int poll(){// 1. 隊列為空// 2. 隊列中只有一個元素----鏈表中只有一個節點---直接刪除// 3. 隊列中有多個元素---鏈表中有多個節點----將第一個節點刪除int value = 0;if(?rst == null){return null;}else if(?rst == last){last = null;?rst = null;}else{value = ?rst.value;?rst = ?rst.next;?rst.prev.next = null;?rst.prev = null;}--size;return value;}// 獲取隊頭元素---獲取鏈表中第一個節點的值域public int peek(){if(?rst == null){return null;}return ?rst.value;}public int size() {return size;}public boolean isEmpty(){return ?rst == null;}
}

循環隊列?

數組下標循環的小技巧

1. 下標最后再往后(o?set 小于 array.length): index = (index + o?set) % array.length ?

2. 下標最前再往前(o?set 小于 array.length): index = (index + array.length - o?set) % array.length?

如何區分空與滿?

1. 通過添加 size 屬性記錄?

2. 保留一個位置

3. 使用標記 ?

感興趣的可以試試這道相關題目：設計循環隊列?

雙端隊列 (Deque)?

雙端隊列（deque）是指允許兩端都可以進行入隊和出隊操作的隊列，deque 是 “double ended queue” 的簡稱。那就說明元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊。 ?

Deque是一個接口，使用時必須創建LinkedList的對象。?

在實際工程中，使用Deque接口是比較多的，棧和隊列均可以使用該接口。

這里給出兩種實現方式：

Deque stack = new ArrayDeque<>();//雙端隊列的線性實現

Deque queue = new LinkedList<>();//雙端隊列的鏈式實現?

泛型

泛型：就是適用于許多許多類型。從代碼上講，就是對類型實現了參數化。?

主要目的：就是指定當前的容器，要持有什么類型的對象。讓編譯器去做檢查。?

在編譯的過程當中，將所有的T替換為Object這種機制，這種機制稱為：擦除機制。 ?

class MyArray<T> {public T[] array = (T[])new Object[10];//1public T getPos(int pos) {return this.array[pos];}public void setVal(int pos,T val) {this.array[pos] = val;}
}
public class TestDemo {public static void main(String[] args) {MyArray<Integer> myArray = new MyArray<>();//2myArray.setVal(0,10);myArray.setVal(1,12);int ret = myArray.getPos(1);//3System.out.println(ret);myArray.setVal(2,"bit");//4}
}

對上述代碼進行一個說明：

1. 類名后的代表占位符，表示當前類是一個泛型類

了解：【規范】類型形參一般使用一個大寫字母表示，

常用的名稱有：

E 表示 Element

K 表示 Key

V 表示 Value

N 表示 Number

T 表示 Type

S, U, V 等等 - 第二、第三、第四個類型

2. 注釋1處，不能new泛型類型的數組 ,說明：
T[] ts = new T[5];//是不對的
3. 注釋2處，類型后加入指定當前類型

4. 注釋3處，不需要進行強制類型轉換

5. 注釋4處，代碼編譯報錯，此時因為在注釋2處指定類當前的類型，此時在注釋4處，編譯器會在存放元素的時候幫助我們進行類型檢查。

此處只對泛型做一個簡單的介紹，不作過多解釋，理解就好......??