您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言雙向鏈表實現隊列：帶頭尾節點的非循環設計

編輯：關於C

為什麼選雙向鏈表實現隊列？

隊列只在頭部刪除、尾部插入，單鏈表尾部插入需遍歷 O(n)，雙向鏈表配合尾指針 O(1)。
引入虛擬頭尾節點（哨兵），統一空/非空邊界條件，無需特判首尾節點，代碼極簡。
動態分配節點，無「假溢出」與固定容量限制。

節點與隊列結構

typedef struct Node {
    int element;
    struct Node *prior, *next;
} Node;

typedef struct {
    Node *head;  // 虛擬頭節點
    Node *tail;  // 虛擬尾節點
} Queue;

核心操作實現

初始化：頭尾節點互指

void Queue_Init(Queue *q) {
    q->head = malloc(sizeof(Node));
    q->tail = malloc(sizeof(Node));
    q->head->prior = NULL;
    q->tail->next = NULL;
    q->head->next = q->tail;
    q->tail->prior = q->head;  // 空隊列標志：head->next == tail
}

入隊：尾節點前插入

void EnQueue(Queue *q, int x) {
    Node *n = malloc(sizeof(Node));
    n->element = x;
    n->next = q->tail;
    n->prior = q->tail->prior;
    q->tail->prior->next = n;
    q->tail->prior = n;
}

出隊：頭節點後刪除

int DeQueue(Queue *q) {
    if (q->head->next == q->tail) return INT_MIN; // 空隊列
    Node *victim = q->head->next;
    int val = victim->element;
    q->head->next = victim->next;
    victim->next->prior = q->head;
    free(victim);
    return val;
}

判空與打印

bool IsEmpty(const Queue *q) { return q->head->next == q->tail; }

void PrintQueue(const Queue *q) {
    for (Node *p = q->head->next; p != q->tail; p = p->next)
        printf("%d ", p->element);
    puts("");
}

完整可測試主程式

int main(void) {
    Queue q; Queue_Init(&q);
    EnQueue(&q, 2); EnQueue(&q, 1); EnQueue(&q, 9);
    EnQueue(&q, 3); EnQueue(&q, 4);
    PrintQueue(&q);           // 2 1 9 3 4
    DeQueue(&q); DeQueue(&q); DeQueue(&q);
    PrintQueue(&q);           // 3 4
    // 釋放頭尾節點
    free(q.head); free(q.tail);
    return 0;
}

對比總結

實現方式	入隊	出隊	空間	代碼複雜度
順序循環隊列	O(1)	O(1)	固定	中（需處理滿/空判斷）
單鏈表+尾指針	O(1)	O(1)	動態	中（出隊需特判最後一節點）
雙向鏈表+頭尾哨兵	O(1)	O(1)	動態	低（統一邊界，無特判）