一、棧 概念與特性

一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數據插入和刪除操作的一端稱為棧
頂，另一端稱為棧底。棧中的數據元素遵守后進先出 LIFO（Last In First Out）的原則。

二、Stack 集合類及模擬實現

1、Java集合中的 Stack

在Java集合中 Stack 集合類可以表示棧，Stack繼承了Vector，Vector和ArrayList類似，都是動態的順序表，因此Stack 底層維護的也是一個動態順序表。

我們可以先看一下Stack中給出的常用方法：

構造方法

方法	解釋
Stack()	構造一個空的棧

常用方法

方法	功能
E push(E e)	將元素 e 入棧，并返回 e
E pop()	將棧頂元素出棧并返回
E peek()	獲取棧頂元素
int size()	獲取棧中有效元素個數
boolean empty()	檢測棧是否為空

2、Stack 模擬實現

有了順序表和鏈表的基礎，棧的實現就非常的簡單了，下面就直接給出順序棧的實現代碼，大家可以參照注釋進行理解：

public class MyStack {// 數組public int[] elem;// 棧頂public int top;// 構造方法（初始化順序棧）public MyStack() {elem = new int[5];}//1.壓棧：E push(E e) //檢測容量private boolean isFull() {return top == elem.length;}public int push(int e) {if (isFull()) {// 如果棧滿就擴容elem = Arrays.copyOf(elem,2*elem.length);}elem[top++]=e;return e;}//2.出棧：E pop() public int pop() {// 如果棧空，拋異常（這里可以自定義實現一個異常類）if (empty()) {throw new EmptyException("空棧!");}// 正常出棧return elem[--top];}//3.獲取棧頂元素：E peek() public int peek() {return elem[top-1];}//4.獲取棧中有效元素個數：int size() public int size() {return top;}//5.檢測棧是否為空：boolean empty() public boolean empty() {return top == 0;}
}

上面實現的 棧 底層是一個動態數組，它的入棧和出棧都達到了O(1)。其實棧的底層也可以實現成鏈表的結構：

（1） 底層為單向鏈表。 如果底層維護一個單鏈表，那么可以將入棧實現為頭插；出棧實現為頭刪；這樣以來它的時間復雜的也可以達到O(1)。

（2）底層為雙向鏈表。 對于雙向鏈表來說，由于同時記錄了head結點和last結點，并且每個結點的前后結點都是明確的，故無論是在頭部使用插入刪除模擬入棧出棧，還是在尾部實現，復雜度都可以達到O(1)。

這一點在Java集合類LinkedList中給出的接口方法中，得到了體現，它里面就提供了push()、pop()、peek()等方法。

三、棧、虛擬機棧、棧幀有什么區別？

1. 棧是一種數據結構，用于存儲和管理數據。
2. 虛擬機棧是JVM在執行Java程序時使用的一塊內存區域，包含了線程的棧幀。
3. 棧幀是虛擬機棧中的一個元素，用于存儲方法調用的信息。

四、隊列 概念與特性

只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表，隊列具有先進先出FIFO(First In First Out) 的特點。

進行插入操作的一端稱為隊尾（Tail/Rear），進行刪除操作的一端稱為隊頭（Head/Front）

五、Queue集合類及模擬實現

1、Queue的底層結構

眾所周知，無論是棧也好，隊列也好，它們的本質都是一個容器，既然是容器那么底層就有兩種結構：順序結構、鏈式結構。那么隊列的底層究竟是用 順序結構還是鏈式結構？如果使用鏈式結構，那么是使用單向還是雙向呢？下面我們一起來探討一下：

（1）順序結構

我們知道，隊列的兩個關鍵操作是，入隊和出隊。如果使用順序結構，那么意味著它的底層將維護一個數組，此時我們有兩種實現方案：

• 方案一： 使用數組的頭插完成入隊，使用數組的尾刪實現出隊
• 方案二： 使用數組的尾插完成入隊，使用數組的頭刪實現出隊

方案一分析：使用方案1，入隊的話使用頭插法，需要挪動數組元素，復雜度為O(N)；出隊的復雜度可以達到O(1)。

方案二分析：使用方案2，入隊復雜度可達到O(1)，而出隊，由于使用的頭刪，每次需要移動大量的元素，復雜度達到了O(N)。所以這兩種方案均不能保證入隊和出隊的復雜度達到O(1)，因此不建議采用。但是可通過循環數組，解決上述問題（后面講解）

（2）鏈式結構

• 方案一：使用單向鏈表。
• 方案二：使用雙向鏈表。

方案一分析：如果采用方案1使用單向鏈表，我們需要定義兩個特殊結點 ：頭結點-head，尾結點-last。由于鏈表是單向的，所以如果此時我們采用頭插表示入隊，復雜度可達到O(1)；尾刪表示出隊，由于鏈表是單向的，所以還需要找到 last 結點的前一個結點，復雜度達到了O(N)。所以需要使用尾插表示入隊，復雜度可達到O(1)；頭刪表示出隊，復雜度也可達到O(1).

方案二分析：如果采用方案2使用雙向鏈表。由于鏈表是雙向的，所以 無論是將頭插表示出隊，尾刪表示入隊；還是尾插表示入隊，頭刪表示出隊都可以達到復雜度為O(1).

2、Java集合中的 Queue

并且在Java集合中的Queue接口底層實現的就是一個雙向鏈表：

下面我們先查看一下Queue接口中一些常見的隊列方法：

方法	功能
boolean offer(E e)	入隊列，將元素插入隊列尾部
E poll()	出隊列，移除并返回隊頭元素
E peek()	獲取隊頭元素，但不移除
int size()	獲取隊列中有效元素的個數
boolean isEmpty()	檢測隊列是否為空

