当前位置：首页 > news >正文

【深入理解链式队列：C语言实现详解与完整代码】

news 2026/6/23 16:22:32

前言

队列（Queue）是一种 ** 先进先出（FIFO, First In First Out）的线性数据结构。它只允许在队尾（rear）插入，在队头（front）** 删除。

队列的应用场景无处不在：

操作系统任务调度
消息队列
打印机队列
广度优先搜索（BFS）
生产者 - 消费者模型

前面我们学过顺序队列（数组实现），它有固定大小、需要扩容、会出现 “假溢出” 等问题。链式队列完美解决了这些痛点！

一、链式队列是什么？

链式队列 = 用单链表实现的队列

特点：

按需申请内存，不存在容量限制（无假溢出）
不需要扩容
入队在队尾，出队在队头
时间复杂度O(1)
结构简单、稳定、高效

二、链式队列结构体设计（核心）

链式队列采用“队头指针 + 队尾指针”管理模式：

#pragma once typedef int ELEM_TYPE; // 链式队列有效节点结构体 typedef struct LQ_Node { ELEM_TYPE data; // 数据域 struct LQ_Node* next; // 指针域 } LQ_Node; // 链式队列辅助节点结构体（管理队头、队尾） typedef struct List_Queue { LQ_Node* front; // 队头指针（出队端） LQ_Node* rear; // 队尾指针（入队端） } List_Queue;

结构说明

LQ_Node：真正存储数据的节点
List_Queue：辅助管理结构
- front：指向队头节点
- rear：指向队尾节点
- 空队列：front == NULL && rear == NULL

三、链式队列支持的操作（全覆盖）

// 1. 初始化 void Init_List_Queue(struct List_Queue* plq); // 2. 入队（尾插） bool Push(struct List_Queue* plq, ELEM_TYPE val); // 3. 出队（头删） bool Pop(struct List_Queue* plq); // 4. 获取队头元素 ELEM_TYPE Front(struct List_Queue* plq); // 5. 查找元素 LQ_Node* Search(struct List_Queue* plq, ELEM_TYPE val); // 6. 判空 bool IsEmpty(struct List_Queue* plq); // 7. 获取有效元素个数 int Get_Size(struct List_Queue* plq); // 8. 清空队列 void Clear(struct List_Queue* plq); // 9. 销毁队列（释放内存） void Destroy(struct List_Queue* plq); // 10. 打印队列 void Show(struct List_Queue* plq);

四、核心函数精讲（最关键）

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<assert.h> #include<stdlib.h> #include"List_Queue.h" //1.初始化 void Init_List_Queue(struct List_Queue* plq) { assert(NULL != plq); // 空队列：队头、队尾都指向 NULL plq->front = plq->rear = NULL; } //2.入队 bool Push(struct List_Queue* plq, ELEM_TYPE val) { assert(NULL!= plq); LQ_Node* pnewnode = (LQ_Node*)malloc(sizeof(LQ_Node)); if (pnewnode == NULL) return false; pnewnode->data = val; //分情况，看链式队列是否为空 if (IsEmpty(plq)) { pnewnode->next = NULL; plq->front = plq->rear = pnewnode; return true; } //不空，修改对应三个指针 else { /*plq->rear->next = pnewnode; plq->rear = pnewnode;*/ pnewnode->next = plq->rear->next; plq->rear->next = pnewnode; plq->rear = pnewnode;// 更新队尾 return true; } } //3.出队 bool Pop(struct List_Queue* plq) { assert(NULL != plq); if (IsEmpty(plq)) return false; //2分情况处理（看此时的有效元素个数是1还是大于1） //2.1仅有唯一一个有效元素 LQ_Node* tmp = plq->front; if (tmp->next == NULL) { plq->front = plq->rear = NULL; free(tmp); tmp = NULL; return true; } else { plq->front = tmp->next;// 队头后移 free(tmp); // 释放旧队头 tmp = NULL; return true; } } //4.获取队头元素值 ELEM_TYPE Front(struct List_Queue* plq) { assert(NULL != plq); if (IsEmpty(plq)) exit(1); /*LQ_Node* p = plq->front; return p->data;*/ return plq->front->data; } //5查找 LQ_Node* Search(struct List_Queue* plq, ELEM_TYPE val) { assert(NULL != plq); if (IsEmpty(plq)) exit(1); LQ_Node* q = plq->front; while (q != NULL) { if (q->data == val) return q; q = q->next; } return NULL; } //6.判空 bool IsEmpty(struct List_Queue* plq) { // 队头为 NULL 表示空队列 return plq->front ==NULL; } //7.获取有效值个数 Size int Get_Size(struct List_Queue* plq) { assert(NULL != plq); LQ_Node* q = plq->front; int count = 0; // 遍历链表统计节点数 while (q != NULL) { count++; q = q->next; } return count; } //8.清空 void Clear(struct List_Queue* plq) { Destroy(plq); // plq->front = plq->rear = NULL; } //9.销毁 void Destroy(struct List_Queue* plq) { LQ_Node* p = plq->front; LQ_Node* q = NULL; while (p != NULL) { q = p->next; free(p); p = q; } // 重置队头、队尾 plq->front = plq->rear = NULL; } //10.打印 void Show(struct List_Queue* plq) { assert(NULL != plq); LQ_Node* p = plq->front; for ( ; p!=NULL; p=p->next) { printf("%d ", p->data); } printf("\n"); }

链式队列入队 = 单链表尾插——时间复杂度O(1)

链式队列出队 = 删除链表第一个节点——时间复杂度O(1)

五、测试主函数（可直接运行）

int main() { List_Queue head; Init_List_Queue(&head); Push(&head, 1); Push(&head, 2); Push(&head, 3); Show(&head); Pop(&head); Show(&head); // 输出：2 3 printf("队头元素：%d\n", Front(&head)); // 输出：2 Destroy(&head); return 0; }

运行结果：

六、链式队列 VS 顺序队列（重点）

特性	顺序队列	链式队列
存储结构	连续数组	链式节点
容量	固定 / 需扩容	无限（无溢出）
入队出队	O(1)	O(1)
内存分配	静态 / 动态	动态
假溢出	会出现	不会
适用场景	已知最大容量	无法预估容量