LinkedList 實作 Deque 介面，天然支援雙端操作，是實作堆疊與佇列的理想選擇。本文從資料結構原理出發，展示如何用 LinkedList 模擬 LIFO 堆疊與 FIFO 佇列，並說明 JDK 內建 ArrayDeque 的優勢。
| 結構 | 原則 | 口訣 | 對應 LinkedList 方法 |
|---|---|---|---|
| 堆疊 | LIFO (Last In First Out) | 像一疊盤子，後放上去的先拿 | addFirst() / removeFirst() 或 push() / pop() |
| 佇列 | FIFO (First In First Out) | 像排隊買飲料，先來的先服務 | addLast() / removeFirst() 或 offer() / poll() |
import java.util.LinkedList;
public class MyStack<E> {
private final LinkedList<E> list = new LinkedList<>();
public void push(E e) {
list.addFirst(e); // 或 list.push(e)
}
public E pop() {
if (list.isEmpty()) throw new EmptyStackException();
return list.removeFirst(); // 或 list.pop()
}
public E peek() {
if (list.isEmpty()) throw new EmptyStackException();
return list.getFirst(); // 或 list.peek()
}
public boolean isEmpty() {
return list.isEmpty();
}
public int size() {
return list.size();
}
}
import java.util.LinkedList;
public class MyQueue<E> {
private final LinkedList<E> list = new LinkedList<>();
public void offer(E e) {
list.addLast(e); // 尾端加入
}
public E poll() {
return list.pollFirst(); // 頭端取出，空回傳 null
}
public E remove() {
return list.removeFirst(); // 頭端取出，空拋出例外
}
public E peek() {
return list.peekFirst(); // 查看頭端不移除
}
public boolean isEmpty() {
return list.isEmpty();
}
public int size() {
return list.size();
}
}
import java.util.LinkedList;
public class StackQueueDemo {
public static void main(String[] args) {
// === 堆疊示範 ===
System.out.println("=== 堆疊 ====");
LinkedList<String> stack = new LinkedList<>();
stack.push("Java"); // 底
stack.push("Python");
stack.push("Go"); // 頂
System.out.println("堆疊頂端: " + stack.peek()); // Go
while (!stack.isEmpty()) {
System.out.println("彈出: " + stack.pop()); // Go → Python → Java
}
// === 佇列示範 ===
System.out.println("\n=== 佇列 ====");
LinkedList<String> queue = new LinkedList<>();
queue.offer("Task-1"); // 前
queue.offer("Task-2");
queue.offer("Task-3"); // 後
System.out.println("佇列前端: " + queue.peek()); // Task-1
while (!queue.isEmpty()) {
System.out.println("處理: " + queue.poll()); // Task-1 → Task-2 → Task-3
}
// === 雙端佇列操作 ===
System.out.println("\n=== Deque 雙端操作 ====");
LinkedList<String> deque = new LinkedList<>();
deque.addFirst("Head");
deque.addLast("Tail");
deque.addFirst("New-Head");
System.out.println("移除頭: " + deque.removeFirst()); // New-Head
System.out.println("移除尾: " + deque.removeLast()); // Tail
}
}
LinkedList 實作 Deque<E>，提供豐富的雙端操作：
| 操作 | 拋出例外 | 回傳特殊值 | 說明 |
|---|---|---|---|
| 頭端插入 | addFirst(e) | offerFirst(e) | |
| 尾端插入 | addLast(e) | offerLast(e) | add(e) 等同 addLast |
| 頭端移除 | removeFirst() | pollFirst() | 空時前者拋 NoSuchElementException |
| 尾端移除 | removeLast() | pollLast() | |
| 頭端檢視 | getFirst() | peekFirst() | |
| 尾端檢視 | getLast() | peekLast() |
// 堆疊專用（LIFO）
stack.push(e); // = addFirst(e)
stack.pop(); // = removeFirst()
stack.peek(); // = peekFirst()
// 佇列專用（FIFO）
queue.offer(e); // = addLast(e)
queue.poll(); // = pollFirst()
queue.peek(); // = peekFirst()
| 指標 | LinkedList | ArrayDeque |
|---|---|---|
| 底層結構 | 雙向鏈結串列 | 循環陣列 (可擴容) |
| 記憶體開銷 | 高 (每節點 3 個參考) | 低 (連續陣列) |
| 頭尾增刪 | O(1) | O(1) 擴攤 |
| 隨機存取 | O(n) | O(1) |
| 快取友善 | 差 | 優 |
| 執行緒安全 | 否 | 否 |
結論：非執行緒安全環境下，ArrayDeque 幾乎全面優於 LinkedList。僅在需要頻繁中間插入/刪除、或實作 List 介面時才考慮 LinkedList。
// 同步包裝 (效能較差)
Deque<String> syncDeque = Collections.synchronizedCollection(new LinkedList<>());
// 並發安全 (推薦)
BlockingDeque<String> concurrentDeque = new LinkedBlockingDeque<>();
// 或無界佇列
BlockingQueue<String> queue = new LinkedBlockingQueue<>();
LinkedList 透過 Deque 介面完美支援堆疊與佇列操作。教學上適合理解指標操作與雙向鏈結結構；實務上首選 ArrayDeque 作為非同步堆疊/佇列，首選 LinkedBlockingQueue/Deque 作為並發環境。掌握 push/pop、offer/poll、addFirst/removeLast 等語義化方法，能寫出更易讀、少 Bug 的程式碼。
