一篇讲透数据结构之链式队列

目录

一.队列的定义

二.队列的分类

三.队列的功能

四.链式队列的声明

五.链式队列功能的实现

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;
}