基本概念
队列（queue）是一种抽象数据类型，与栈相比，队列是一种先进先出(FIFO first in frist out)的线性表，它只允许在表的一端进行插入，而在另一端删除元素。和日常生活中的排队相似，最早进入队列的元素最早离开。在队列中，允许插入元素的一端叫做队尾（rear），允许删除的一端叫做队头(front)。
建立队列必须为其申请静态或者动态的连续存储空间，并设置两个指针进行管理，队尾指针和队头指针，当插入一个元素（入队）时，队尾指针加一，而删除一个元素（出队）时，队头指针减一。
队列的结构如下图所示：
队列
队列的定义及其实现
队列定义
在C语言中，用两个结构体表示链式队列，其中第一个结构体表示队列结点，包含指针域和数据域第二个结构体表示队列，包含一个队头和队尾。如下所示：
typedef struct qNode {
int data;
struct qNode *next;
}qNode,*queuePtr;
typedef struct queueList{
queuePtr front;
queuePtr rear;
}queueList;
接口定义
根据队列特点，队列有以下接口定义，包括初始化，入队，出队，队列情空和队列销毁等，具体如下所示：
#pragma once
#ifndef QUEUE_H
#define QUEUE_H
#define INIT_QUEUE_SIZE 100
#define bool int
#define true 1
#define false 0
//
typedef struct qNode {
int data;
struct qNode *next;
}qNode,*queuePtr;
typedef struct queueList{
queuePtr front;
queuePtr rear;
}queueList;
queueList* initQueue(); //初始化
queueList* enQueue(queueList* queue,int element); //入队
queueList* deQueue(queueList* queue); //出队
void clearQueue(queueList* queue); //清空队列
void destoryQueue(queueList* queue); //销毁队列
void queueTraverse(queueList* queue); //遍历队列
int getLength(queueList* queue); //返回队列长度
int locateQueue(queueList* queue, int element); //查找指定元素的位置
#endif
接口实现
根据队列接口定义，接口实现如下所示：
- 初始化
链式队列的初始化包括整个队列的初始化和队列结点的初始化，并需要将队尾指针指向队头指针，具体实现如下所示
queueList* initQueue()
{
queueList *queue = (queueList*)malloc(sizeof(queueList));
if (!queue)
{
printf("空间分配失败！");
exit(0);
}
queue->front = queue->rear = (queuePtr)malloc(sizeof(qNode));
if (!queue->front)
{
printf("空间分配失败！");
}
queue->front->next = NULL;
return queue;
}
- 入队
入队操作主要是以下步骤：
1). 生成临时结点，并将数据赋值给临时结点的数据域；
2). 队尾指针指向临时结点；
3). 新插入的临时结点变为队尾;
以上过程可以用以下动态图表示：
入队
以上过程可以有以下代码实现
queueList* enQueue(queueList* queue, int element)
{
queuePtr temp=(queuePtr)malloc(sizeof(qNode));
if (!temp)
{
printf("错误！");
exit(0);
}
temp->data = element;
temp->next = NULL;
queue->rear->next = temp;
queue->rear = temp; //新插入的元素自动成为队尾
return queue;
}
-
出队
队列的出队操作主要有以下步骤实现：
1). 将头部赋值给一个临时结点；
2). 将队列头部的后继变成队列的头部
3). 删除临时结点。
可由以下动态图表示这一过程，如下所示：
出队
以上过程可以由以下代码实现
queueList* deQueue(queueList *queue) //出队
{
queuePtr temp = NULL;
if (queue->rear == queue->front)
{
printf("空队列！");
exit(0);
}
temp = queue->front->next; //临时=头部
queue->front->next = temp->next; // 头部 = 头部的后继
if (queue->rear==temp)
{
queue->rear = queue->front;
}
free(temp);
return queue;
}
- 遍历队列
链式队列的遍历与单向链表一样，从队头开始，输出每一个结点的数据，具体代码实现如下所示;
void queueTraverse(queueList* queue)
{
if (queue->rear==queue->front->next)
{
printf("空队列！");
exit(0);
}
queuePtr p;
p = queue->front;
while (queue->rear != p)
{
printf("%d", p->next->data);
p = p->next;
}
}
- 队列长度
队列长度与遍历队列相似，从队头开始，直到队尾结束。具体如下代码所示：
int getLength(queueList* queue)
{
int length = 0;
if (queue->front == queue->rear)
{
length = 0;
}
queuePtr p = queue->front;
while (p != queue->rear)
{
length++;
p = p->next;
}
return length;
}
- 查找元素
查找指定元素在队列中的位置，与求取队列长度类似，从队头开始遍历，若找到指定的元素，则返回计数器的值。具体代码实现如下所示：
int locateQueue(queueList* queue, int element)
{
int index = 0;
if (queue->rear == queue->front)
{
return -1;
}
queuePtr p;
p = queue->front;
while (p != queue->rear)
{
if (p->next->data == element)
{
return index;
}
p = p->next;
index++;
}
return index;
}
- 清空队列
清空队列需要将队尾指针指向队头，并从队头开始，回收每一个结点，具体如下所示：
void clearQueue(queueList* queue)
{
queuePtr p, q;
queue->front = queue->rear;
p = queue->front->next;
queue->front->next = NULL;
while (p)
{
q = p;
p = p->next;
free(q);
}
}
- 销毁队列
队列的销毁主要包括以下步骤：
1). 将队尾指向队头下一个节点的地址（第1个节点）
2). 回收队头
3). 将队头指向队尾（相当于第1个节点变成了队头，然后依次第2个第3个直到没有下一个节点，也就是 Q->front == NULL 的时候）
具体实现如下所示
void destoryQueue(queueList* queue)
{
while (queue->front)
{
queue->rear = queue->front->next; //1)
free(queue->front); //2)
queue->front = queue->rear; //3)
}
free(queue);
}
教材：数据结构（C语言）清华大学出版社
辅助学习网站：https://visualgo.net
