一、棧（Stack）

1. 棧的定義

• 棧（Stack）是一種 先進后出（LIFO, Last In First Out） 的數據結構。

• 就像一摞書：最后放的書最先拿走。

---

2. 棧的常用方法（Stack 類）

• Stack<E> 繼承自 Vector，是 線程安全 的，但性能一般。

• 更推薦使用 Deque<E>（如 ArrayDeque 或 LinkedList）來實現棧結構。

方法	功能描述	備注
push(E e)	將元素壓入棧頂	相當于入棧操作
pop()	彈出棧頂元素，并返回該元素	棧為空時會拋 EmptyStackException
peek()	查看棧頂元素，但不刪除	棧為空時會拋 EmptyStackException
empty()	判斷棧是否為空	返回 true 或 false
search(Object o)	返回元素在棧中的位置（從 1 開始，棧頂為 1）	找不到返回 -1

---

3. 使用示例

• Stack<E> 繼承自 Vector，是 線程安全 的，但性能一般。(下面的(1))

• 更推薦使用 Deque<E>（如 ArrayDeque 或 LinkedList）來實現棧結構。(下面的(2))

（1）使用 Stack 類

Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
stack.push(30);System.out.println(stack.peek()); // 30
System.out.println(stack.pop());  // 30
System.out.println(stack.pop());  // 20
System.out.println(stack.empty()); // false

（2）使用 ArrayDeque 模擬棧（推薦）

Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.push("B");
stack.push("C");System.out.println(stack.pop()); // C
System.out.println(stack.peek()); // B

---

4. 棧的應用場景

• 函數調用棧：保存方法調用現場（局部變量、返回地址等）。

• 括號匹配：比如判斷 ({[]}) 是否匹配。

• 表達式求值：逆波蘭表達式（后綴表達式）。

• 回溯算法：比如迷宮尋路。

二、隊列（Queue）

1. 隊列的定義

• 隊列（Queue）是一種 先進先出（FIFO, First In First Out） 的數據結構。

• 就像排隊買票：先排隊的人先買，后排的人要等前面的人買完。

• 在 Java 中，Queue 是一個接口，繼承自 Collection 接口。

---

2. 隊列的常用方法（來自 Queue 接口）

方法	功能
boolean add(E e)	向隊列尾部插入元素，若失敗拋異常
boolean offer(E e)	向隊列尾部插入元素，失敗時返回 false
E remove()	刪除并返回隊首元素，隊列為空時拋異常
E poll()	刪除并返回隊首元素，隊列為空時返回 null
E element()	返回隊首元素但不刪除，隊列為空時拋異常
E peek()	返回隊首元素但不刪除，隊列為空時返回 null

---

3. 常見的隊列實現類

（1）LinkedList

• LinkedList 實現了 Queue 接口，可以作為普通隊列使用。

Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");
queue.offer("C");
System.out.println(queue.poll()); // A
System.out.println(queue.peek()); // B

（2）PriorityQueue（優先隊列）

• 元素按 優先級排序（默認是自然順序，小的優先）。

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
System.out.println(pq.poll()); // 1
System.out.println(pq.poll()); // 3

（3）ArrayDeque（雙端隊列）

• 推薦的隊列實現，比 LinkedList 更高效。

• 可以當隊列（FIFO）或棧（LIFO）使用。

Queue<String> dq = new ArrayDeque<>();
dq.offer("A");
dq.offer("B");
System.out.println(dq.poll()); // A

---

4. 隊列的應用場景

• 排隊系統：比如消息隊列（RabbitMQ、Kafka）。

• 緩沖區：比如網絡 IO 中的數據緩沖。

• 廣度優先搜索（BFS）：圖/樹的層序遍歷。

---

三、棧和隊列對比

特點	棧（Stack）	隊列（Queue）
存取順序	LIFO（先進后出）	FIFO（先進先出）
典型操作	push 入棧，pop 出棧	offer 入隊，poll 出隊
Java 實現類	Stack, ArrayDeque	LinkedList, ArrayDeque, PriorityQueue
應用場景	函數調用棧、表達式計算、回溯	消息隊列、BFS、排隊系統

---

? 總結

• 棧：適合 回溯 / 嵌套處理，強調后進先出。

• 隊列：適合 排隊 / 順序處理，強調先來先服務。

• 推薦 使用 ArrayDeque 來實現隊列和棧，性能比 LinkedList 和 Stack 更好。