😜前言
🍎栈和队列可以说是一对好兄弟，前面学习了栈，那队列当然也少不了。对于栈而言，队列可以说具有与他相反的性质，本章就给大家领悟一下队列的魅力。
🍒队列是一种简单的数据结构，它的主要性质，就是数据先进先出(FIFO)，我们可以利用这一性质，在做某些算法题时，以此为切入点，如：单调队列等等。所以说，我们要熟练其性质。
队列初始化
- 队列的性质是先进先出(相当于一根管道)，出是出一个队列的队头，进是在一个队列的队尾进，当然还可以访问队列的队头元素和队尾元素。
图示：
那么根据列队的性质，我们该如何来选择队列的底层结构呢？是顺序表的数组还是链表呢？
假如我们选择顺序表的数组，对于入队操作是很简单的，时间复杂度为O(1)，但是，出队操作效率就比较低了，需要挪动数据。并且，当入队的数据多了，数组还需要扩容，这样看来，顺序表的数组结构不是很完美，所以我们在看看链表怎么样。
如果底层是链表结构，很明显，对于出队操作就相当于链表的头删，时间复杂度为O(1)，效率不错，但如果是入队操作呢？我们是否需要遍历一遍链表找到队尾，然后再进行入队呢？ 这里是不需要的。我们可以定义一个指针指向链表的尾节点 （由于没有尾删的操作，所以这个指针定义的很合理），通过这个指针来进行入队操作，这样以来，入队操作也变成O(1)了。因此，总的看来，链表结构是最适合于作为队列的底层结构了。
有了对队列的认识和对队列的底层结构的断定，接下来就开始实现一个简单的队列咯。
首先是对一个队列整个框架的初始操作。
同样的，需要三个文件：queue.h queue.c test.c。queue.h用来存放所需头文件，队列相关的结构体以及功能函数接口声明。queue.c用来实现功能函数接口。test.c用来测试。
整个队列所需的头文件：
#include <stdio.h> // assert 断言所需 #include <assert.h> // malloc 所需 #include <stdlib.h> // 布尔类型所需 #include <stdbool.h>
有了头文件之后，定义一个结构体，来表示每一个节点的结构：
// 队列的数据的类型 typedef int QDataType; // 节点结构 typedef struct QueueNode { // 起连接作用的节点指针 struct QueueNode* next; // 存放数据 QDataType data; }QNode;
上面说到，需要两个指针，一个指向链表的头，一个指向链表的尾，如果我们在测试的时候定义这两个指针，然后通过传递这两个指针来对链表进行操作，那未免非常的麻烦。并且，如果要改变这两个指针的指向，还需用到二级指针，这想想就可怕。因此，这里也用一个结构体对这两个指针进行封装，通过对这个结构体的操作，间接操控整个链表。定义如下：
// 队列结构 typedef struct Queue { // QNode* 表示它是一个节点指针，head表示他是指向链表头的那个指针 QNode* head; // QNode* 表示它是一个节点指针，tail表示它是指向链表尾的那个指针 QNode* tail; // 统计队列的数据个数 int size; }Que; // typedef 重命名为 Que
- 可以看到，上面这个结构体还多了一个
size成员，它是用来统计队列的数据个数的，在判空，获取数据个数等函数接口里都要用到。 Que这个结构体，就可以看作一个队列，通过两个指针，对整个队列进行操作，所以每个函数接口的参数，都要包含Que结构体的指针参数：
- 一个队列的基本框架形成之后，接下来就要开始逐一实现队列的功能模块了。
所需功能函数接口的声明：
// 初始化队列 void QInit(Que* pq); // 队列判空 bool QEmpty(Que* pq); // 数据入队列 void QPush(Que* pq, QDataType x); // 数据出队列 void QPop(Que* pq); // 取队头数据 QDataType QFront(Que* pq); // 取队尾数据 QDataType QBack(Que* pq); // 获取队列中有效元素个数 int QSize(Que* pq); // 销毁队列 void QDestroy(Que* pq);
- 首先是对队列的初始化，简单来说，就是对一个
Que结构体变量初始化，具体的操作：
Que q; // 创建一个 Que 结构体变量 QInit(&q); // 对 q 调用初始化函数来初始化
- 而初始化函数，就是将
Que的结构体变量里边的两个指针置为空，size置为零。
相关函数接口实现：
// 初始化队列 void QInit(Que* pq) { // 防止传递一个NULL过来 assert(pq); // 初始化 // pq为Que结构体指针，通过->操作符访问其成员 pq->head = NULL; pq->tail = NULL; pq->size = 0; }
队列的判空
- 由于
Que结构体里面含有一个size成员用来统计队列数据个数的，因此，队列的判空就很简单了，只需要判断一下size是不是0即可。
相关函数接口实现：
// 队列判空 bool QEmpty(Que* pq) { // 防止pq为NULL assert(pq); // 如果size为0，说明判断为true，返回true return pq->size == 0; }
数据入队列
- 入队列简单来说就是插入数据，在队列的尾部插入数据，由于我们定义了一个指针指向队列的尾部，因此这里插入数据就显得很简单了。
- 首先是使用malloc得到一个QNode节点，每次得到的节点都需要将其里面的next指针置为NULL，data存放所需数据。
- 接着通过指向尾的指针将尾节点与新节点连接。如果此时队列为空，将两个指针都指向这个新节点即可。
- 最后将size加一即可。
- 注意，每次对尾指针进行操作后，都要更新一下尾指针。
相关函数接口实现：
// 数据入队列 void QPush(Que* pq, QDataType x) { assert(pq); // 开辟一个节点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); assert(newnode); newnode->data = x; newnode->next = NULL; // 如果此时队列为空，将两个指针指向这个新节点即可 if (pq->size == 0) pq->head = pq->tail = newnode; else { // 连接 pq->tail->next = newnode; pq->tail = newnode; } // 入一个数据，size要加一 pq->size++; }
数据出队列
数据出队列就相当于头删，由于我们定义了一个指针指向队列的头，因此这里也是很好操作的。
我们先要存放头节点的下一个节点的地址，然后再将头节点删除，最后指向头节点的指针更新一下即可。
如果此时队列为空，就不能删了，直接assert暴打。
如果此时队列只有一个元素，删除过后，指向队列头的那个指针此时指向NULL，而那个指向队列尾的指针还指向刚才被删的节点的位置，因此，为了以防万一（防止通过该指针继续使用那个被删的节点），这里需要将指向队列尾的那个指针置为NULL。
当然最后记得size要减一。
相关函数接口实现：
// 数据出队列 void QPop(Que* pq) { // 需要判空 assert(pq && !QEmpty(pq)); // 这是只有一个节点的操作 if (pq->head == pq->tail) { free(pq->head); pq->head = NULL; pq->tail = NULL; } else { // 正常删除 QNode* tmp = pq->head->next; free(pq->head); pq->head = tmp; } // 删除完后size要减一 pq->size--; }
取队头数据
- 取队头数据就是第一个节点的数据，我们通过指向队头的指针可以直接拿出数据。
- 注意，如果队列为空，就不能取数据。
相关函数接口实现：
// 取队头数据 QDataType QFront(Que* pq) { assert(pq && !QEmpty(pq)); // 直接返回队头的数据 return pq->head->data; }
取队尾数据
- 这里通过指向队尾的指针也可以直接获取队尾数据。
- 注意，队列不能为空。
相关函数接口实现：
// 取队尾数据 QDataType QBack(Que* pq) { assert(pq && !QEmpty(pq)); return pq->tail->data; }
数据的个数
- 由于我们再
Que结构体里定义了一个size来统计队列的数据个数，因此这里直接返回这个size即可。
相关函数接口实现：
// 获取队列中有效元素个数 int QSize(Que* pq) { assert(pq); return pq->size; }
队列的销毁
- 队列的销毁需要我们将每一个节点依次释放，因此，我们只需要运用指向头节点的指针遍历一遍队列，一边遍历一边删除即可。
- 当然最后需要将操作队列的两个指针都指向
NULL，size也要置为0。
相关函数接口实现：
// 队列销毁 void QDestroy(Que* pq) { assert(pq); QNode* cur = pq->head; // 遍历队列（链表） while (cur) { QNode* next = cur->next; free(cur); cur = next; } // 最后操作 pq->head = NULL; pq->tail = NULL; pq->size = 0; }
整体的代码
queue.h
#include <stdio.h> #include <assert.h> #include <stdlib.h> #include <stdbool.h> // 队列的数据的类型 typedef int QDataType; // 节点结构 typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; // 队列结构 typedef struct Queue { QNode* head; QNode* tail; int size; }Que; // 初始化队列 void QInit(Que* pq); // 销毁队列 void QDestroy(Que* pq); // 数据入队列 void QPush(Que* pq, QDataType x); // 数据出队列 void QPop(Que* pq); // 获取队列中有效元素个数 int QSize(Que* pq); // 队列判空 bool QEmpty(Que* pq); // 取队头数据 QDataType QFront(Que* pq); // 取队尾数据 QDataType QBack(Que* pq);
queue.c
#include "queue.h" // 初始化队列 void QInit(Que* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; pq->size = 0; } // 队列销毁 void QDestroy(Que* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = NULL; pq->tail = NULL; pq->size = 0; } // 数据入队列 void QPush(Que* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); assert(newnode); newnode->data = x; newnode->next = NULL; if (pq->size == 0) pq->head = pq->tail = newnode; else { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; } // 数据出队列 void QPop(Que* pq) { assert(pq && !QEmpty(pq)); if (pq->head == pq->tail) { free(pq->head); pq->head = NULL; pq->tail = NULL; } else { QNode* tmp = pq->head->next; free(pq->head); pq->head = tmp; } pq->size--; } // 获取队列中有效元素个数 int QSize(Que* pq) { assert(pq); return pq->size; } // 队列判空 bool QEmpty(Que* pq) { assert(pq); return pq->size == 0; } // 取队头数据 QDataType QFront(Que* pq) { assert(pq && !QEmpty(pq)); return pq->head->data; } // 取队尾数据 QDataType QBack(Que* pq) { assert(pq && !QEmpty(pq)); return pq->tail->data; }
test.c
#include "queue.h" void test() { Que q; QInit(&q); QPush(&q, 1); printf("%d %d %d\n", q.size, QBack(&q), QFront(&q)); QPush(&q, 2); printf("%d %d %d\n", q.size, QBack(&q), QFront(&q)); QPush(&q, 3); printf("%d %d %d\n", q.size, QBack(&q), QFront(&q)); QPush(&q, 4); printf("%d %d %d\n", q.size, QBack(&q), QFront(&q)); QPush(&q, 5); printf("%d %d %d\n", q.size, QBack(&q), QFront(&q)); printf("%d\n", QSize(&q)); while (!QEmpty(&q)) { printf("%d ", QFront(&q)); QPop(&q); } printf("\n"); printf("%d\n", q.size); QDestroy(&q); } int main() { test(); return 0; }
🤪写在最后
💝队列还是比较简单呢，只要能够实现前面的数据结构，队列也可以说是洒洒水嘞。
❤️🔥后续将会持续输出有关数据结构的文章，你们的支持就是我写作的最大动力！
感谢阅读本小白的博客，错误的地方请严厉指出噢~
