一篇讲透数据结构之链式队列
目录
一.队列的定义
二.队列的分类
三.队列的功能
四.链式队列的声明
五.链式队列功能的实现
5.1 初始化队列
5.2 判断队列是否为空
5.3 获取队头元素
5.4 获取队尾元素
5.5获取队列长度
5.6 入队
5.7出队
5.8 打印队列元素
5.9 销毁队列
一.队列的定义
队列（queue）是一种只允许在一端进行插入操作，而在另一端进行删除操作的线性表。其严格遵循先进先出（First In First Out）的规则，简称FIFO。
队列与栈类似，实现方式有两种。一种是以数组的方式实现，另一种以单链表来实现。这两种实现方式各有优劣，并且都有细节需要处理。
二.队列的分类
队列可以根据分为单向队列、双向队列（特殊的队列）、循环队列三种。
其中，单向队列为本篇文章中要实现的队列
双向队列为可以从两端进行插入和删除的队列（我也不知道为什么要弄一个这样的队列出来，根定义不一样了都）
循环队列是循环的队列。
三.队列的功能
队列主要需要实现如下功能：
5.1 初始化队列
5.2 判断队列是否为空
5.3 获取队头元素
5.4 获取队尾元素
5.5获取队列长度
5.6 入队
5.7出队
5.8 打印队列元素
5.9 销毁队列
四.链式队列的声明
由于我们实现的队列是由链表实现的，因此我们需要先声明一个结构体类型表示链表。
之后，我们就可以声明队列了，队列其中的成员分别是队列的头指针、队列的尾指针、队列的长度。
typedef int QDataType;
typedef struct QueueNode
{QDataType data;//队列数据struct QueueNode* next;//指向下一个队列块
}QNode;
typedef struct Queue
{QNode* front;//队列头QNode* rear;//队列尾int size;//队列长度
}Queue;五.链式队列功能的实现
5.1 初始化队列
初始化队列，就是给队列的每个成员赋初值。
由于front和rear是指针，因此我们初始化为空。
由于size是整型，因此我们初始化为0.
void QueueInit(Queue* q)
{q->front = NULL;q->rear = NULL;q->size = 0;
}5.2 判断队列是否为空
判断一个队列是否为0的方式有很多，
可以通过判断size是否为0判断；
也可以通过队列头和队列尾的指针来判断 。
这里我们通过size是否等于0来判断。
bool QueueEmpty(Queue* q)
{assert(q);return q->size;
}5.3 获取队头元素
获取队列的头元素，只要保证队列存在并且不为空即可。
队列的头元素就是队列头指针的data，我们访问即可。
QDataType QueueFront(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->front->data;
}5.4 获取队尾元素
队列的尾部数据的获取，和获取队头数据类似，直接返回队尾指针即可。
、
QDataType QueueBack(Queue* q)
{assert(q);assert(!QueueEmpty(q));return q->rear->data;
}5.5获取队列长度
直接返回size即可。
//获取队列长度
int QueueSize(Queue* q)
{assert(q);return q->size;
}5.6 入队
入队列，首先我们应动态申请一个链表结点。
之后我们就可以自行初始化链表结点的值了。
再然后我们要分为两种情况了，
第一种情况是链表没有结点，这时我们的结点入队列对队头和队尾都会产生影响；
第二种情况是链表中已有结点，这时我们的结点入队列只会对队尾产生影响。
因此我们在这里需要通过分支结构处理这个问题。
由于这两种情况都需要处理size，为了防止代码冗长，我们将size的自增语句写在分支结构之外。
void QueuePush(Queue* q, QDataType x)
{assert(q);//初始化新结点QNode* newnode = (QNode*)malloc(sizeof(QNode));newnode->data = x;newnode->next = NULL;//队列为空if (q->front == q->rear == NULL){//更新信息q->front = q->rear = newnode;//q->size++;}else{//更新信息q->rear->next = newnode;q->rear = newnode;//q->size++;}q->size++;
}5.7出队
在已经讲解了入队列之后，我们再讲解一下出队列。
出队列首先要确保队列中已有队列结点，否则将无队列结点可出。
出队列也分为两种情况，
第一种情况是队列中只有一个结点，我们需要释放掉这个结点并将队列的头指针和尾指针置空；
第二种情况是队列中有好多个结点，这时我们释放掉队列头的结点之后，更新队头即可。
//出队
//1.考虑情况要全面
//2.在更新队列时，要将数据结构中受到影响的成员全部更新
//3.如果分不清谁受到了影响，就逐个排查。
void QueuePop(Queue* q)
{assert(q);assert(q->front);if (q->size == 1){free(q->front);q->front = q->rear = NULL;}else{QNode* ret = q->front->next;free(q->front);q->front = ret;}q->size--;
}在有多个结点的情况下，我们在出队时，需要注意的是需要定义一个指针保存队头的下一个结点，否则在更新时则无从下手。
5.8 打印队列元素
与链表的打印方式一样，打印即可。
void QueuePrint(Queue* q)
{assert(q);QNode* cur = q->front;printf("队头->");while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("队尾");
}5.9 销毁队列
与链表的销毁方法一样，销毁即可。
void QueueDestroy(Queue* q)
{assert(q);QNode* ret = q->front;while (ret){QNode* next = ret->next;free(ret);ret = next;}q->front = q->rear = NULL;
}