C 語言雙向鏈表實現隊列：帶頭尾節點非循環設計，O(1) 入隊出隊全解析

設計動機

• 數組隊列需處理環狀下標、擴容遷移。
• 單鏈表隊列出隊 O(1) 但入隊需遍歷到尾（無尾指針時）。
• 雙向鏈表 + 頭尾哨兵節點：頭尾操作均 O(1)，無需特判空隊列邊界。

節點與隊列結構

typedef struct Node {
    int data;
    struct Node *prev, *next;
} Node;

typedef struct {
    Node *head, *tail; // 哨兵節點，不存有效數據
} Queue;

核心操作實現

1. 初始化：頭尾互指

void init(Queue *q) {
    q->head = malloc(sizeof(Node));
    q->tail = malloc(sizeof(Node));
    q->head->prev = NULL; q->head->next = q->tail;
    q->tail->prev = q->head; q->tail->next = NULL;
}

2. 入隊：尾哨兵前插入

void enqueue(Queue *q, int x) {
    Node *n = malloc(sizeof(Node));
    n->data = x;
    n->prev = q->tail->prev;
    n->next = q->tail;
    q->tail->prev->next = n;
    q->tail->prev = n;
}

3. 出隊：頭哨兵後刪除

int dequeue(Queue *q) {
    if (q->head->next == q->tail) return -1; // 空
    Node *n = q->head->next;
    int val = n->data;
    n->next->prev = q->head;
    q->head->next = n->next;
    free(n);
    return val;
}

4. 判空：頭尾相連

int isEmpty(Queue *q) { return q->head->next == q->tail; }

完整測試主函數

int main() {
    Queue q; init(&q);
    enqueue(&q, 2); enqueue(&q, 1); enqueue(&q, 9);
    // 隊列: 2 1 9
    printf("%d ", dequeue(&q)); // 2
    printf("%d ", dequeue(&q)); // 1
    enqueue(&q, 5);
    while (!isEmpty(&q)) printf("%d ", dequeue(&q)); // 9 5
    return 0;
}

優缺點總結