一. 队列的概念
队列是一种特殊的线性表，用于存储元素，并且按照先进先出(First In First Out)的顺序进行管理，这意味着最先加入队列的元素将会是最先从队列中被移除的元素
队列的原型：只允许在一端进行插入数据的操作，在另一端进行删除数据的操作
队列的原则：队列中的元素遵循先进先出的原则
队列的两个经典操作：
入队列：队列的插入操作叫做入队列，进行操作的一端称为队尾
出队列：队列的删除操作叫做出队列，进行操作的一端称为队头
二. 队列的结构
现实中的队列
当我们去银行取款机排队取钱的过程就是队列，我们从队尾进入，依次取钱，取完钱之后从队头离开
三. 队列的实现
队列的实现有两种方式
一. 用数组实现
优点
- 快速访问：数组允许随机访问，可以快速访问任何一个元素，特别是在入队和出队操作时，可以直接通过索引来访问队头和队尾。
- 内存连续：数组是连续内存的数据结构，这可能有助于提高缓存效率，因为连续的内存块更有可能一起被加载到CPU缓存中。
缺点
- 固定大小：数组的大小在初始化时固定，这意味着队列的容量有一个上限。如果队列满了，就需要执行昂贵的数组扩展操作，通常涉及分配一个更大的数组并复制现有元素。
- 空间浪费：在使用数组实现循环队列时，即使数组中还有空间，队列也可能报告已满，这是因为循环使用的逻辑问题导致的空间利用不充分。
二. 用链表实现
优点
- 动态大小：链表提供了动态大小的能力，队列可以根据需要增长和缩小，不存在固定的容量限制。
- 内存利用率高：链表只在需要时分配内存，且只为实际存储的元素分配，这减少了内存浪费。
缺点
- 内存分配开销：链表的每个新元素都可能需要内存分配（除非使用内存池技术），这可能比连续的内存分配（如数组）更昂贵。
- 访问速度慢：链表不支持随机访问，访问任何位置的元素都需要从头开始遍历，这使得某些操作比数组慢。
- 额外内存需求：每个链表节点需要额外的内存空间来存储指向下一个节点的指针，这增加了每个元素的内存开销。
总结：不过整体上使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。下面我将用链表的结构来实现队列
1. 初始化队列
1.1 链式结构表示队列
在使用链表实现队列的时候，定义一个节点结构QNode，为队列中的每个元素提供一个容器，使得元素能连接起来
typedef int QDataType;
typedef struct QListNode //定义一个节点
{
struct QListNode* pNext; //指针域
QDataType data; //数据域
}QNode;1.2 队列的结构
普通链表通常只需要一个头指针来访问链表的起始位置，而队列为了支持高效的入队和出队操作，需要同时维护队头和队尾两个指针，我们通常会定义一个额外的结构体，这个结构体包括了指向队头的指针和指向队尾的指针。
typedef struct Queue
{
QNode* front; // 队头指针
QNode* rear; // 队尾指针
} Queue; // 队列结构体别名
1.3 队列的初始化
接下来就是创建一个初始化函数，对队列里的元素进行初始化
void QueueInit(Queue* q)
{
assert(q); // 断言队列指针q不为NULL，确保不对NULL指针进行操作，提高程序的安全性。
q->front = NULL; // 将队列的前端指针设置为NULL，表示队列为空，即队列中没有元素。
q->rear = NULL; // 将队列的后端指针也设置为NULL，与队列为空的状态一致，因为没有元素可以指向。
}
2. 销毁队列
从对头开始，进行释放空间，最后让队头队尾指针置为NULL
void QueueDestory(Queue* q)
{
assert(q); // 断言队列指针不为空
QNode* cur = q->front; // 创建一个变量，从队头开始销毁队列节点
while (cur)
{
QNode* next = cur->next; // 保存当前节点的下一个节点
free(cur); // 释放当前节点的内存
cur = next; // 移动到下一个节点
}
q->front = NULL; // 将队列的头指针置为空，表示队列已被销毁
q->rear = NULL; // 将队列的尾指针置为空，表示队列已被销毁
}
3. 入队列
申请一个新的节点链接到尾部，然后让尾指针，指向新节点 需要注意的是：若队列中无数据，我们需要让队头和队尾都指向这个新的节点
void QueuePush(Queue* q, QDataType x)
{
assert(q); // 断言队列指针不为空
QNode* newnode = (QNode*)malloc(sizeof(QNode)); // 分配新节点的内存空间
if (newnode == NULL)
{
printf("malloc fail\n"); // 如果内存分配失败，打印错误信息
exit(-1); // 退出程序
}
newnode->data = x; // 将数据存储到新节点中
newnode->next = NULL; // 新节点的下一个节点指针为空
if (q->front == NULL) // 如果队列为空
{
q->front = newnode; // 将新节点设置为队列的头节点
q->rear = newnode; // 将新节点设置为队列的尾节点
}
else
{
q->rear->next = newnode; // 将新节点链接到队列尾部
q->rear = newnode; // 更新队列的尾节点为新节点
}
}
4. 出队列
释放队头的节点，并将队头更新到下一个元素。需要注意的是，如果队列中只有一个数据，在释放了队头的节点之后，要让队尾和队头的指针置空
void QueuePop(Queue* q)
{
assert(q); // 断言以确保队列指针 'q' 不是 NULL，保证这是一个有效的指针。
assert(!QueueEmpty(q)); // 断言以确保队列不为空，仅当队列非空时才能进行出队操作。
// 如果队列中只有一个节点，即队首和队尾是同一个节点
if (q->front->next == NULL)
{
q->front = NULL; // 将队首指针置为空
q->rear = NULL; // 将队尾指针置为空，因为队列要变为空队列
}
else
{
// 如果队列中不止一个节点，则将队首节点出队
QNode* head = q->front->next; // 临时保存新的队首节点
free(q->front); // 释放当前的队首节点的内存
q->front = head; // 更新队首指针为新的队首节点
}
}
5. 获取队列的队头元素
返回队头指针指向的数据即可
QDataType QueueFront(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));//检测队列是否为空
return q->front->data;//返回队头指针指向的数据
}6.获取队列的队尾元素
返回队尾指针指向的数据即可
QDataType QueueBack(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));//检测队列是否为空
return q->rear->data;//返回队尾指针指向的数据
}7. 检测队列是否为空
判断队头的指针是否指向空
bool QueueEmpty(Queue* q)
{
assert(q);
return q->front == NULL;
}8. 获取队列中有效元素个数
队列中有效元素个数，即队列中的结点个数。我们只需遍历队列，统计队列中的节点数并返回即可
int QueueSize(Queue* q)
{
assert(q); // 断言以确保队列指针 'q' 不是 NULL，保证这是一个有效的指针。
QNode* cur = q->front; // 创建一个指针 'cur'，用来遍历队列，从队首开始
int count = 0; // 初始化计数器 'count'，用于统计队列中的元素数量
// 遍历队列，直到 'cur' 指针为空，即到达队列末尾
while (cur)
{
count++; // 对每个节点进行计数
cur = cur->next; // 将 'cur' 指针移动到下一个节点
}
return count; // 返回队列中的元素总数
}
"Yesterday is history, tomorrow is a mystery, but today is a gift. That is why it is called the present."
昨日已成历史，明天充满未知，而今天是一份礼物，这就是为什么它被称为‘现在’。
