企业官网建设流程全解析

队列（Queue）是一种与栈并列的基础线性数据结构。它的核心特点是先进先出，也就是 First In First Out，简称FIFO。

你可以把队列想象成排队买票：先来的人先买到票，后来的人排在队尾。队列只允许在一端插入元素，在另一端删除元素。允许插入的一端叫队尾（rear），允许删除的一端叫队头（front）。

队列的常见操作有：

• enqueue：入队，在队尾插入元素
• dequeue：出队，删除并返回队头元素
• front / peek：查看队头元素，但不删除
• isEmpty：判断队列是否为空
• isFull：判断队列是否已满，主要用于顺序队列
• destroy：销毁队列，释放内存

队列的应用非常广泛，例如：

• 操作系统中的进程调度
• 打印机任务队列
• 消息队列
• 广度优先搜索（BFS）
• 键盘缓冲区
• 网络数据包排队

下面用 C 语言分别实现循环队列和链队列，并给出一个经典应用：用队列打印杨辉三角。

一、循环队列的 C 语言实现

如果用普通数组实现队列，随着不断入队和出队，front 和 rear 会不断后移，最终导致“假溢出”：数组前面明明有空位，但 rear 已经到达末尾，无法再入队。

解决方法是使用循环队列：把数组看作一个环，当 rear 到达末尾时，再回到下标 0。

循环队列通常有两种设计：

1. 牺牲一个存储单元，用(rear + 1) % MAX_SIZE == front判断队满。
2. 增加一个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. 初始化队列，把第一行的1入队。
2. 对于每一行，先在队尾入队一个0作为行结束标记。
3. 维护变量prev，表示上一行前一个元素，初始为0。
4. 循环出队：
   • 如果出队元素是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

五、循环队列与链队列对比

六、总结

队列是一种典型的“先进先出”结构，核心操作都围绕队头和队尾进行。它的实现方式主要有两种：

• 循环队列：用数组实现，通过取模运算形成环，解决假溢出问题，简单高效，但容量固定。
• 链队列：用链表实现，动态灵活，不需要预先指定容量，但需要额外指针开销。

队列虽然结构简单，但在算法和工程中非常常见。进程调度、消息队列、广度优先搜索、缓冲区管理等，都离不开队列。

如果你正在学习数据结构，建议亲手把上面的代码敲一遍，再尝试实现：

1. 用两个栈实现一个队列
2. 用两个队列实现一个栈
3. 用队列实现二叉树的层次遍历
4. 用循环队列模拟生产者—消费者问题
5. 用队列求解迷宫最短路径

这些练习会让你对队列的理解更加深入。动手敲一遍，比看十遍都管用。