数据结构（4）—队列
队列（queue）也是一种重要的线性结构。与栈相同，实现一个队列同样需要顺序表或者链表为基础；与栈不同，队列是一种先进先出（first in first out，FIFO）的线性表。在队列中，允许插入数据的一端叫做队尾（rear），允许数据离开的一端叫作队头（front）。
在操作上有特殊的限制：数据只能从队尾进入队列，只能从队头取出队列。
队列的示意图，如下：
1. 链队列
队列既可以用链表实现，也可以用顺序表实现。这里重点介绍用链表实现一个队列，这样的队列简称为链队列。
队列结构定义如下：
typedef int elemType_t; ///< 此处以int为例
// 结点参数
typedef struct node_t
{
elemType_t data;
struct node_t *next;
} node_t; ///< 定义结点
// 队列参数
typedef struct
{
node_t* front; ///< 队头指针
node_t* rear; ///< 队尾指针
} queue_t; ///< 定义队列首先定义一个队列元素 node_t 结构体，因为要定义一个链队列，因此每个队列元素 node_t 不但要包括数据本身，还必须包括一个指针域，用来存放后继元素的指针（地址）。
定义一个 queue_t 类型，该类型也是一个结构体类型，包含两个域。front 域用来指向队列的头，即用来存放队头元素地址，它是一个node_t* 类型的变量； 同理，rear 域用来指向队列的尾。
1.1 创建一个队列
代码描述如下：
/**
* @brief 创建一个空队列
*
* @param *p_queue: 所要操作的队列
* @return 0-初始化失败；1-初始化成功；
*
*/
int init_queue(queue_t *p_queue)
{
//创建一个头结点，队头队尾指针指向该结点
p_queue->rear = (node_t*)malloc(sizeof(node_t));
p_queue->front = p_queue->rear;
//创建头结点失败
if(!p_queue->front)
{
return 0;
}
// 头结点指针域置为NULL
p_queue->front->next = NULL;
return 1;
}创建一个队列需要完成两个步骤：
（1）通过 malloc() 函数创建一个 node_t* 类型的结点，并将 p_queue->front 和 p_queue->rear 指针分别指向该头结点。
（2）将该头结点的指针域 next 置为 NULL。
创建的空队列，其状态图如下：
1.2 入队列操作
入队列操作就是将一个 node_t 类型的元素从队列的尾部进入队列。每当将一个队列元素插入队列，队列的尾指针都要进行修改（因此元素从队列的尾部进入队列），队头的指针不会发生改变。
入队列操作的代码描述如下：
/**
* @brief 队列中添加一个结点
*
* @param *p_queue: 所要操作的队列
* @param e: 所添加的结点内容
* @return 0-失败；1-成功；
*
*/
int put_queue(queue_t *p_queue, elemType_t e)
{
node_t *node_p;
//创建一个队列元素结点
node_p = (node_t*)malloc(sizeof(node_t));
node_p->data = e;
node_p->next = NULL;
if(!p_queue->front)
{
free(node_p);
printf("队列不存在\n");
return 0;
}
p_queue->rear->next = node_p;
p_queue->rear = node_p;
return 1;
}首先，使用 malloc() 创建一个 node_t * 类型的元素结点。然后，将数据 e 赋值给该元素结点的数据域 node_p->data，并将该元素结点的指针域 next 置为NULL。
操作示意图，如下：
最后，通过语句：
//原队尾next指针需要指向新结点 p_queue->rear->next = node_p; //更新队尾结点 p_queue->rear = node_p;
将该元素结点从队列的尾部插入队列。
操作示意图，如下：
1.3 出队列操作
出队列操作是将队列中的元素从队列的头部移出。每当从队列中移出数据时，队头指针不发生改变，但是头结点的 next 指针发生改变。队尾指针只有在原队列中只有一个元素，即队头等于队尾的情况下才会改变，否则不改变。
出队列代码描述，如下：
/**
* @brief 从队列中取出结点数据
*
* @param *p_queue: 所要操作的队列
* @param *e: 存放取出结点的数据内容
* @return 0-失败；1-成功；
*
*/
int get_queue(queue_t *p_queue, elemType_t *e)
{
node_t *p_node;
// 队列为空，直接返回
if(p_queue->front == p_queue->rear)
{
printf("异常退出：所要删除的队列为空！!\n");
return 0;
}
// 取一个结点
p_node = p_queue->front->next;
// 取出队头的数据内容
*e = p_node->data;
// 更新队列指针
p_queue->front->next = p_node->next;
// 若队列头尾相同，修改队尾指针
if(p_queue->rear == p_node)
{
p_queue->rear = p_queue->front;
}
free(p_node);
return 1;
}首先，判断队列是否为空，如果是空队列则返回，程序终止执行，否则继续执行。之后，先将队头元素（p_queue->front->nex 指向的队列元素结点）的指针赋值给 p_node，这样 p_node 就指向了队列的第一个元素。之后，将 p->data 赋值给变量 *e 。
最后通过语句：
// 更新队列头为，原队列头的下一个结点
p_queue->front->next = p_node->next;
// 若队列头尾相同，修改队尾指针
if(p_queue->rear == p_node)
{
p_queue->rear = p_queue->front;
}
free(p_node);将队列的队头元素删除。需要注意一点，如果原队列中队头就是队尾，则说明删除队头元素后该队列为空，因此队尾指针 q->rear 必须修改，应当赋值为 q->front ，此时队列变为空，队头队尾指针同时指向头结点。
原队列不止一个元素情况下，出队列操作示意图如下：
原队列只有一个元素情况下，出队列操作示意图如下：
1.4 销毁一个队列
由于链队列建立在内存的动态区，因此当一个队列不再使用时，应当及时销毁，以避免占用过多的内存空间。
代码如下：
/**
* @brief 销毁一个链表
*
* @param *p_queue: 所要操作的队列
* @return 无；
*
*/
void destroy_queue(queue_t* p_queue)
{
while(p_queue->front)
{
// 队头指针指向下一个结点
p_queue->rear = p_queue->front->next;
// 释放内存
free(p_queue->front);
p_queue->front = p_queue->rear;
}
}通过以上代码可以完整销毁一个队列，最终 q->rear 和 q->front 都为空。
1.5 示例
#include <stdio.h>
#include <stdlib.h>
typedef int elemType_t; ///< 此处以int为例
// 结点参数
typedef struct node_t
{
elemType_t data;
struct node_t *next;
} node_t; ///< 定义结点
// 队列参数
typedef struct
{
node_t* front; ///< 队头指针
node_t* rear; ///< 队尾指针
} queue_t; ///< 定义队列
/**
* @brief 创建一个空队列
*
* @param *p_queue: 所要操作的队列
* @return 0-初始化失败；1-初始化成功；
*
*/
int init_queue(queue_t *p_queue)
{
//创建一个头结点，队头队尾指针指向该结点
p_queue->rear = (node_t*)malloc(sizeof(node_t));
p_queue->front = p_queue->rear;
//创建头结点失败
if(!p_queue->front)
{
return 0;
}
// 头结点指针域置为NULL
p_queue->front->next = NULL;
return 1;
}
/**
* @brief 队列中添加一个结点
*
* @param *p_queue: 所要操作的队列
* @param e: 所添加的结点内容
* @return 0-失败；1-成功；
*
*/
int put_queue(queue_t *p_queue, elemType_t e)
{
node_t *node_p;
//创建一个队列元素结点
node_p = (node_t*)malloc(sizeof(node_t));
node_p->data = e;
node_p->next = NULL;
if(!p_queue->front)
{
free(node_p);
printf("队列不存在\n");
return 0;
}
p_queue->rear->next = node_p;
p_queue->rear = node_p;
return 1;
}
/**
* @brief 从队列中取出结点数据
*
* @param *p_queue: 所要操作的队列
* @param *e: 存放取出结点的数据内容
* @return 0-失败；1-成功；
*
*/
int get_queue(queue_t *p_queue, elemType_t *e)
{
node_t *p_node;
// 队列为空，直接返回
if(p_queue->front == p_queue->rear)
{
printf("异常退出：所要删除的队列为空！!\n");
return 0;
}
// 取一个结点
p_node = p_queue->front->next;
// 取出队头的数据内容
*e = p_node->data;
// 更新队列指针
p_queue->front->next = p_node->next;
// 若队列头尾相同，修改队尾指针
if(p_queue->rear == p_node)
{
p_queue->rear = p_queue->front;
}
free(p_node);
return 1;
}
/**
* @brief 销毁一个链表
*
* @param *p_queue: 所要操作的队列
* @return 无；
*
*/
void destroy_queue(queue_t* p_queue)
{
while(p_queue->front)
{
// 队头指针指向下一个结点
p_queue->rear = p_queue->front->next;
// 释放内存
free(p_queue->front);
p_queue->front = p_queue->rear;
}
}
int main()
{
queue_t q_link;
node_t *p_node;
int i = 0;
// 1.创建链表
printf("\n1.测试创建列表：\n");
init_queue(&q_link);
i = 0;
if(q_link.front == q_link.rear)
{
printf("空队列创建成功 -> %d, %d\n", q_link.front->next, q_link.rear->next);
}
// 2.插入结点
printf("\n2.测试队列添加结点：\n");
put_queue(&q_link, 10);
put_queue(&q_link, 20);
put_queue(&q_link, 30);
put_queue(&q_link, 40);
put_queue(&q_link, 40);
i = 0;
p_node = q_link.front;
while(q_link.rear != p_node)
{
p_node = p_node->next;
printf("结点%d，对应数据%d\n", i, p_node->data);
i++;
}
// 3.删除结点
printf("\n3.测试删除队列结点：\n");
for(i = 0; i < 2; i++)
{
elemType_t elem;
get_queue(&q_link, &elem);
printf("结点%d，取出数据%d\n", i, elem);
}
i = 0;
p_node = q_link.front;
printf("\n4.最终队列数据为：\n");
while(q_link.rear != p_node)
{
p_node = p_node->next;
printf("结点%d，对应数据%d\n", i, p_node->data);
i++;
}
// 4.释放链表
printf("\n5.测试释放结点：\n");
destroy_queue(&q_link);
if(q_link.rear == q_link.front)
printf("释放队列成功\n");
return 0;
}2. 循环队列
所谓循环队列就是该队列与传统链队列不同，队列的空间是可以循环使用的。循环队列一般有固定的容量，与传统的队列相同，队列元素必须从队尾进入队列，必须从队头出队列。
如果在使用队列的过程中，不断有元素入队列，同时又不断有元素出队列，那么对于一般的链队列，只要队列不为空，其队头指针 front 和 队尾指针 rear 都不会发生改变，只是头结点的 next 指针和队尾的前一个结点的 next 指针会发生变化，而且链队列的长度也会随着入队列元素不断变化。
而对于循环队列，它的容量是固定的，并且他的队头指针和队尾指针都可以随着元素入出队列而发生改变，这样循环队列逻辑上就好像是一个环形的存储空间，主要队列中还有空单元未使用，就可以向队列中存放元素。
由于循环队列的这一特性，循环队列可作为缓冲池存储结果来存放数据，循环队列逻辑结构如下：
如上图所示，图（a）为一个循环队列，该队列总容量为8B，实际长度为5B。为了方便操作，这里约定循环队列队列头指针 front 始终指向队头元素，队尾指针 rear 始终指向队尾元素的下一个空间。因此这里队头元素为 f，队尾元素为 b，该队列的实际可用空间为 7 B。
图（b）为将队列图（a）的队首元素 f 出队列，将字符 a 入队列后，该队列情形。从图（b）中可以看出，对于循环队列，入队列操作就是向 rear 指向的空间赋值，然后指针 rear 再指向队尾元素的下一个空间。出队列操作就是将队头指针 front 向上移动一个单元。整个循环队列逻辑上就是一个首尾相接的环形缓冲区。
2.1 循环队列的实现
循环队列的几种状态图，如下：
图（a）表示初始化一个循环队列，在内存中开辟一个 7B 大小的连续存储单元。这就标志着该循环队列最多存放 6B 元素，因为 rear 指针始终指向队尾元素的下一个单元。最后的循环队列队头指针 front 和队尾指针 rear 都指向 0 号单元。
图（b）表示向队列中存放了两个元素a、b。字符 a、b入队列的过程是：先将字符a存放到队尾指针 rear 指向的空间，rear 指针加 1，这样字符 a 入队列；同样地过程，将字符 b 存放到队尾指针 rear 指向的空间，rear 指针再加 1，这样字符 b 入队列。队尾指针 rear 始终指向队尾元素的下一个单元。
图（c）表示图（b）所示的队列将队首元素 a 出队列后队列的状态。队首元素 a 出队列的过程：将 front 所指向的元素返回，再将指针 front 加 1。队头指针 front 始终指向队头元素。
图（d）表示在图（c）所示队列的基础上，将 c、d、e、f、g 这5个字符元素入队列后队列的状态。此时队尾指针 rear 重新指向 0 号单元，这是因为 rear 不断加1后超出了循环队列的地址范围，于是采取取模运算处理的结果。因此，无论是入队列的 rear 加 1 操作，还是出队列的 front 加 1 操作，实际上就是模加操作，即：（rear+1）% 7和 （front + 1）%7。正是因为这样，才能在线性的内存空间上模拟出逻辑上的循环的队列。
2.2 定义一个循环队列
#define MAX_QUEUE_SIZE 6
typedef int elemType_t; ///< 此处以int为例
// 队列参数
typedef struct
{
elemType_t *base; ///< 队列基地址
int front; ///< 队头指针
int rear; ///< 队尾指针
} cycle_queue_t; ///< 定义队列2.3 初始化一个循环队列
/**
* @brief 初始化一个循环队列
*
* @param *p_queue: 所要操作的队列指针
* @return 0-初始化失败；1-初始化成功；
*
*/
int init_cycle_queue(cycle_queue_t *p_queue)
{
p_queue->base = (elemType_t *)malloc(MAX_QUEUE_SIZE*sizeof(elemType_t));
// 内存分配失败
if(!p_queue -> base)
{
return 0;
}
p_queue->front = p_queue->rear = 0;
return 1;
}2.4 入队列操作
/**
* @brief 入队列
*
* @param *p_queue: 所要操作的队列指针
* @param e: 所添加的数据内容
* @return 0-失败；1-成功；
*
*/
int en_cycle_queue(cycle_queue_t *p_queue, elemType_t e)
{
if(((p_queue->rear + 1) % MAX_QUEUE_SIZE) == p_queue->front)
{
printf("异常：队列已满！\n");
return 0;
}
p_queue->base[p_queue->rear] = e;
p_queue->rear = (p_queue->rear + 1) % MAX_QUEUE_SIZE;
return 1;
}2.5 出队列操作
/**
* @brief 出队列
*
* @param *p_queue: 所要操作的队列指针
* @param *e: 取出的结点数据内容
* @return 0-失败；1-成功；
*
*/
int de_cycle_queue(cycle_queue_t *p_queue, elemType_t *e)
{
// 队列为空
if(p_queue->front == p_queue->rear)
{
printf("队列为空！\n");
return 0;
}
// 取出队头元素
*e = p_queue->base[p_queue->front];
// 队头指针加1
p_queue->front = (p_queue->front + 1) % MAX_QUEUE_SIZE;
return 1;
}2.6 示例
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 6
typedef int elemType_t; ///< 此处以int为例
// 队列参数
typedef struct
{
elemType_t *base; ///< 队列基地址
int front; ///< 队头指针
int rear; ///< 队尾指针
} cycle_queue_t; ///< 定义队列
/**
* @brief 初始化一个循环队列
*
* @param *p_queue: 所要操作的队列指针
* @return 0-初始化失败；1-初始化成功；
*
*/
int init_cycle_queue(cycle_queue_t *p_queue)
{
p_queue->base = (elemType_t *)malloc(MAX_QUEUE_SIZE*sizeof(elemType_t));
// 内存分配失败
if(!p_queue -> base)
{
return 0;
}
p_queue->front = p_queue->rear = 0;
return 1;
}
/**
* @brief 入队列
*
* @param *p_queue: 所要操作的队列指针
* @param e: 所添加的数据内容
* @return 0-失败；1-成功；
*
*/
int en_cycle_queue(cycle_queue_t *p_queue, elemType_t e)
{
if(((p_queue->rear + 1) % MAX_QUEUE_SIZE) == p_queue->front)
{
printf("异常：队列已满！\n");
return 0;
}
p_queue->base[p_queue->rear] = e;
p_queue->rear = (p_queue->rear + 1) % MAX_QUEUE_SIZE;
return 1;
}
/**
* @brief 出队列
*
* @param *p_queue: 所要操作的队列指针
* @param *e: 取出的结点数据内容
* @return 0-失败；1-成功；
*
*/
int de_cycle_queue(cycle_queue_t *p_queue, elemType_t *e)
{
// 队列为空
if(p_queue->front == p_queue->rear)
{
printf("队列为空！\n");
return 0;
}
// 取出队头元素
*e = p_queue->base[p_queue->front];
// 队头指针加1
p_queue->front = (p_queue->front + 1) % MAX_QUEUE_SIZE;
return 1;
}
/**
* @brief 打印队列内容
*
* @param *p_queue: 所要操作的队列
* @return 0-失败；1-成功；
*
*/
int dump_cycle_queue(cycle_queue_t *p_queue)
{
int i, start_pos = 0;
int valid_len = 0;
if(p_queue->front == p_queue->rear) // 队列为空
{
printf("队列为空！\n");
return 0;
}
else if(p_queue->front > p_queue->rear) // 队列已转圈
{
int pos = 0;
valid_len = MAX_QUEUE_SIZE + p_queue->rear - p_queue->front;
start_pos = p_queue->front;
for(i = 0; i < valid_len; i++)
{
pos = (start_pos + i) % MAX_QUEUE_SIZE;
printf("结点数据：%d\n", p_queue->base[pos]);
}
}
else // 循环未转圈
{
valid_len = p_queue->rear - p_queue->front;
start_pos = p_queue->front;
for(i = 0; i < valid_len; i++)
{
printf("结点数据：%d\n", p_queue->base[start_pos + i]);
}
}
return 1;
}
int main()
{
cycle_queue_t q_link;
elemType_t elem;
int i = 0;
// 1.创建链表
printf("\n1.测试创建循环队列：\n");
if(init_cycle_queue(&q_link))
{
printf("创建循环队列成功！\n");
}
// 2.插入结点
printf("\n2.测试队列添加结点：\n");
en_cycle_queue(&q_link, 10);
en_cycle_queue(&q_link, 20);
en_cycle_queue(&q_link, 30);
en_cycle_queue(&q_link, 40);
en_cycle_queue(&q_link, 50);
dump_cycle_queue(&q_link);
// 3.删除结点
printf("\n3.测试删除队列结点：\n");
de_cycle_queue(&q_link, &elem);
printf("删除结点：%d\n", elem);
de_cycle_queue(&q_link, &elem);
printf("删除结点：%d\n", elem);
printf("\n新的队列数据：\n");
dump_cycle_queue(&q_link);
// 4.再次插入结点
printf("\n4.测试再次添加结点：\n");
en_cycle_queue(&q_link, 60);
en_cycle_queue(&q_link, 70);
dump_cycle_queue(&q_link);
}示例运行结果如下：
参考来源：
1.《妙趣横生的算法（C语言实现）》 杨峰 编著