队列：排队规则、先进先出

文章目录

• • 引入：队列解决的是“按到达顺序服务”
  • 一、链队列的结构：节点串起来，两个指针守住两端
  • 二、根据功能使用C语言实现
  • • 1. 初始化：三个成员先指向“空状态”
    • 2. 入队：首节点和普通节点是两种情况
    • 3. 出队：真正关键的是只剩一个节点
    • 4. 获取队头队尾元素
    • 5. 查看元素数量与销毁链表
  • 三、运行测试
  • 四、复杂度与内存代价
  • 五、扩展练习
  • • 1. 手动追踪队列的两端
  • 六、完整参考代码
  • • `Queue.h`
    • `Queue.c`
    • `test.c`

引入：队列解决的是“按到达顺序服务”

在实际排队买票场景中，先到的人通常先办理；打印机收到多个任务时，也常按提交顺序处理。若后来的人可以随意插队，系统就很难预测，也不公平。队列（queue）把这种规则抽象成一种线性数据结构：先进入的元素先离开，即 FIFO（First In, First Out，先进先出）。

队列有两个操作端：元素从队尾（rear）加入，从队头（front）删除。注意“加入”和“删除”发生在不同位置，这正是它与栈的关键区别。 队列的常见操作包括：

• QueuePush：在队尾入队。
• QueuePop：从队头出队。
• QueueFront：查看队头元素，不删除。
• QueueBack：查看队尾元素，不删除。
• QueueSize：获取有效元素个数。
• QueueEmpty：判断队列是否为空。

队列也只是一个抽象接口，可以用数组实现，也可以用链表实现。本篇采用的是带头尾指针的链队列实现。

一、链队列的结构：节点串起来，两个指针守住两端

本篇同样采用三个文件Queue.h、Queue.c、test.c来实现链队列。

• Queue.h： 链队列节点定义以及功能函数声明。
• Queue.c： 链队列各功能函数具体实现。
• test.c： 测试功能有效性。

定义链队列节点与结构：

typedef int QDataType;

//定义队列节点,链式结构
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;

//队列结构（队头队尾）
typedef struct Queue
{
QNode* front; //队头指针
QNode* rear; //队尾指针
int size; //元素数量
}Queue;

当队列保存 10、20、30 时，逻辑结构是：

front rear
│ │
▼ ▼
[10 | next] ──▶ [20 | next] ──▶ [30 | NULL]
size = 3

front 指向第一个要被服务的节点，rear 指向最后一个刚进入的节点。因为两端地址都保存着，所以队尾追加不需要从头遍历整条链表，队头删除也能直接定位。

链队列实现时须保证以下规则：

二、根据功能使用C语言实现

1. 初始化：三个成员先指向“空状态”

使用QueueInit()函数初始化队列，但不在初始化时申请节点：

//初始化队列
void QueueInit(Queue* q)
{
assert(q);
q->front = NULL;
q->rear = NULL;
q->size = 0;
}

链队列的空间随入队动态申请，因此空队列本身只需要两个个指针和一个计数器。

2. 入队：首节点和普通节点是两种情况

新节点先写入数据并把 next 设为 NULL，因为它会成为新的队尾：

//队尾入队列
void QueuePush(Queue* q, QDataType x)
{
assert(q);
//申请节点
QNode* newNode = (QNode*)malloc(sizeof(QNode));
if (newNode == NULL)
{
perror("QueuePush()::malloc() fail");
return;
}
newNode->data = x;
newNode->next = NULL;
//判断当前队列是否有节点
if (q->rear == NULL)
{
q->rear = q->front = newNode;
}
else
{
q->rear->next = newNode;
q->rear = newNode;
}
q->size++;
}

第一次入队时，队头和队尾必须同时指向新节点；之后才是“旧队尾连到新节点，再移动 rear”的普通流程。若忘记处理第一次入队，front 仍为空，后续 QueueFront 就无法工作。

3. 出队：真正关键的是只剩一个节点

普通出队只需保存下一个节点、释放旧队头、移动 front：

//队头出队列
void QueuePop(Queue* q)
{
assert(q);
if (QueueEmpty(q))
{
printf("当前队列为空，无法出队列！！\\n");
return;
}
else
{
//处理只有单个节点的情况
if (q->front->next == NULL)
{
free(q->front);
q->front = q->rear = NULL;
}
//处理多个节点
else
{
QNode* next = q->front->next;
free(q->front);
q->front = next;
}
}
q->size—;
}

//检测队列是否为空
bool QueueEmpty(Queue* q)
{
assert(q);
if (q->front == NULL)
return true;
else
return false;
}

最后一个节点出队后，front 变成 NULL，此时必须让 rear 也变成 NULL，否则 rear 会成为悬空指针：它指向已经释放的内存，下一次入队或取队尾都可能出错。

4. 获取队头队尾元素

在获取队头队尾元素值时，仅读队头队尾指针的指向，不执行任何删除插入与改变指向的操作：

//获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
if (QueueEmpty(q))
{
printf("当前队列为空，无法获取！！\\n");
return;
}
else
{
return q->front->data;
}
}
//获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
if (QueueEmpty(q))
{
printf("当前队列为空，无法获取！！\\n");
return;
}
else
{
return q->rear->data;
}
}

