😜前言

🍎栈和队列可以说是一对好兄弟，前面学习了栈，那队列当然也少不了。对于栈而言，队列可以说具有与他相反的性质，本章就给大家领悟一下队列的魅力。
🍒队列是一种简单的数据结构，它的主要性质，就是数据先进先出(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为NULLassert(pq);// 如果size为0，说明判断为true，返回truereturn 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;
}

🤪写在最后

💝队列还是比较简单呢，只要能够实现前面的数据结构，队列也可以说是洒洒水嘞。
❤️‍🔥后续将会持续输出有关数据结构的文章，你们的支持就是我写作的最大动力！

感谢阅读本小白的博客，错误的地方请严厉指出噢~