C語言鏈式隊列完整實現與核心操作解析

編輯：關於C語言

鏈式隊列的C語言實現指南

隊列作為先進先出（FIFO）的線性數據結構，在任務調度、緩衝區管理等場景中至關重要。本文提供基於鏈表的隊列完整實現，包含創建、入隊、出隊、銷毀等核心操作，代碼結構清晰，適合學習與項目直接使用。

數據結構設計

採用帶頭結點的鏈表結構，隊列結構體維護隊首和隊尾指針，實現O(1)時間複雜度的入隊出隊操作：

typedef int ElementType;  // 隊列元素類型，可根據需要修改

typedef struct QueueNode {
    ElementType element;
    struct QueueNode *next;
} QueueNode, *Node;

typedef struct {
    Node first;  // 隊首指針（指向頭結點）
    Node last;   // 隊尾指針（指向最後一個元素結點）
} QueueStruct, *Queue;

核心操作實現

1. 創建空隊列

分配頭結點並初始化首尾指針均指向頭結點：

Queue createQueue() {
    Queue Q = (Queue)malloc(sizeof(QueueStruct));
    Node node = (Node)malloc(sizeof(QueueNode));
    
    if (!Q || !node) {
        fprintf(stderr, "內存分配失敗\n");
        exit(EXIT_FAILURE);
    }
    
    node->next = NULL;
    Q->first = Q->last = node;
    return Q;
}

2. 判斷隊列是否為空

通過比較首尾指針是否相等判斷：

int isEmpty(Queue Q) {
    return Q->first == Q->last;
}

3. 入隊操作

在隊尾插入新結點，更新隊尾指針：

void EnQueue(ElementType X, Queue Q) {
    Node node = (Node)malloc(sizeof(QueueNode));
    if (!node) {
        fprintf(stderr, "內存分配失敗\n");
        exit(EXIT_FAILURE);
    }
    
    node->element = X;
    node->next = NULL;
    Q->last->next = node;
    Q->last = node;
}

4. 出隊操作

刪除隊首元素結點（頭結點之後的第一個結點），返回元素值：

ElementType DeQueue(Queue Q) {
    if (isEmpty(Q)) {
        fprintf(stderr, "隊列為空\n");
        exit(EXIT_FAILURE);
    }
    
    Node p = Q->first->next;
    ElementType x = p->element;
    Q->first->next = p->next;
    
    // 若刪除的是最後一個元素，需更新隊尾指針
    if (p == Q->last) {
        Q->last = Q->first;
    }
    
    free(p);
    return x;
}

5. 銷毀隊列

循環出隊釋放所有元素結點，最後釋放頭結點和隊列結構體：

void deleteQueue(Queue Q) {
    while (!isEmpty(Q)) {
        DeQueue(Q);
    }
    free(Q->first);  // 釋放頭結點
    free(Q);         // 釋放隊列結構體
}

完整頭文件定義

#ifndef QUEUE_H
#define QUEUE_H

#include 
#include 

typedef int ElementType;
typedef struct QueueNode *Node;
typedef struct queue *Queue;

struct QueueNode {
    ElementType element;
    Node next;
};

struct queue {
    Node first;
    Node last;
};

Queue createQueue();
int isEmpty(Queue Q);
void EnQueue(ElementType X, Queue Q);
ElementType DeQueue(Queue Q);
void deleteQueue(Queue Q);

#endif

使用示例與測試

以下主函數演示隊列基本操作：

int main() {
    Queue q = createQueue();
    
    printf("入隊 10, 20, 30...\n");
    EnQueue(10, q);
    EnQueue(20, q);
    EnQueue(30, q);
    
    printf("出隊順序: ");
    while (!isEmpty(q)) {
        printf("%d ", DeQueue(q));
    }
    printf("\n");
    
    deleteQueue(q);
    return 0;
}

輸出結果：入隊 10, 20, 30... 出隊順序: 10 20 30