队列：一种让你又爱又恨的数据结构

队列Queue是一种与栈并列的基础线性数据结构。它的核心特点是先进先出也就是 First In First Out简称FIFO。你可以把队列想象成排队买票先来的人先买到票后来的人排在队尾。队列只允许在一端插入元素在另一端删除元素。允许插入的一端叫队尾rear允许删除的一端叫队头front。队列的常见操作有enqueue入队在队尾插入元素dequeue出队删除并返回队头元素front / peek查看队头元素但不删除isEmpty判断队列是否为空isFull判断队列是否已满主要用于顺序队列destroy销毁队列释放内存队列的应用非常广泛例如操作系统中的进程调度打印机任务队列消息队列广度优先搜索BFS键盘缓冲区网络数据包排队下面用 C 语言分别实现循环队列和链队列并给出一个经典应用用队列打印杨辉三角。一、循环队列的 C 语言实现如果用普通数组实现队列随着不断入队和出队front 和 rear 会不断后移最终导致“假溢出”数组前面明明有空位但 rear 已经到达末尾无法再入队。解决方法是使用循环队列把数组看作一个环当 rear 到达末尾时再回到下标 0。循环队列通常有两种设计牺牲一个存储单元用(rear 1) % MAX_SIZE front判断队满。增加一个size变量记录元素个数这样不会浪费空间逻辑也更直观。这里采用第二种方式。约定front指向队头元素rear指向队尾元素的下一个位置size记录当前元素个数空队列size 0满队列size MAX_SIZE入队data[rear] value; rear (rear 1) % MAX_SIZE; size出队*value data[front]; front (front 1) % MAX_SIZE; size--#include stdio.h #include stdlib.h #define MAX_SIZE 100 /* 循环队列 */ typedef struct { int data[MAX_SIZE]; int front; /* 队头下标 */ int rear; /* 队尾下一个位置 */ int size; /* 当前元素个数 */ } CircularQueue; /* 初始化队列 */ void initCircularQueue(CircularQueue *q) { q-front 0; q-rear 0; q-size 0; } /* 判断队列是否为空 */ int circularQueueEmpty(const CircularQueue *q) { return q-size 0; } /* 判断队列是否已满 */ int circularQueueFull(const CircularQueue *q) { return q-size MAX_SIZE; } /* 入队成功返回 1失败返回 0 */ int circularQueueEnqueue(CircularQueue *q, int value) { if (circularQueueFull(q)) { return 0; } q-data[q-rear] value; q-rear (q-rear 1) % MAX_SIZE; q-size; return 1; } /* 出队成功返回 1并把值存入 *value失败返回 0 */ int circularQueueDequeue(CircularQueue *q, int *value) { if (circularQueueEmpty(q)) { return 0; } *value q-data[q-front]; q-front (q-front 1) % MAX_SIZE; q-size--; return 1; } /* 查看队头元素成功返回 1失败返回 0 */ int circularQueuePeek(const CircularQueue *q, int *value) { if (circularQueueEmpty(q)) { return 0; } *value q-data[q-front]; return 1; }循环队列的优点是内存连续、访问效率高并且通过取模运算解决了假溢出问题。缺点是容量固定需要预先估计最大元素数量。二、链队列的 C 语言实现链队列用单链表实现。为了操作方便通常让front指向队头节点rear指向队尾节点。空队列front NULL且rear NULL入队创建新节点接到rear后面并更新rear出队删除front节点并更新front如果删除后队列为空还要把rear置为NULL链队列不需要预先指定容量因此一般不会出现“队满”的问题除非内存分配失败。/* 链队列 */ typedef struct QueueNode { int data; struct QueueNode *next; } QueueNode; typedef struct { QueueNode *front; /* 队头指针 */ QueueNode *rear; /* 队尾指针 */ } LinkQueue; /* 初始化链队列 */ void initLinkQueue(LinkQueue *q) { q-front NULL; q-rear NULL; } /* 判断链队列是否为空 */ int linkQueueEmpty(const LinkQueue *q) { return q-front NULL; } /* 入队 */ int linkQueueEnqueue(LinkQueue *q, int value) { QueueNode *node (QueueNode *)malloc(sizeof(QueueNode)); if (node NULL) { return 0; } node-data value; node-next NULL; if (q-rear NULL) { /* 空队列 */ q-front node; q-rear node; } else { q-rear-next node; q-rear node; } return 1; } /* 出队 */ int linkQueueDequeue(LinkQueue *q, int *value) { if (linkQueueEmpty(q)) { return 0; } QueueNode *tmp q-front; *value tmp-data; q-front tmp-next; if (q-front NULL) { /* 队列已空rear 也要置空 */ q-rear NULL; } free(tmp); return 1; } /* 查看队头元素 */ int linkQueuePeek(const LinkQueue *q, int *value) { if (linkQueueEmpty(q)) { return 0; } *value q-front-data; return 1; } /* 销毁链队列 */ void destroyLinkQueue(LinkQueue *q) { int value; while (linkQueueDequeue(q, value)) { /* 不断出队直到队列为空 */ } }链队列的优点是动态扩容、没有固定容量限制。缺点是每个节点需要额外的指针空间内存分配也可能带来一定开销。三、经典应用用队列打印杨辉三角杨辉三角是队列的经典应用之一。它的每一行都可以由上一行推导出来每个数等于上一行相邻两个数之和首尾都是 1。使用队列的算法思路初始化队列把第一行的1入队。对于每一行先在队尾入队一个0作为行结束标记。维护变量prev表示上一行前一个元素初始为0。循环出队如果出队元素是0说明本行结束把prev入队即下一行最后一个1换行结束本行。否则输出该元素把prev 当前元素入队并更新prev 当前元素。/* 用队列打印杨辉三角 */ void printYanghui(int n) { CircularQueue q; initCircularQueue(q); /* 第一行 */ circularQueueEnqueue(q, 1); for (int i 1; i n; i) { /* 入队 0 作为行结束标记 */ circularQueueEnqueue(q, 0); int prev 0; while (1) { int cur; circularQueueDequeue(q, cur); if (cur 0) { /* 本行结束入队下一行最后一个 1 */ circularQueueEnqueue(q, prev); printf(\n); break; } printf(%d , cur); circularQueueEnqueue(q, prev cur); prev cur; } } }测试printYanghui(5)输出1 1 1 1 2 1 1 3 3 1 1 4 6 4 1四、完整测试代码把前面的代码按顺序放在同一个.c文件中再添加上main函数即可运行。int main(void) { printf( 循环队列测试 \n); CircularQueue cq; initCircularQueue(cq); for (int i 1; i 5; i) { circularQueueEnqueue(cq, i * 10); } int value; while (circularQueueDequeue(cq, value)) { printf(%d , value); } printf(\n); printf( 链队列测试 \n); LinkQueue lq; initLinkQueue(lq); for (int i 1; i 5; i) { linkQueueEnqueue(lq, i * 10); } while (linkQueueDequeue(lq, value)) { printf(%d , value); } printf(\n); destroyLinkQueue(lq); printf( 杨辉三角测试 \n); printYanghui(6); return 0; }运行结果类似 循环队列测试 10 20 30 40 50 链队列测试 10 20 30 40 50 杨辉三角测试 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1五、循环队列与链队列对比对比项循环队列链队列存储方式数组单链表容量固定可能队满动态一般不会满入队出队复杂度O(1)O(1)内存开销较小连续内存每个节点多一个指针实现难度需要处理取模和队满稍复杂需管理内存适用场景元素数量可预估元素数量变化大六、总结队列是一种典型的“先进先出”结构核心操作都围绕队头和队尾进行。它的实现方式主要有两种循环队列用数组实现通过取模运算形成环解决假溢出问题简单高效但容量固定。链队列用链表实现动态灵活不需要预先指定容量但需要额外指针开销。队列虽然结构简单但在算法和工程中非常常见。进程调度、消息队列、广度优先搜索、缓冲区管理等都离不开队列。如果你正在学习数据结构建议亲手把上面的代码敲一遍再尝试实现用两个栈实现一个队列用两个队列实现一个栈用队列实现二叉树的层次遍历用循环队列模拟生产者—消费者问题用队列求解迷宫最短路径这些练习会让你对队列的理解更加深入。动手敲一遍比看十遍都管用。