5. 查看元素数量与销毁链表

由于我们在设计队列结构时为其设置了记录元素数量的变量size，所以函数QueueSize()可直接返回队列结构中size的值：

//获取队列有效元素个数
int QueueSize(Queue* q)
{
assert(q);

return q->size;
}

//销毁队列
void QueueDestroy(Queue* q)
{
assert(q);

QNode* cur = q->front;
while (cur)
{
QNode* next = cur->next;
free(cur);

cur = next;
}
q->front = q->rear = NULL;
q->size = 0;
}

销毁函数则从队头开始逐个释放：先保存 next，再释放当前节点，最后把队头、队尾和数量恢复为空状态。这种“先记住下一跳，再释放当前节点”的顺序与链表中的一样不能颠倒。

三、运行测试

在test.c文件中编写测试代码，初始化队列后入队1， 2， 3， 4，然后依次取出队头元素并打印，同时统计当前的元素个数再出队尾，最后销毁：

void test()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);

while (!QueueEmpty(&q))
{
printf("队头元素：%d ", QueueFront(&q));
printf("元素数量：%d \\n", QueueSize(&q));
QueuePop(&q);
}

QueueDestroy(&q);
}

运行结果：

四、复杂度与内存代价

链队列不会像固定数组那样因为“容量满”而整体搬迁，元素数量可以按需增长；代价是每个节点多了一个 next 指针，还要承担多次 malloc/free 的管理成本。若任务数量已知且频繁访问，连续数组可能有更好的缓存局部性；若数量变化大且需要两端 O(1) 操作，链队列则更加灵活。

五、扩展练习

1. 手动追踪队列的两端

操作序列为：Push(7)、Push(9)、Pop()、Push(4)、Pop()、Pop()。写出每一步的队头、队尾和 size。

思路： 入队只改变 rear，出队只改变 front；删除前要先记住当前队头。

参考答案：

• Push(7)：队头 7，队尾 7，size=1。
• Push(9)：队头 7，队尾 9，size=2。
• Pop()：队头 9，队尾 9，size=1。
• push(4)：队头 9，队尾 4，size=2。
• 两次 Pop() 后为空：front=NULL、rear=NULL、size=0。

六、完整参考代码

Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int QDataType;

//定义队列节点,链式结构
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;

//队列结构（队头队尾）
typedef struct Queue
{
QNode* front; //队头指针
QNode* rear; //队尾指针
int size; //元素数量
}Queue;

//初始化队列
void QueueInit(Queue* q);

//队尾入队列
void QueuePush(Queue* q, QDataType x);
//队头出队列
void QueuePop(Queue* q);

//获取队列头部元素
QDataType QueueFront(Queue* q);
//获取队列队尾元素
QDataType QueueBack(Queue* q);
//获取队列有效元素个数
int QueueSize(Queue* q);
//检测队列是否为空
bool QueueEmpty(Queue* q);

//销毁队列
void QueueDestroy(Queue* q);

Queue.c

#include "Queue.h"

//初始化队列
void QueueInit(Queue* q)
{
assert(q);
q->front = NULL;
q->rear = NULL;
q->size = 0;
}

//队尾入队列
void QueuePush(Queue* q, QDataType x)
{
assert(q);
QNode* newNode = (QNode*)malloc(sizeof(QNode));
if (newNode == NULL)
{
perror("QueuePush()::malloc() fail");
return;
}
newNode->data = x;
newNode->next = NULL;
if (q->rear == NULL)
{
q->rear = q->front = newNode;
}
else
{
q->rear->next = newNode;
q->rear = newNode;
}
q->size++;
}

//队头出队列
void QueuePop(Queue* q)
{
assert(q);
if (QueueEmpty(q))
{
printf("当前队列为空，无法出队列！！\\n");
return;
}
else
{
//处理只有单个节点的情况
if (q->front->next == NULL)
{
free(q->front);
q->front = q->rear = NULL;
}
//处理多个节点
else
{
QNode* next = q->front->next;
free(q->front);
q->front = next;
}
}
q->size—;
}

//获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
if (QueusEmpty(q))
{
printf("当前队列为空，无法获取！！\\n");
return;
}
else
{
return q->front->data;
}
}
//获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
if (QueueEmpty(q))
{
printf("当前队列为空，无法获取！！\\n");
return;
}
else
{
return q->rear->data;
}
}

//获取队列有效元素个数
int QueueSize(Queue* q)
{
assert(q);

return q->size;
}

//检测队列是否为空
bool QueueEmpty(Queue* q)
{
assert(q);
if (q->front == NULL)
return true;
else
return false;
}

//销毁队列
void QueueDestroy(Queue* q)
{
assert(q);

QNode* cur = q->front;
while (cur)
{
QNode* next = cur->next;
free(cur);

cur = next;
}
q->front = q->rear = NULL;
q->size = 0;
}

test.c

#include "Queue.h"

void test()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);

while (!QueueEmpty(&q))
{
printf("队头元素：%d ", QueueFront(&q));
printf("元素数量：%d \\n", QueueSize(&q));
QueuePop(&q);
}

QueueDestroy(&q);
}

int main()
{
test();
return 0;
}