隊列數據結構全解析：鏈隊列、循環隊列 C 語言完整實現

隊列數據結構全解析：鏈隊列、循環隊列 C 語言完整實現

隊列（FIFO）是受限線性表，僅允許隊尾入隊、隊頭出隊。本文實現鏈式與循環順序兩種存儲結構。

一、鏈隊列

帶頭結點單鏈表，頭/尾指針分別指向頭結點/尾節點。

typedef struct Node { int data; struct Node *next; } Node, *Queue;
typedef struct { Queue front, rear; } LinkQueue;

void initQueue(LinkQueue *q) {
    q->front = q->rear = malloc(sizeof(Node));
    q->front->next = NULL;
}
bool isEmpty(LinkQueue q) { return q.front == q.rear; }

void insertQueue(LinkQueue *q, int val) {
    Node *n = malloc(sizeof(Node));
    n->data = val; n->next = NULL;
    q->rear->next = n; q->rear = n;
}
void deleteQueue(LinkQueue *q) {
    if (isEmpty(*q)) return;
    Node *n = q->front->next;
    q->front->next = n->next;
    if (q->rear == n) q->rear = q->front;  // 刪除最後一個
    free(n);
}

二、循環隊列（順序存儲）

固定大小數組，front 指向隊頭，rear 指向隊尾**下一位置**。犧牲一個單元區分空/滿。

#define MAX_SIZE 5
typedef struct { int *base; int front, rear; } CircularQueue;

void initQueue(CircularQueue *q) {
    q->base = malloc(MAX_SIZE * sizeof(int));
    q->front = q->rear = 0;
}
int getLength(CircularQueue q) {
    return (q.rear - q.front + MAX_SIZE) % MAX_SIZE;
}
void insertQueue(CircularQueue *q, int e) {
    if ((q->rear + 1) % MAX_SIZE == q->front) { puts("Full"); return; }
    q->base[q->rear] = e;
    q->rear = (q->rear + 1) % MAX_SIZE;
}
void deleteQueue(CircularQueue *q) {
    if (q->front == q->rear) { puts("Empty"); return; }
    q->front = (q->front + 1) % MAX_SIZE;
}

測試結果

循環隊列初始化：長度 0
入隊 0,1,2,3 → 遍歷: 0 1 2 3
再入隊 4 → Full (犧牲一格)
出隊 0 → 1 2 3
出隊 1 → 2 3
出隊 2 → 3
出隊 3 → Empty

對比總結

掌握兩種實現，可根據場景選擇最適隊列結構。

1. 上一篇文章： C99 可變參數宏 __VA_ARGS__ 實戰：調試日志開關與 Android NDK 應用
2. 下一篇文章： 二分查找算法詳解：原理、實現與注意事項

關於C語言

博客首發：以旁觀者視角重啟技術記錄之路

博客首發：以旁觀者視角重啟技術記錄之路 一直想記錄成長與工

CentOS 6.6 編譯安裝 GCC 4.7.4 完整實踐：依賴庫、配置參數、多版本切換

CentOS 6.6 編譯安裝 GCC 4.7.4 完整實踐

C語言關鍵字深度解析：const 與 volatile 的特性與應用

const 與 volatile 分析 1. const 修

C# WinForms 執行期控件設計器實作 (二) - 效果展示與擴充

上篇已提供核心程式碼架構，本文展示執行畫面並討論進階擴充方向