现在我们来掌握一下队列！如果有对往期知识有不足地方，可翻阅之前文章哦！
个人主页：小八哥向前冲~-CSDN博客
所属专栏：数据结构【c语言版】_小八哥向前冲~的博客-CSDN博客
栈和队列的实现其实都是对你顺序表和链表的检验，只有一些新的概念罢了！
哈哈！不信就往下看吧！！！
目录
什么是队列？
- 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 。
- 入队列：进行插入操作的一端称为队尾。
- 出队列：进行删除操作的一端称为队头。
上图理解：
注意：遵循先进先出的原则！这个原则就是区分栈（后进先出）和队列（先进先出）方法！
我们来看看一个队列需要有的最基本要求：详情见--queue - C++ Reference
了解了队列的基本概念，我们来扩展一下！
扩展--循环队列
生活中队列很常用，而在实际的生活中，有时我们会用到循环队列。
循环队列它也有一些应用场景。如：在操作系统中的生产者消费者模型（这个我们后续提到！）
在这种问题中，环形队列可以使用数组实现，也可以使用循环链表实现。
我们图上了解：
空的环形队列：
满的环形队列：
注意：为了能区别Q.front=Q.rear为队满还是队空，我们通常认为Q.rear+1=Q.front为满！
ok!了解了队列的基本，我们来巩固一下：
3.循环队列的存储空间为 Q(1:100) ，初始状态为 front=rear=100 。经过一系列正常的入队与退队操作 后， front=rear=99 ，则循环队列中的元素个数为（ ）
A .1
B.2
C.99
D.0或者100
4.以下( )不是队列的基本运算？
A.从队尾插入一个新元素
B.从队列中删除第i个元素
C.判断一个队列是否为空
D.读取队头元素的值
5.现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为( )？(假设 队头不存放数据)
A.(rear - front + N) % N + 1
B.(rear - front + N) % N
C.ear - front) % (N + 1)
D.(rear - front + N) % (N - 1)
答案：3.D 4.B 5.B
参考：
3.我们肯定知道元素个数为空时，front=rear，可当front=rear时，也有元素为满的情况！
5.因为是循环队列，单纯尾指针和头指针相减并不能求出总长。
现在我们来实现一下队列（按照一个队列的基本要求）。
当然，队列像栈一样，都可以写成链表和顺序表的底层！这里主要了解链表！
队列的实现
还是老样子：我们创建Queue.h文件声明各种变量和函数，创建Queue.c文件来将函数实现。
思路：
我们在实现一个函数时，要先弄清楚参数。
既然底层是链表，那么就得定义节点！
typedef int QDataType;
//队列节点
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;我们来看看我们的底层逻辑：需要头指针记录头，尾指针记录尾，一个计数变量。
既然需要这几个变量时刻记录，不如我们直接定义一个结构体来管理这些参数。
作用：
这里将参数管理起来可以避免插入和删除函数参数二级指针的使用！（下面会有体现）。
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
ok! 我们来将这些函数一一实现。
初始化
我们得先将记录的参数初始化一下，以便后续参数的更新！
//队列的初始化
void QInit(Queue* p)
{
assert(p);
p->phead = p->ptail = NULL;
p->size = 0;
}队列的插入
这里谨记：队列是先进先出，栈是后进先出，不要搞混了！
这里由于记录好了尾指针，我们直接在尾后面插入就行！这样看是不是觉得很方便？避免了二级指针的使用。
在插入之前，需要开辟一个节点，然后开始插入！
//队列的插入
void Qpush(Queue* p, QDataType x)
{
assert(p);
QNode* node = (QNode*)malloc(sizeof(QNode));
if (node == NULL)
{
perror("malloc failed!");
return;
}
//初始化节点
node->next = NULL;
node->val = x;
//开始插入
if (p->phead == NULL)
{
p->phead = p->ptail = node;
}
else
{
p->ptail->next = node;
p->ptail = node;
}
}队列的判空
我们只需要在管理的数据变量中判断计数器的值是否为空就行！这也侧面体现了我们用一个结构体管理变量的好处！
//队列的判空
bool QEmpty(Queue* p)
{
assert(p);
return p->size==0;
}队列的删除
- 在删除之前，我们要先判断队列是否为空，如果为空的话，不能删除。
- 因为队列是先进先出原则，既然尾部进数据，那么头部出数据。所以我们删除数据要在头部删除！
而在删除时要讨论队列中一个节点还是多个节点问题。本来不讨论我们也能删除数据，那么是为什么要讨论呢？
当队列中只有一个节点时，头指针等于尾指针一起指向这一个节点，当删除时，头指针移向空，然后将这个节点释放掉，但尾指针仍然指向那个节点，当我们访问尾指针指向的那个值时，程序出现错误！
我们上图理解：
于是我们能这样写代码：
//队列的删除
void Qpop(Queue* p)
{
assert(p);
//删除之前不能为空
assert(!QEmpty(p));
//讨论队列只有一个节点的情况！
if (p->phead->next == NULL)
{
free(p->phead);
p->phead = p->ptail = NULL;
}
else
{
QNode* next = p->phead->next;
free(p->phead);
p->phead = next;
}
p->size--;
}队列的尾数据
有了前面的基础，我们访问队列尾数据十分简单，但需要注意的是，判断队列是否为空。
//队列的尾数据
QDataType QBack(Queue* p)
{
assert(p);
assert(!QEmpty(p));
return p->ptail->val;
}队列的头数据
能十分访问尾数据，访问头数据也是如此，但是别忘了要判断队列是否为空。
//队列的头数据
QDataType QFront(Queue* p)
{
assert(p);
assert(!QEmpty(p));
return p->phead->val;
}队列的销毁
我们动态开辟了内存节点，那么当我们不用了这个队列时，不要忘了销毁它！
//队列的销毁
void QDestroy(Queue* p)
{
assert(p);
QNode* cur = p->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
}总代码
Queue.h文件
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDataType;
//队列节点
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;
//队列相关变量
//先进先出
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
//队列的初始化
void QInit(Queue* p);
//队列的插入
void Qpush(Queue* p, QDataType x);
//队列的判空
bool QEmpty(Queue* p);
//队列的删除
void Qpop(Queue* p);
//队列的尾数据
QDataType QBack(Queue* p);
//队列的头数据
QDataType QFront(Queue* p);
//队列的销毁
void QDestroy(Queue* p);Queue.c文件
#include"Queue.h"
//队列的初始化
void QInit(Queue* p)
{
assert(p);
p->phead = p->ptail = NULL;
p->size = 0;
}
//队列的插入
void Qpush(Queue* p, QDataType x)
{
assert(p);
QNode* node = (QNode*)malloc(sizeof(QNode));
if (node == NULL)
{
perror("malloc failed!");
return;
}
//初始化节点
node->next = NULL;
node->val = x;
//开始插入
if (p->phead == NULL)
{
p->phead = p->ptail = node;
}
else
{
p->ptail->next = node;
p->ptail = node;
}
}
//队列的判空
bool QEmpty(Queue* p)
{
assert(p);
return p->phead == NULL;
}
//队列的删除
void Qpop(Queue* p)
{
assert(p);
//删除之前不能为空
assert(!QEmpty(p));
//讨论队列只有一个节点的情况！
if (p->phead->next == NULL)
{
free(p->phead);
p->phead = p->ptail = NULL;
}
else
{
QNode* next = p->phead->next;
free(p->phead);
p->phead = next;
}
p->size--;
}
//队列的尾数据
QDataType QBack(Queue* p)
{
assert(p);
assert(!QEmpty(p));
return p->ptail->val;
}
//队列的头数据
QDataType QFront(Queue* p)
{
assert(p);
assert(!QEmpty(p));
return p->phead->val;
}
//队列的销毁
void QDestroy(Queue* p)
{
assert(p);
QNode* cur = p->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
}好了，现在你已经掌握了队列，快去题海感受一下吧！
我们下期见！
