链式队列 - C语言实现

数据结构学习笔记 | 2026-5-7

一、基本概念

队列（Queue）是一种先进先出（FIFO, First In First Out）的线性表。它只允许在表的一端（队尾）进行插入，在另一端（队头）进行删除。

链式队列：用链表实现的队列，不需要考虑队列满的问题，动态分配内存。

基本操作：

  • 初始化：创建空队列
  • 入队（enQueue）：在队尾插入元素
  • 出队（deQueue）：删除队头元素并返回其值
  • 判空（QueueEmpty）：判断队列是否为空
  • 销毁（DeleteQueue）：释放队列占用的所有内存

二、结构体定义

链式队列使用两层结构：数据节点类型和链队节点类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef char ElemType;

// 数据节点类型
typedef struct qnode
{
    ElemType data;         // 数据元素
    struct qnode *next;
} DataNode;

// 链队节点类型
typedef struct LinkQuNode
{
    DataNode *front;       // 指向单链表队头结点
    DataNode *rear;        // 指向单链表队尾结点
} LinkQuNode;
成员 所属结构体 含义
data DataNode 节点的数据域
next DataNode 指向下一个数据节点的指针
front LinkQuNode 指向队头节点的指针
rear LinkQuNode 指向队尾节点的指针

说明：链队使用 LinkQuNode 结构体统一管理 front 和 rear 两个指针，方便操作

三、函数声明

1
2
3
4
5
6
void InitQueue(LinkQuNode **q);           // 初始化队列
void enQueue(LinkQuNode **q, ElemType e); // 入队
bool deQueue(LinkQuNode **q, ElemType *e);// 出队
bool QueueEmpty(LinkQuNode *q);           // 判断队列是否为空
void DeleteQueue(LinkQuNode **q);         // 销毁队列
void disp(LinkQuNode *q);                 // 遍历显示队列元素

四、功能函数实现

1. 初始化队列

1
2
3
4
5
void InitQueue(LinkQuNode **q)
{
    (*q) = (LinkQuNode *)malloc(sizeof(LinkQuNode));
    (*q)->front = (*q)->rear = NULL;
}
  • 通过 malloc() 分配链队节点空间
  • 将 front 和 rear 指针都设为 NULL，表示空队列

2. 入队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void enQueue(LinkQuNode **q, ElemType e)
{
    // 生成入队的新结点
    DataNode *p;
    p = (DataNode *)malloc(sizeof(DataNode));
    p->data = e;
    p->next = NULL;

    if ((*q)->rear == NULL) // 队列为空
    {
        (*q)->front = (*q)->rear = p;
    }
    else
    {
        (*q)->rear->next = p;
        (*q)->rear = p;
    }
}

特点：新节点插入到队尾，根据队列是否为空分别处理

3. 出队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool deQueue(LinkQuNode **q, ElemType *e)
{
    DataNode *t;
    if ((*q)->rear == NULL) // 队列为空
        return false;

    t = (*q)->front;          // t指向队头结点
    *e = t->data;

    if ((*q)->rear == (*q)->front) // 只有一个结点
    {
        (*q)->rear = (*q)->front = NULL;
    }
    else // 有多个结点
    {
        (*q)->front = (*q)->front->next;
    }

    free(t);
    return true;
}

注意：出队后需要 free(t) 释放被删除节点的内存

4. 判断队列是否为空

1
2
3
4
bool QueueEmpty(LinkQuNode *q)
{
    return (q->rear == NULL);
}

5. 销毁队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void DeleteQueue(LinkQuNode **q)
{
    DataNode *p = (*q)->front, *r;
    if (p != NULL) // 释放数据节点占用空间
    {
        r = p->next;
        while (r != NULL)
        {
            free(p);
            p = r;
            r = p->next;
        }
    }
    free(p);
    free(*q); // 释放链队结点占用空间
}

说明：先逐个释放所有数据节点，最后释放链队节点

6. 遍历显示

1
2
3
4
5
6
7
8
9
void disp(LinkQuNode *q)
{
    DataNode *s = q->front;
    while (s != NULL)
    {
        printf("%4c", s->data);
        s = s->next;
    }
}

五、使用示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int main(void)
{
    LinkQuNode *q;
    ElemType e;

    printf("队列开始初始化\n");
    InitQueue(&q);

    if (QueueEmpty(q))
        printf("队列为空\n");

    printf("\n开始入队\n");
    enQueue(&q, 'a');
    enQueue(&q, 'b');
    enQueue(&q, 'c');
    enQueue(&q, 'd');
    enQueue(&q, 'e');
    printf("队列中的元素:\n");
    disp(q); // 输出: a   b   c   d   e

    printf("\n\n队列开始出队");
    deQueue(&q, &e);
    printf("\n当前出队的元素为：%c\n", e); // a
    disp(q); // 输出: b   c   d   e

    printf("\n释放队列\n");
    DeleteQueue(&q);

    return 0;
}

运行结果：

1
2
3
4
5
6
7
8
9
10
11
队列开始初始化
队列为空

开始入队
队列中的元素:
   a   b   c   d   e

队列开始出队
当前出队的元素为：a
   b   c   d   e
释放队列

六、图解链式队列

1
2
3
4
5
6
7
链式队列结构示意：

    LinkQuNode
    ┌─────────────────┐
    │  front  → [a] → [b] → [c] → NULL
    │  rear   → ────────┘
    └─────────────────┘
1
2
3
4
5
6
7
8
9
入队操作 (enQueue 'x'):

    原队列: front → [a] → [b] → [c] → NULL
                                         ↑
                                        rear
    
    入队后: front → [a] → [b] → [c] → [x] → NULL
                                         ↑
                                        rear
1
2
3
4
5
6
7
8
9
10
出队操作 (deQueue):

    原队列: front → [a] → [b] → [c] → NULL
                                        ↑
                                      rear
    
    出队后: front → [b] → [c] → NULL
                                  ↑
                                rear
    返回: a

七、时间复杂度分析

操作 时间复杂度 说明
初始化 O(1) 只需分配链队节点空间
入队 O(1) 通过 rear 指针直接在队尾操作
出队 O(1) 通过 front 指针直接在队头操作
判空 O(1) 直接判断 rear == NULL
遍历显示 O(n) 需遍历所有数据节点
销毁队列 O(n) 需逐个释放所有节点

注意：链式队列的入队和出队操作都是 O(1)，这是链式队列相比顺序队列的显著优势

八、关键知识点

  1. 队列的特点：先进先出（FIFO），队尾入队、队头出队
  2. 链队优势：不需要考虑队列满的问题，动态分配内存
  3. front 和 rear：front 指向队头，rear 指向队尾，两个指针配合完成操作
  4. 空队列判断：rear == NULL 表示队列为空
  5. 内存管理：入队 malloc() 分配节点，出队 free() 释放节点
  6. 销毁队列：必须先释放所有数据节点，再释放链队节点本身

九、完整代码

源代码文件：Linked-Queue-from-Scratch-with-C.c