深入理解队列（Queue）的实现（纯小白进）

前言

前篇我们学习了栈，理解了栈的性质和实现。现在我们进入队列的学习，那么什么是队列？队列有什么样的特性？它的应用场景有哪些？ 本文会对队列这种数据结构进行进行抽丝剥茧般的讲解，让你彻底学会它。

一、 什么是队列?

队列是一种常见的数据结构，它按照先进先出（FIFO）的原则进行操作。队列中的元素按照进入的顺序排列，新元素插入到队列的一端，称为队尾，已有元素的删除操作则发生在队列的另一端，称为队头。

1.1、 队列的特性

1. 先进先出（FIFO）：队列中的元素按照进入的顺序排列，最先进入的元素最先被删除。
2. 只能在队尾插入元素：新元素只能从队尾插入。
3. 只能在队头删除元素：已有元素只能从队头删除。
4. 队列长度可变：队列的长度可以根据需要动态变化。
5. 队列可以为空：队列中没有元素时为空队列。
6. 队列可以为满：队列中的元素数量达到了队列的最大容量时为满队列。

1.2、 队列的图解

这个可以简单理解成，就像是我们生活中的食堂打饭排队一样，先来的在前面后来的在后面，前面的打完饭后就走了。这就像是数据结构中的队列。

二、 队列的详细实现

2.1、 队列不同的实现方式

1. 数组实现：使用数组来存储队列中的元素，通过两个指针分别指向队头和队尾。入队操作时，将新元素插入到队尾，同时移动队尾指针；出队操作时，删除队头元素，同时移动队头指针。这种实现方式简单直观，但在动态扩容时需要进行数据的搬移，效率较低。
2. 链表实现：使用链表来存储队列中的元素，每个节点包含一个元素和一个指向下一个节点的指针。入队操作时，创建一个新节点并插入到链表的末尾；出队操作时，删除链表的头节点。这种实现方式不需要进行数据的搬移，但需要额外的空间来存储指针。

本文我们的队列使用链表的形式来进行队列的实现。这里更推荐链表实现起来不会那么复杂。

2.2、 队列结构体

typedef int QDataType;//局部,单个节点的信息
typedef struct QueueNode {struct QueueNode* next;QDataType data;
}QNode;
//整体，整个队列的信息
typedef struct Queue {QNode* head;QNode* tail;int size;
}Queue;

对数据类型进行重命名，这样以后需要更换其他数据类型使用的时候只需要更改这一个地方就可以了。

这里有两个结构体，进行了结构体嵌套。定义一个链表的结点，包含当前结点元素和指向下一个结点的指针。然后定义一个队列结构体，队列中两个结构体体指针分别代表队头和队尾，size是当前队列的有效元素个数。

这样做的目的是，方便了队列的头删（出队列）和尾插（入队列），已经获取队列内的元素个数和队尾、队头的元素。

2.3、 队列的初始化

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

这里先将所以的指针都置空，size为0，因为是初始化所以队中无元素。

2.4、 入队列

在队列插入数据，要先开辟一个结点的空间，用来存放值和下一个结点的地址。这里要进行两种情况的判断：如果队头为空时，代表此时队列中无元素，那么队头和队尾指针指向同一块空间。当队头不为空时，就将队尾的指针指向新开辟的结点。插入新数据后，size的个数++。

void QueuePush(Queue* pq, QDataType x) {QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode==NULL) {perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL) {assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else {pq->tail->next = newnode;pq->tail = newnode;}pq->size++;}

2.5、 出队列

在队头删除数据，此处和入队列一样，要进行两种情况的判断：

（1）、 如果队头和队尾指针同时指向一块空间时，此时队列中只有一个元素，所以释放队头或队尾指针都可，然后将队头和队尾指针置空，方便下一次进行插入数据（入队列）。

（2）、队头和队尾指针不相等时，表名队列有最少一个以上的元素，创建一个临时结点用来存放队头指针下一个元素的地址，然后释放队头指针，再让队头指针指向下一个元素。

出队列后，队列中的有效元素个数就少了一个，所以size也要进行 --。

void QueuePop(Queue* pq) {assert(pq);assert(pq->head != NULL);if (pq->head->next == NULL) {//表示就一个节点free(pq->head);pq->head = pq->tail = NULL;}else {QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;}

2.6、 获取对头元素

要获取元素前需要进行判空，如果队列是空，那么就会报错。

队头指针指向的就是队列的首元素地址，进行解引用就可以获取队头的元素。

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

和QueuePush，QueuePop搭配在一起的测试运行结果如下：

2.7、 获取队尾元素

要获取元素前需要进行判空，如果队列是空，那么就会报错。

队头指针指向的就是队尾的首元素地址，进行解引用就可以获取队尾的元素。

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

2.8、 队列的判空

队列如果为空的情况下代表队头指针是空，此时队列无元素。

bool QueueEmpty(Queue* pq) {assert(pq);return pq->size == 0;
}

2.9、 队列有效的元素个数

我们先前定义的size就是队列中有效元素的个数。

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

2.10、 队列的销毁

因为队列是链表实现的，所以这里的释放空间要写成循环，释放队列中每一个结点的空间。

创建临时指针，让cur去迭代。最后队头和队尾指针都置空，size归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->size = 0;
}

2.11、 队列的应用场景

队列在计算机科学和软件开发中有广泛的应用场景:

1. 任务调度：队列可以用来实现任务调度系统，将待执行的任务按照先后顺序排列，每次从队头取出一个任务进行执行，保证任务按照顺序执行。
2. 消息传递：队列可以用来实现消息传递系统，消息发送方将消息入队，消息接收方从队头出队获取消息。这种方式可以实现异步消息传递，并且可以处理消息的积压情况。
3. 缓冲区：队列可以用来实现缓冲区，例如网络数据传输中的数据包缓冲区、磁盘读写中的数据缓冲区等。数据可以按照顺序入队，然后按照顺序出队进行处理，保证数据的有序性和流畅性。
4. 广度优先搜索：在图的广度优先搜索算法中，使用队列来存储待访问的节点，每次从队头取出一个节点进行访问，并将其邻接节点入队。这样可以保证按照层次遍历图的节点，从而实现广度优先搜索。
5. 线程池：在多线程编程中，线程池可以使用队列来实现任务的调度。将待执行的任务入队，线程池中的线程从队头取出任务进行执行，保证任务的有序执行和线程的复用。

以上只是一些常见的应用场景，队列还可以用于解决其他问题，如数据流量控制、请求排队、打印队列等。队列的先进先出特性使其在这些场景下能够提供高效的数据处理和调度能力。

三、 全篇总结

本篇对队列这种数据结构进行了概念的说明,对队列的实现细致入微,最后普及了队列这种数据结构的泛用性!希望大家搭配和栈的学习一起食用。
需要源代码自取