棧與隊列數據結構詳解：順序/鏈式實現、循環隊列與環形緩衝區

棧與隊列數據結構詳解：順序/鏈式實現、循環隊列與環形緩衝區

棧（LIFO）與隊列（FIFO）是最基礎的線性數據結構。本文詳細講解其定義、順序/鏈式兩種實現方式、核心操作代碼，重點分析循環隊列解決假溢出的原理與環形緩衝區優化技巧，並提供完整 Java 實現源碼鏈接。

一、 棧

1. 定義與特性

• 線性表，僅允許一端（棧頂）插入/刪除
• 後進先出（LIFO）
• 核心操作：push（入棧）、pop（出棧）、top（棧頂指針）

2. 實現方式

順序棧（數組）

// 入棧
public void push(T item) {
    if (top >= capacity) throw new IllegalStateException("Stack full");
    items[top++] = item;
}
// 出棧
public T pop() {
    if (top <= 0) return null;
    return (T) items[--top];
}

鏈棧（單鏈表頭插法）

private class Node { T item; Node next; }
private Node top; int count;

// 入棧：頭插法
public void push(T item) {
    Node old = top;
    top = new Node();
    top.item = item;
    top.next = old;
    count++;
}
// 出棧：移動 top 指針
public T pop() {
    T item = top.item;
    top = top.next;
    count--;
    return item;
}

二、 隊列

1. 定義與特性

• 一端入隊（尾），一端出隊（頭），先進先出（FIFO）
• 雙指針：head（讀）、tail（寫）

2. 順序存儲與假溢出問題

數組實現時，tail == maxSize 不代表隊列滿，可能 head 前有空閒空間（假溢出）。

3. 循環隊列（環形緩衝區）解決方案

邏輯上將數組首尾相連，指針取模運算實現循環：

// 取模版本
head = (head + 1) % maxSize;
tail = (tail + 1) % maxSize;
size = (tail + maxSize - head) % maxSize;

// 無取模優化版（RingBuffer 風格）
int next = tail + 1;
if (next >= bufferSize) next = 0;
if (next == head) return false; // 滿
buffer[next] = item;
tail = next;

4. 鏈式存儲（鏈隊列）

private Node head, tail;
// 入隊：尾部掛接
public void enqueue(T item) {
    Node old = tail;
    tail = new Node();
    tail.item = item;
    tail.next = null;
    if (isEmpty()) head = tail;
    else old.next = tail;
    count++;
}
// 出隊：頭部移動
public T dequeue() {
    T res = head.item;
    head = head.next;
    if (isEmpty()) tail = null;
    count--;
    return res;
}

三、 源碼獲取

完整可運行實現：GitHub 算法倉庫