队列

1.队列的概念

队列和栈一样，是一个 特殊的线性表。

队列只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。进行 插入操作 的一端称为队尾，进行 删除操作 的一端称为队头。

队列中的元素遵守 先进先出(First In First Out) 的原则。就和排队一样，队列是绝对公平的，先来的先到队头，不存在插队行为，只能后面排队，前面离开。
在这里插入图片描述

2.队列的结构

队列的结构可以用数组或链表来实现。哪个结构更好？

数组：
数组左边为队头右边为队尾：队尾(右)插入数据 为 顺序表尾插 很方便，但是 队头(左)删除数据 需要挪动数据，很麻烦。
数组左边为队尾右边为队头：队头(右)删除数据 为尾删，队尾(左)插入数据 需要挪动数据，也很麻烦。
所以数组结构并不适合队列。

链表：
结构选择：单/双循环/非循环带头/不带头
带不带头？可要可不要，带头就是方便尾插，少一层判断，没什么影响。
双向吗？没必要找前一个元素，队列只需要队头队尾出入数据。
循环吗？价值不大。双向循环可以找尾，但是没有必要。

双向链表：
可以使用双向链表，但是没必要，小题大做了，使用单链表就可以。

3.队列的实现

3.1结构设计

上面确定了用 单链表实现，所以就一定要有结构体表示节点：

typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;

由于链表的尾插比较麻烦，而队列的入数据为尾插。所以定义队列的结构体时，可以定义两个指针 head 和 tail 分别对应队头和队尾，tail 的引入就是方便尾插，再在给定一个 sz 实时记录队列的大小

typedef struct Queue
{QNode* head;QNode* tail;int sz;
}Queue;

看到这样的结构可能会有疑问：
1.为什么会有两个结构体？struct QueueNode是整体，是存数据和下一个节点链接的；struct Queue是局部，是头指针和存size的。
2.为什么不直接合并两个结构体呢？struct QueueNode是整体，struct Queue是局部，不能和在一起，同时也体现了使用数据结构的灵活性

3.2接口总览

void QueueInit(Queue* pq); // 初始化
void QueueDestroy(Queue* pq); // 销毁
void QueuePush(Queue* pq, QDataType x); // 入队列
void QueuePop(Queue* pq); // 出队列
QDataType QueueFront(Queue* pq); // 取队头元素
QDataType QueueBack(Queue* pq); // 取队尾元素
bool QueueEmpty(Queue* pq); // 判空
int QueueSize(Queue* pq); // 计算队列大小

3.3初始化

队列初始化，就只需要结构中指针初始化为 NULL，并将 sz 初始化为0。

void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->sz = 0;
}

这里是通过结构体的地址来找到结构体中的两个指针，通过结构体来改变指针的。

3.4销毁

我们实现的队列结构为链式的，所以本质为一条 单链表。
那么销毁时，就需要迭代销毁链表的节点。

void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->sz = 0;
}

3.5入队列

对于单链表的尾插，需要创建节点，找尾，然后链接。

但是我们设计队列结构时，给定了一个 tail 作为队尾，这时插入就比较方便了。但是需要注意一下 第一次尾插 的情况。

在入队列之后，记得调整 sz。

而且队列只会从队尾入数据，所以创建节点的一步，并没有必要封装一个接口专门调用，直接在函数中创建即可。

void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}else{newnode->data = x;newnode->next = NULL;//不置空newnode->next是随机值，会出问题}// 尾插if (pq->head == NULL){assert(pq->tail == NULL);//头为空，尾却没为空，警告pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = pq->tail->next;}pq->sz++; 
}

3.6 出队列

首先明确，队列为空不能出队列，出队列是从队头出数据。
其次，需要考虑删除时会不会有什么特殊情况。
一般删除时，可以记录 head 的下一个节点，然后释放 head ，再重新为 head 赋值。

但是，当 只有一个节点 呢？此刻 head == tail，它们的地址相同，如果此时仅仅释放了 head，最后head走到 NULL，但是tail 此刻指向被释放的节点，且没有置空，此刻风险就产生了，tail就变成野指针了。
在这里插入图片描述

之后一旦我 入队列 时，tail != NULL，那么必定就会走到 else 部分，对 tail 进行访问，此刻程序就会奔溃，所以需要处理一下，将 tail 也置空。

同样的，出队列 成功后 sz 需要发生调整。

void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));// 一个节点时删除的特殊情况// 需要将头尾都变为空if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* newhead = pq->head->next;free(pq->head);pq->head = newhead;}pq->sz--;
}

3.7取对头数据

队列非空，取 head 出数据

QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}

3.8 取队尾数据

队列非空，取 tail 处数据。

QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

3.9 判空

当 head 和 tail 都为空指针时，说明队列中无元素。

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL && pq->tail == NULL;
}

3.10 计算队列大小

从这个接口处，就可以看出设计结构时，设计的还是很精妙的，因为有 sz 直接返回即可。

int QueueSize(Queue* pq)
{assert(pq);return pq->sz;
}

试想一下，如果没有这个 sz，我们如何计算队列大小？是不是又得遍历链表了？这样接口的时间复杂度就为O(N)，而其他接口几乎都是O(1)的复杂度，是不是不太理想？所以结构设计时加上一个 sz 的效果是极好的！

下面贴上没有 sz 时的代码：

int QueueSize(Queue* pq)
{assert(pq);QNode* cur = pq->head;int size = 0;while (cur){cur = cur->next;++size;}return size;
}

4. 完整代码

Queue.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>typedef int QDataType;typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int sz;
}Queue;void QueueInit(Queue* pq); // 初始化
void QueueDestroy(Queue* pq); // 销毁
void QueuePush(Queue* pq, QDataType x); // 入队列
void QueuePop(Queue* pq); // 出队列
QDataType QueueFront(Queue* pq); // 取队头元素
QDataType QueueBack(Queue* pq); // 取队尾元素
bool QueueEmpty(Queue* pq); // 判空
int QueueSize(Queue* pq); // 计算队列大小

Queue.c

#include "Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->sz = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->sz = 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}else{newnode->data = x;newnode->next = NULL;//不置空newnode->next是随机值，会出问题}// 尾插if (pq->head == NULL){assert(pq->tail == NULL);//头为空，尾却没为空，警告pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = pq->tail->next;}pq->sz++;
}void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));// 一个节点时删除的特殊情况// 需要将头尾都变为空if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* newhead = pq->head->next;free(pq->head);pq->head = newhead;}pq->sz--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//防止空指针return pq->head->data;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}bool QueueEmpty(Queue* pq)
{assert(pq);//return pq->size==0;return pq->head == NULL && pq->tail == NULL;
}int QueueSize(Queue* pq)
{assert(pq);return pq->sz;
}

test.c

#include "Queue.h"int main()
{Queue q;QueueInit(&q);QueuePush(&q,1);QueuePush(&q,2);QueuePush(&q,3);QueuePush(&q,4);while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}printf("\n");QueueDestroy(&q);system("pause");return 0;
}