3、Queue 模擬實現

同樣根據上面給出的隊列方法，下面就實現一個底層為雙向鏈表的隊列，大家可以參照上述實現思路和代碼注釋進行理解：

//原理：先進先出
//思路：雙向鏈表頭尾無所謂，下面采用[頭插、尾刪]代替[入隊、出隊]
public class DQueue {// 定義雙向鏈表節點static class Node {public int val;public Node prev;public Node next;public Node(int val) {this.val = val;}}// 頭結點public Node head;// 尾結點public Node last;// 隊列長度public int size;//1.入隊列：boolean offer(E e) 【頭插】public boolean offer(int e) {Node node = new Node(e);// 判空if (isEmpty()) {head = node;last = node;} else {// 頭插node.next = head;head.prev = node;head = head.prev;}size++;return true;}//2.出隊列：E poll() 【尾刪】public int poll() {// 判空if (isEmpty()) {// 這里可以自定義異常throw new EmptyException("隊列為空!");}// 接收出隊元素int ret = head.val;// 如果只有1個結點if (head.next == null) {last = null;head = null;} else {// 大于1個結點last.prev.next = null;last = last.prev;}size--;return ret;}//3.獲取隊頭元素：int peek() public int peek() {// 判空if (isEmpty()) {// 這里可以自定義異常throw new EmptyException("隊列為空!");}return head.val;}//4.獲取隊列中有效元素個數：int size() public int getSize() {return size;}//5.檢測隊列是否為空：boolean isEmpty() public boolean isEmpty() {return size == 0;}
}

六、設計循環隊列

循環隊列通過巧妙地利用數組的循環使用，解決了普通隊列在頭部插入和刪除操作時效率低下的問題，使得offer()和poll()操作均能夠在O(1)的時間復雜度內完成。這種結構經常在 生產者消費者模型（敬請期待） 中使用。

1、循環隊列涉及的兩個關鍵問題

循環隊列的設計主要涉及兩個關鍵問題：

1. 數組下標如何循環？
2. 如何判斷循環隊列的空與滿？

（1）問題 1 解決方案

方案一： 讓 head 和 tail 使用加 1 取模操作。既保證當 head 和 tail 不處于數組尾下標時，加 1 取模操作不影響下標正常遞增，又能保證 head 和 tail 處于數組尾下標時繼續 入隊 或 出隊 下標循環。

方案二： 判斷 tail 和 head 與 數組長度 nums.length 是否相等，相等則置 0 保證下標循環。

（2）問題 2 解決方案

方案一： 設置 usedSize 變量記錄隊列元素個數。usedSize 為 0 隊列為空；usedSize 等于數組長度 nums.length 隊列為滿。

方案二： 犧牲 1 個數組元素。當 head 等于 tail 時表示隊列為空；當 tail + 1 等于 head 時表示隊列為滿。

2、循環隊列具體實現

解決了上面兩個問題，下面的實現就是信手拈來。下面給出具體的實現代碼，大家可以參照注釋理解（判空 / 滿 ：這里采用 useSize；循環：使用 head / tail 與 nums.length 判斷）：

// 規定有效元素為：[head,tail)
// 判空判滿使用：usedSize
// 下標循環使用：head / tail 與 nums.length 判斷
public class CircularQueue {// 數組private int[] elem;// 隊頭private int head;// 隊尾的下一個private int tail;// 有效元素個數private int usedSize;// 使用構造方法，初始化循環隊列public CircularQueue(int k) {this.elem = new int[k];this.head = 0;this.tail = 0;this.usedSize = 0;}// 1.入隊列：put()public boolean put(int val) {// 判滿if (isFull()) {return false;}// 正常入隊情況elem[tail ++] = val;// 增加有效元素個數usedSize ++;// 判斷下標if (tail == elem.length) {tail = 0;}return true;}// 2.出隊列：take()public int take() {// 判空if (isEmpty()) {throw new EmptyException("隊列為空!");}// 正常出隊情況int val = elem[head ++];// 減少有效元素個數usedSize --;// 判斷下標if (head == elem.length) {head = 0;}return val;}// 3.獲取隊頭元素：peekHead()public int peekHead() {// 判空if (isEmpty()) {throw new EmptyException("隊列為空!");}int val = elem[head --];return val;}// 4.獲取隊尾元素：peekTail()public int peekTail() {// 判空if (isEmpty()) {throw new EmptyException("隊列為空!");}// 由于 tail 指向最后一個有效元素的下一個，所以需要考慮下標邊界情況int index = tail == 0? elem.length -1:tail -1;int val = elem[index];return val;}// 5.判空：isEmpty()public boolean isEmpty() {return usedSize == 0;}// 6.判滿：isFull()public boolean isFull() {return usedSize == elem.length;}// 7.獲取隊列有效元素個數：getSize()public int getSize() {return usedSize;}
}

七、Deque 集合類

Deque表示一個雙端隊列，即允許兩端都可以進行入隊和出隊操作的隊列。

在Java集合框架中，Deque是一個接口，它實現了LinkedList和ArrayDeque，分別表示雙端隊列的線性實現 和 雙端隊列的鏈式實現。其中線性實現的底層為一個循環數組，鏈式實現的底層為一個雙向鏈表。

在實際工程中，使用Deque接口是比較多的，Deque接口中涵蓋了隊列和棧的功能接口，實現棧和隊列均可以使用該接口：

Deque<Integer> stack1 = new ArrayDeque<>();  // 線性實現
Deque<Integer> stack2 = new LinkedList<>();  // 鏈式實現Deque<Integer> queue1 = new ArrayDeque<>();  // 線性實現
Deque<Integer> queue2 = new LinkedList<>();  // 鏈式實現