目录
- 队列
- 队列的概念及结构
- 队列的实现
- 队列功能的实现
队列
队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) (一端入一端出)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
队列的入队顺序和出队顺序是否和栈一样存在一对多的关系？
因为栈是后进先出,假设我们入栈一个数据A，在A入栈后不继续加入其他的数据B C D,那么如果我们进行出栈的话，数据A就会第一个出来
所以栈的入栈顺序和出栈顺序是一对多的情况，举个例子
栈的入栈顺序为A B C D E
则出栈顺序可能为 E D C B A，或者 A B C D E
对于E D C B A这种情况就是当数据全部入栈后，我们按照后进先出的规则，进行出栈，也就是E最后入栈，所以第一个出栈，D是倒数第二个入栈，所以出栈的时候就是第二个…
对于A B C D E这种情况就是当A刚入栈后，我们就让A直接出栈，因为其他的数据B C D E都还没有入栈，所以我们只能让A先出栈，之后再将B入栈，然后B再出栈…
出栈的顺序不止这两种，所以就不一一举例了，总之栈的出栈顺序和入栈顺序是一对多的关系
对于队列而言，因为是先进先出的顺序，所以入和出都只有一种情况，没有一对多的关系
队列的实现
队列也可以数组和链表的结构实现
如果用数组实现的就比较麻烦，因为队列是队尾入，对头出，那么如果用数组去实现队列，我们就要让数组头删，头删的复杂度为O（N）
如果用单链表的话，就很方便，因为是队尾入，队头出，删除数据不像栈一样要尾删，队列只需要让队头的数据删除就可以了，单链表的头删时间复杂度为O（1），并且实现起来要比双向链表要容易些，所以选择用单链表实现队列
单链表实现队列我们可以用带哨兵位的方式，也可以选择不用，带哨兵位需要malloc，最后还需要free掉哨兵位，并且哨兵位在这里的作用不是很大，所以队列的实现我们选择不带哨兵位的方式
实际中我们有时还会使用一种队列叫循环队列，环形队列可以使用数组实现，也可以使用循环链表实现
代码
typedef struct QueueNode
{
QDataType val;
struct QueueNode* next;
}QNode;
队列功能的实现
队列的尾插void QueuePush(Queue*pq, QDataType x);
队列尾插函数如果只传两个参数参数头节点的地址,还有需要插入的数据x,(void QueuePush(QNode* * phead, QDataType x)),那么尾插的时间复杂度就为O（N），这样好像单链表就没什么优势了
如果我们传入三个参数void QueuePush(QNode* * phead, QNode* * ptail, QDataType x)，其中ptail为指向尾节点的地址，虽然这样可以解决问题，但是我们要注意这里的指针全是二级指针，phead是plist指针传入的参数，因为plist是一个一级指针，要更改一级指针我们就需要将传参类型变成二级指针，ptail也是，非常麻烦
结构体封装指针typedef struct Queue
所以我们要创建一个结构体，将两个指针封装起来， 这样我们传入的参数就不用二级指针，只需要修改结构体成员就可以了
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size//size为队尾到队头总共有多少个节点
}Queue;
总结
如果遇到函数参数需要传入多个二级指针，那么我们可以用结构体将他们封装起来，结构体封装的成员就是二级指针的值，然后通过结构体访问成员将他们修改，并且在传参时我们只需要传入结构体的地址即可
代码
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode * )malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->val = x;
newnode->next = NULL;
if (pq->ptail == NULL)
{
pq->ptail = pq->phead = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
当ptail=NULL的时候就说明没有尾节点，只要队列有一个节点，那么尾节点都不可能为空，尾节点为空说明队列是空的，那么尾插就直接让尾节点=头节点=插入的newnode
如果尾节点不为空，那就直接让尾节点的next=newnode，然后插入newnode后newnode又是新的尾节点，所以让ptail=newnode
最后不要忘记size++
队列的头删void QueuePop(Queue* pq)
头删一般都得考虑两种情况，一种是只有一个节点，另一种就是没有节点
当没有节点时，我们assert断言就可以了
只有一个节点时，在头删后要小心ptail变成野指针，当phead走到下一个节点，发现是空后，如果直接把之前的头节点删除，我们会发现ptail还指向原来头节点的位置，free掉头节点后，ptail就成了野指针
所以需要判断如果phead走到下一个节点为空后，要让ptail赋值成NULL
代码
void QueuePop(Queue* pq)
{
assert(pq);//结构体不能为空
assert(pq->phead);//判断头节点为空的情况
QNode* del = pq->phead;//del保存头节点方便后面释放空间
pq->phead = pq->phead->next;
free(del);
if (pq->phead == NULL)
pq->ptail == NULL;
pq->size--
}
队列的初始化void QueueInit(Queue* pq)
代码
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
队列的销毁void QueueDestroy(Queue* pq, QDataType x)
代码
void QueueDestroy(Queue* pq, QDataType x)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = pq->ptail = NULL;
size=0；
}
取队尾数据QDataType QueueBack(Queue* pq)
代码
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->ptail);
return pq->ptail->val;
}
取队头数据QDataType QueueFront(Queue* pq)
代码
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->val;
}
判断队列是否为空bool QueueEmpty(Queue* pq)
代码
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL;
}
获得队列的长度int QueueSize(Queue* pq)
代码
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}