队列是一种特殊的线性表，其核心特点是先进先出。
概念及特点：
概念
队列是一种只允许在一端进行插入数据操作，在另一端进行删除数据操作的线性表。进行插入操作的一端被称为队尾（Tail 或 Rear），进行删除操作的一端被称为队头（Head 或 Front）。在日常生活中，我们可以将队列比作排队等候的场景，排在前面的人会先得到服务，新来的人则排在队尾等待。
特点：
先进先出（FIFO）：队列的基本操作是入队和出队。入队操作是在队尾插入一个元素，而出队操作是从队头删除一个元素。这意味着最先进入队列的元素将最先被移除。
操作受限：与普通的线性表不同，队列的操作是受限制的。只能在队尾添加元素，只能在队头删除元素。
两种实现方式：队列可以通过数组或链表来实现。使用数组实现时，可能会遇到数组空间受限的问题，但可以通过循环队列的方式解决。使用链表实现时，可以动态地分配内存，但可能会有额外的内存开销。
动态变化：队列是一种动态的数据结构，其大小可以根据需要动态变化。在入队和出队操作时，队列的大小会相应地增加或减少。
应用广泛：队列在计算机科学中有广泛的应用，如广度优先搜索、任务调度、缓冲处理、线程同步等。
队列的操作
初始化：创建一个空队列。
入队：将一个元素添加到队列的末尾，即队尾。
出队：从队列的开头，即队首，移除元素并返回该元素的值。
返回队首元素：返回队列中的第一个元素的值，但不从队列中删除该元素。
返回队尾元素）：返回队列中的末尾元素的值，但不从队列中删除该元素。
获取队列元素个数：返回队列中的末尾元素的值，但不从队列中删除该元素。
判断队列是否为空： 检查队列中是否没有任何元素。
销毁队列：释放队列所占用的存储空间，使得队列不再存在。
队列的应用
队列的应用场景包括但不限于：
打印机任务队列：打印机按照任务进入队列的顺序进行打印，确保了公平性和先到先服务的原则。
网络请求处理：服务器使用队列来管理并响应客户端的请求，保证了请求按照到达顺序被处理。
生产线作业：在生产线上，队列模型用于管理产品的生产流程，确保每个产品都能按照顺序经过各个加工阶段。
消息队列：在消息传递系统中，消息被放入队列，然后由消费者按照顺序处理，支持异步消息处理和负载均衡。
任务队列：在Web服务器和后台处理系统中，任务队列用于管理和调度异步任务，如发送电子邮件、处理图像等。
优先级队列：在需要优先处理的场景中，如紧急任务或高价值任务，使用优先级队列可以确保这些任务能够优先被执行。
队列的实现
这里我们使用链表来实现队列。
首先创建三个文件：
- Queue.h —— 用于声明函数的头文件。
- Queue.c —— 队列主要函数的实现。
- test.c——测试队列。
队列节点的定义
这里和单链表结构一致。
// 链式结构：表示队列
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
队列指针的定义
将队列的首尾指针封装成一个结构体，可以方便函数调用，统一接口。再使用一个整型size记录元素个数，利于其他函数功能实现。
// 队列的结构
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
初始化
// 初始化队列
void QueueInit(Queue* q)
{
assert(q);//队列必须存在
q->head = q->tail = NULL;
q->size = 0;
}
销毁队列
创建指针循环遍历链表，每次记录下指针的下一个节点，释放指针指向的节点，指针指向下一个节点
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
while (q->head)//释放所有节点
{
QNode* next = q->head->next;
free(q->head);
q->head = next;
}
q->head = q->tail = NULL;
q->size = 0;
}
入队列（队尾插入）
- 情况一：队列为空直接申请新节点给头节点和尾节点；
- 情况二：队列不为空，将新节点接入尾节点后即可。
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)//判定是否申请成功
{
perror("newnode error\n");
exit(1);
}
newnode->data = data;
newnode->next = NULL;
if (q->head == NULL)//对空队列入队的处理
{
q->head = q->tail = newnode;
}
else //对非空队列入队的处理
{
q->tail->next = newnode;
q->tail = newnode;
}
q->size++;
}
出队列（队头删除）
- 情况一：队列只有一个节点，直接释放即可；
- 情况二：队列有多个节点，将头节点的下一个节点保存后释放头节点，在让头节点指向保存的节点。
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(q->head);//队列不能为空
if (q->head == q->tail)//对只有一个元素的队列的出队处理
{
free(q->head);
q->head = q->tail = NULL;
}
else //对存在多个元素的队列的出队处理
{
QNode* next = q->head->next;
free(q->head);
q->head = next;
}
q->size--;
}
获取队头元素
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->head);//队列不能为空
return q->head->data;
}
获取队尾元素
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->head);
return q->tail->data;
}
获取队列元素个数
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
队列判空
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{
assert(q);
return q->size == 0;
}
队列源码
Queue.h
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
// 链式结构：表示队列
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
Queue.c
#include"Queue.h"
// 初始化队列
void QueueInit(Queue* q)
{
assert(q);//队列必须存在
q->head = q->tail = NULL;
q->size = 0;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)//判定是否申请成功
{
perror("newnode error\n");
exit(1);
}
newnode->data = data;
newnode->next = NULL;
if (q->head == NULL)//对空队列入队的处理
{
q->head = q->tail = newnode;
}
else //对非空队列入队的处理
{
q->tail->next = newnode;
q->tail = newnode;
}
q->size++;
}
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(q->head);//队列不能为空
if (q->head == q->tail)//对只有一个元素的队列的出队处理
{
free(q->head);
q->head = q->tail = NULL;
}
else //对存在多个元素的队列的出队处理
{
QNode* next = q->head->next;
free(q->head);
q->head = next;
}
q->size--;
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->head);//队列不能为空
return q->head->data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->head);
return q->tail->data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{
assert(q);
return q->size == 0;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
while (q->head)//释放所有节点
{
QNode* next = q->head->next;
free(q->head);
q->head = next;
}
q->head = q->tail = NULL;
q->size = 0;
}