C 語言實作隊列：鏈式與陣列雙重解析

編輯：關於C語言

前言

隊列是資料結構中基礎且重要的線性結構，遵循「先進先出」原則。在 C 語言中，主要透過「鏈式儲存」與「順序儲存」兩種方式實作。本文將完整呈現兩種實作的核心操作，包含初始化、入隊、出隊、讀取隊首、判空與清空等六大核心演算法，並附上可直接編譯執行的完整程式碼。

一、鏈式隊列實作

鏈式隊列利用動態記憶體分配節點，無固定大小限制，適合資料量不確定的場景。結構定義包含資料欄位與指向下一節點的指標；隊列控制結構則維護隊首與隊尾指標。

核心操作詳解

初始化：將隊首、隊尾指標同步設為 NULL，表示空隊列。
入隊：分配新節點，若隊列為空則隊首隊尾同指向新節點；否則將新節點接在隊尾後，並更新隊尾指標。注意 hq->rear = hq->rear->next = newP; 的賦值順序。
出隊：檢查空隊列，暫存隊首資料與指標，移動隊首指標至下一節點，若刪除後為空則同步將隊尾設為 NULL，釋放原節點並回傳資料。
讀取隊首：僅回傳隊首資料，不改變結構。
判空：檢查隊首指標是否為 NULL。
清空：遍歷釋放所有節點，最後重置隊首隊尾指標。

#include <stdio.h>
#include <stdlib.h>

typedef int elemType;

struct sNode {
    elemType data;
    struct sNode *next;
};

struct queueLK {
    struct sNode *front;
    struct sNode *rear;
};

void initQueue(struct queueLK *hq) {
    hq->front = hq->rear = NULL;
}

void enQueue(struct queueLK *hq, elemType x) {
    struct sNode *newP = malloc(sizeof(struct sNode));
    if (!newP) { printf("記憶體分配失敗！"); exit(1); }
    newP->data = x;
    newP->next = NULL;
    if (hq->rear == NULL) {
        hq->front = hq->rear = newP;
    } else {
        hq->rear = hq->rear->next = newP;
    }
}

elemType outQueue(struct queueLK *hq) {
    if (hq->front == NULL) { printf("隊列為空，無法刪除！"); exit(1); }
    struct sNode *p = hq->front;
    elemType temp = p->data;
    hq->front = p->next;
    if (hq->front == NULL) hq->rear = NULL;
    free(p);
    return temp;
}

elemType peekQueue(struct queueLK *hq) {
    if (hq->front == NULL) { printf("隊列為空！"); exit(1); }
    return hq->front->data;
}

int emptyQueue(struct queueLK *hq) {
    return hq->front == NULL;
}

void clearQueue(struct queueLK *hq) {
    struct sNode *p = hq->front;
    while (p) {
        hq->front = hq->front->next;
        free(p);
        p = hq->front;
    }
    hq->rear = NULL;
}

二、順序隊列實作

順序隊列以動態陣列為底層，採用環狀佈局提高空間利用率。當隊列滿時自動擴容，採用 realloc 倍增策略，並處理資料搬移以維持邏輯順序。

關鍵設計點

結構包含陣列指標、隊首/隊尾下標、當前長度與最大容量。
入隊時若 (rear+1)%maxSize == front 觸發擴容：分配雙倍空間，若隊尾未在陣列末端則將前段資料搬移至新空間高址處，更新隊尾下標與容量。
出隊與讀取隊首均透過模運算計算實際下標。
清空時釋放陣列記憶體並重置所有欄位。

#include <stdio.h>
#include <stdlib.h>

typedef int elemType;

struct queue {
    elemType *queue;
    int front, rear, len;
    int maxSize;
};

void againMalloc(struct queue *q) {
    elemType *p = realloc(q->queue, 2 * q->maxSize * sizeof(elemType));
    if (!p) { printf("空間分配失敗！"); exit(1); }
    q->queue = p;
    if (q->rear != q->maxSize - 1) {
        for (int i = 0; i <= q->rear; i++)
            q->queue[i + q->maxSize] = q->queue[i];
        q->rear += q->maxSize;
    }
    q->maxSize *= 2;
}

void initQueue(struct queue *q, int ms) {
    if (ms <= 0) { printf("ms值非法!"); exit(1); }
    q->maxSize = ms;
    q->queue = malloc(ms * sizeof(elemType));
    if (!q->queue) { printf("記憶體分配失敗！"); exit(1); }
    q->front = q->rear = 0;
}

void enQueue(struct queue *q, elemType x) {
    if ((q->rear + 1) % q->maxSize == q->front) againMalloc(q);
    q->rear = (q->rear + 1) % q->maxSize;
    q->queue[q->rear] = x;
}

elemType outQueue(struct queue *q) {
    if (q->front == q->rear) { printf("隊列為空，無法刪除！"); exit(1); }
    q->front = (q->front + 1) % q->maxSize;
    return q->queue[q->front];
}

elemType peekQueue(struct queue *q) {
    if (q->front == q->rear) { printf("隊列為空！"); exit(1); }
    return q->queue[(q->front + 1) % q->maxSize];
}

int emptyQueue(struct queue *q) {
    return q->front == q->rear;
}

void clearQueue(struct queue *q) {
    if (q->queue) {
        free(q->queue);
        q->queue = NULL;
        q->front = q->rear = q->maxSize = 0;
    }
}