一、队列的概念及结构
1.队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先
进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一 端称为队头
二、队列的实现
队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，
出队列在数组头上出数据，效率会比较低。
// 链式结构：表示队列
typedef struct QListNode
{ struct QListNode* _pNext; QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{ QNode* _front; QNode* _rear;
}Queue;
三、实现队列的函数
1. 初始化队列
void QueueInit(Queue* q);
在函数内部，将队列的 head （队头）和 tail （队尾）指针都初始化为 NULL 。这通常表示一个空队列的状态，即队列中没有任何元素，队头和队尾都不存在指向的有效节点
//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;
}
2.队尾入队列
void QueuePush(Queue* q, QDataType data);
- 首先，使用 malloc 为新的节点 newnode 分配内存，其大小为 QNode 结构体的大小。如果 newnode 为 NULL ，表示内存分配失败，此时打印错误信息并使用 exit(-1) 终止程序。
- 接着，将新节点的 data 成员设置为要插入的数据 x ，并将 next 成员设置为 NULL 。
- 如果队列的尾指针 pq->tail 为 NULL ，说明队列是空队列，此时新节点既是队头也是队尾，将 pq->head 和 pq->tail 都设置为 newnode 。
- 否则，如果队列不为空，将当前队尾节点（ pq->tail ）的 next 指针指向新节点 newnode ，然后更新队尾指针 pq->tail 为 newnode 。
//队尾入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode =(QNode*) malloc(sizeof(QNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;//没有节点，新插入的节点就是头结点if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}
}
3. 队头出队列
void QueuePop(Queue* q);
. 出队操作
- 如果队列中只有一个元素（即 pq->head->next == NULL ），那么这个元素既是队头也是队尾。先释放队头节点的内存（ free(pq->head) ），然后将队头指针 pq->head 和队尾指针 pq->tail 都设置为 NULL ，表示队列变为空队列。
- 如果队列中有多个元素，先保存队头节点的下一个节点（ QNode* next = pq->head->next ），然后释放队头节点（ free(pq->head) ），最后将队头指针 pq->head 更新为保存的下一个节点 next 。
//队头出
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head);//1.一个节点 2.多个节点if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}
}
4.获取队列头部元素
QDataType QueueFront(Queue* q);
. 函数目的
- 这个函数的作用是获取队列的队头元素的数据。
. 输入参数
- 函数接受一个指向 Queue 结构体的指针 pq 。通过 assert(pq) 确保传入的指针不为空，再通过 assert(pq->head) 确保队列不为空，因为从空队列中获取队头元素是无意义的操作。
. 获取数据操作
- 如果前面的断言都通过，直接返回队头节点（ pq->head ）中的数据成员（ data ），其类型为 QDataType 。
//取队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->head);return pq->head->data;
}
5 获取队列队尾元素
QDataType QueueBack(Queue* q);
. 函数目的
- 此函数旨在获取队列中的队尾元素的数据。
. 输入参数
- 接受一个指向 Queue 结构体的指针 pq 。通过 assert(pq) 确保 pq 不为空指针，再通过 assert(pq->head) 确保队列非空，因为空队列不存在队尾元素。
. 获取数据操作
- 在确保队列不为空的情况下，直接返回队尾节点（ pq->tail ）中的 data 成员，其类型为 QDataType 。
//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->head);return pq->tail->data;
}
6. 获取队列中有效元素个数
int QueueSize(Queue* q);
- 首先初始化一个变量 size 为0，用于记录元素个数。然后将一个临时指针 cur 指向队列的队头（ pq->head ）。通过一个 while 循环，只要 cur 不为空（即队列中还有未统计的元素），就将 size 加1，并将 cur 移动到下一个节点（ cur = cur->next ）。当 cur 为空时，循环结束，此时 size 的值就是队列中元素的个数，最后返回 size 。
//取数据个数
int QueueSize(Queue* pq)
{assert(pq);int size = 0;QNode* cur = pq->head;while (cur){++size;cur = cur->next;}return size;
}
7. 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);
- 直接通过检查队列的队头指针（ pq->head ）是否为 NULL 来判断队列是否为空。如果队头指针为 NULL ，则表示队列为空，函数返回 true ；否则返回 false 。
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL;
}
8. 销毁队列
void QueueDestroy(Queue* q);
-首先，将 cur 指针初始化为队列的头节点（ pq - > head ）。然后，通过一个 while 循环遍历队列中的每个节点。在循环中，先保存当前节点 cur 的下一个节点指针（ next ），然后使用 free(cur) 释放当前节点的内存，最后将 cur 指针移动到下一个节点（ cur = next ）。当循环结束时，所有的节点都被释放。最后，将队列的 head 和 tail 指针都设置为 NULL 。
//摧毁函数
void QueueDestory(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next =cur->next;free(cur);cur = next;} pq->head = pq->tail = NULL;
}
