前言
队列和栈一样，同样是操作受限的线性表，在日常生活中的体现也很多，所以学习队列也是必不可少的。本篇文章将会详细介绍队列的具体实现，去解释每行代码的意思，希望对你有所帮助。话不多说，直接上菜。
文章末尾附带源码。
一、初识队列
队列，顾名思义，和平时就会遇到的排队一样。那么排队有什么特点吗，我们都知道，排队就是为了 “先到先得” 先来排队的会先完成自己的事并第一个离开队伍。所以队列也一样，他的核心思想就是先进先出，先进的数据肯定是比后进的数据要先出的。栈跟队列是相反的，栈是 后进先出 的线性表，队列是 先进先出 的线性表，千万不要记混了。
一般规定在队尾插入，在队头删除，也就是说在队头出数据，在队尾入数据。队列同样可以使用顺序表或者链表实现，如果使用顺序表，也就是数组来实现，不管是在哪端插入删除，都无法避免将整个数组给挨个移动，效率比较低。如果使用链表的话，在哪端插入删除都有较好的解决方法，效率较高。所以本篇文章将会使用最常见的单链表的方式来实现队列。
二、头文件的编写
好的代码可读性是非常高的，分工明确，所以我们将库函数源文件、定义的结构体和函数声明放在一个头文件里面。我们创建一个头文件，叫做 “Queue.h” 。
1.引入库函数头文件
#include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h>
2.定义队列结构体
// 重定义队列的数据类型 typedef int QDataType; // 队列元素的结构体 typedef struct QueueNode { // 队列元素的数据域 QDataType val; // 队列元素的指针域 struct QueueNode* next; }QNode;
我们使用 typedef 重定义队列的数据类型，后文的数据类型都被替换为 QDataType ，以方便以后改变数据类型时只需要改变此一行代码即可。由于我们是使用链表的方式来实现队列的，我们都知道，链表是通过指针来连接数据与数据的，所以在创建队列元素的结构体时，不仅仅需要存储元素的值，还需要一个指针来找到下一个元素。
3.定义传参结构体
// 传参结构体 typedef struct Queue { // 有一个指向队列的首元结点(队头)的指针 QNode* phead; // 有一个指向队列的尾结点(队尾)的指针 QNode* ptail; // 队列的元素个数 int size; }Queue;
队列的基本特性就是在队尾插入，在队头删除，不会改变中间的值。所以队尾和队头是需要经常使用的，不妨我们直接记录一下队列的队尾和队头，那么找尾再也不用遍历链表了。于是我们创建一个结构体，这个结构体里面储存着队头和队尾的位置，还顺便储存着队列的大小。两个指针是指向队列元素的，可以通过指针创建队列元素，所有有了指向队头的头指针，就可以创建队列。这个结构体在后面会有大用。
4.声明功能函数
// 初始化队列 void QueueInit(Queue* pq); // 销毁队列 void QueueDestroy(Queue* pq); // 在队尾插入 void QueuePush(Queue* pq, QDataType x); // 在队头弹出 void QueuePop(Queue* pq); // 查询队头元素 QDataType QueueFront(Queue* pq); // 查询队尾元素 QDataType QueueBack(Queue* pq); // 判断队列是否为空 bool QueueEmpty(Queue* pq); // 查询队列元素个数 int QueueSize(Queue* pq);
在一般情况下，对链表操作时，可能改变头指针的函数传参必须传入头指针的地址，通过二级指针来实现功能。但我们早在前面以及使用结构体包含了头指针以及尾指针，如果要改变头指针或者尾指针或者队列的元素个数，相当于在改变结构体，所以传入结构体的指针就能实现。
三、主函数文件的编写
同样的操作，我们将测试函数以及主函数放在同一个文件里面。我们创建一个源文件，叫做 “test.c” 。
1.包含头文件
#include"Queue.h"
2.编写测试函数
void test() { // 创建一个传参结构体成员 Queue q; // 初始化这个成员 QueueInit(&q); // 在队尾入队列 QueuePush(&q, 1); // 在队尾入队列 QueuePush(&q, 2); // 在队尾入队列 QueuePush(&q, 3); // 在队尾入队列 QueuePush(&q, 4); // 在队尾入队列 QueuePush(&q, 5); // 如果队列不为空 while (!QueueEmpty(&q)) { // 打印队头元素 printf("%d ", QueueFront(&q)); // 在队头出队列 QueuePop(&q); } printf("\n"); // 销毁 QueueDestroy(&q); return 0; }
测试用例仅作参考，可自拟测试用例。
四、功能函数的编写
我们创建一个源文件，叫做 “Queue.c” 。
1.包含头文件
#include"Queue.h"
2.初始化
// 传入传参结构体成员的地址 void QueueInit(Queue* pq) { // pq是指向传参结构体的指针，只要结构体创建了，那pq就不可能为空，为空说明传参错误或者结构体没创建 assert(pq); // 让指向首元结点的头指针和指向尾结点的尾指针置空，说明队列为空 pq->phead = pq->ptail = NULL; // 队列目前有效数据为0 pq->size = 0; }
3.销毁
void QueueDestroy(Queue* pq) { // pq不可能为空，可以断言一下以免出现小差错 assert(pq); // 如果pq指向的结构体里面的phead不为空，即存在结点 while (pq->phead) { // 创建一个临时指针变量指向首元结点 QNode* tmp = pq->phead; // 让phead指向第二个结点 pq->phead = pq->phead->next; // 释放首元结点空间 free(tmp); // 释放空间后指针置空是好习惯 tmp = NULL; } // 最后没有结点的时候，把尾结点置空 pq->ptail = NULL; // 让有效数据大小为0 pq->size = 0; }
销毁队列的方式其实就是链表的头删，使用临时指针变量指向待销毁的空间，然后使原本指向该结点的指针指向下一个准备销毁的结点，最后销毁即可。在这里面，每销毁一个结点，头指针就会根据结点的指针域找到下一个结点的位置，销毁到最后一个结点时，头指针已经通过指针域被赋值为 NULL 了，由于销毁完了后，尾指针还指向原本尾结点的空间，数据个数也还没有改变，所以销毁的最后是需要把参数给修改回初始值的。
4.入队列
void QueuePush(Queue* pq, QDataType x) { assert(pq); // 为新结点开辟空间 QNode* newNode = (QNode*)malloc(sizeof(QNode)); // 开辟失败时 if (newNode == NULL) { // 弹出反馈 perror("malloc fail"); // 终止程序 exit(-1); } // 为新结点赋值 newNode->val = x; newNode->next = NULL; // 当队列为空时 if (pq->ptail == NULL) { // 头指针指向新结点 pq->phead = pq->ptail = newNode; } // 当队列非空时 else { // 原尾结点的指针域指向新结点 pq->ptail->next = newNode; // 尾指针指向新结点 pq->ptail = newNode; } // 队列的有效个数+1 ++pq->size; }
入队列操作只能是在队尾操作，我们可以通过尾指针去找到尾结点，然后在尾结点后面插入即可，需要注意的是，如果队列中没有数据的话，新结点就相当于即是尾结点又是首元结点，这个情况需要改变两个指针。
5.出队列
void QueuePop(Queue* pq) { assert(pq); // 队列为空不能删除 assert(pq->phead); // 临时指针指向首元结点 QNode* tmp = pq->phead; // 当队列中只有一个结点时 if (pq->phead == pq->ptail) { // 将两个指针置空 pq->phead = pq->ptail = NULL; } // 当队列中不止一个结点时 else { // 让头结点指向第二个结点 pq->phead = pq->phead->next; } // 有效数据个数-1 --pq->size; // 释放原首元结点的空间 free(tmp); // 释放空间后指针置空 tmp = NULL; }
出队列与入队列一样，也要判断边界情况，当队列中没有元素时，无法进行出队列操作，当队列中只有一个元素时，出的元素就是首元结点，出完后队列变成空队列。
6.查询队头数据
QDataType QueueFront(Queue* pq) { assert(pq); // 队列不为空才有队头数据 assert(pq->phead); // 根据头指针找到队头数据 return pq->phead->val; }
由于我们的结构体里面包含了头指针，而头指针指向首元结点，首元结点就是队头数据，所以使用头指针便可找到队头数据。
7.查询队尾数据
QDataType QueueBack(Queue* pq) { assert(pq); // 也是指队列不为空才能有队尾数据 assert(pq->ptail); // 根据尾指针找到队尾数据 return pq->ptail->val; }
结构体里面不仅仅包含了头指针，还包含了尾指针，尾指针指向尾结点，尾结点就是队尾数据，所以使用尾指针便可找到队尾数据。
8.判断队列是否为空
bool QueueEmpty(Queue* pq) { assert(pq); // 返回队列有效数据的个数是否等于0来判断队列是否为空 return pq->size == 0; }
size 的值就是队列中的有效数据个数，如果队列中有效数据的个数为0，那就说明队列中无有效数据，就是空队列，反之就不是空队列。
9.查询队列中有效数据的个数
int QueueSize(Queue* pq) { assert(pq); // 返回有效数据的个数 return pq->size; }
我们在上面说过，size的值就是有效数据的个数，所以在这里直接返回size的值即可。
五、代码整合及结果演示
1.代码整合
若在整合后出现某些函数不安全的错误，请在头文件里面加上下面这行代码。
#define _CRT_SECURE_NO_WARNINGS 1
1.头文件 Queue.h 部分
#include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> // 队列的数据类型 typedef int QDataType; // 队列的结构体 typedef struct QueueNode { // 队列的数据域 QDataType val; // 队列的指针域 struct QueueNode* next; }QNode; // 传参结构体 typedef struct Queue { // 有一个指向队列的首元结点(队头)的指针 QNode* phead; // 有一个指向队列的尾结点(队尾)的指针 QNode* ptail; // 队列的元素个数 int size; }Queue; // 初始化队列 void QueueInit(Queue* pq); // 销毁队列 void QueueDestroy(Queue* pq); // 在队尾插入 void QueuePush(Queue* pq, QDataType x); // 在队头弹出 void QueuePop(Queue* pq); // 查询队头元素 QDataType QueueFront(Queue* pq); // 查询队尾元素 QDataType QueueBack(Queue* pq); // 判断队列是否为空 bool QueueEmpty(Queue* pq); // 查询队列元素个数 int QueueSize(Queue* pq);
2.源文件 Queue.c 部分
#include"Queue.h" void QueueInit(Queue* pq) { // pq是指向传参结构体的指针，不可能为空，为空说明传参错误 assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; } void QueueDestroy(Queue* pq) { assert(pq); while (pq->phead) { QNode* tmp = pq->phead; pq->phead = pq->phead->next; free(tmp); tmp = NULL; } pq->ptail = NULL; pq->size = 0; } void QueuePush(Queue* pq, QDataType x) { assert(pq); // 为新结点开辟空间 QNode* newNode = (QNode*)malloc(sizeof(QNode)); if (newNode == NULL) { perror("malloc fail"); exit(-1); } // 为新结点赋值 newNode->val = x; newNode->next = NULL; // 当队列为空时 if (pq->ptail == NULL) { pq->phead = pq->ptail = newNode; } // 当队列非空时 else { pq->ptail->next = newNode; pq->ptail = newNode; } ++pq->size; } void QueuePop(Queue* pq) { assert(pq); // 队列为空不能删除 assert(pq->phead); QNode* tmp = pq->phead; // 当队列中只有一个结点时 if (pq->phead == pq->ptail) { pq->phead = pq->ptail = NULL; } // 当队列中不止一个结点时 else { pq->phead = pq->phead->next; } --pq->size; free(tmp); tmp = NULL; } QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->phead); return pq->phead->val; } QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->ptail); return pq->ptail->val; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; } int QueueSize(Queue* pq) { assert(pq); return pq->size; }
3.源文件 test.c 部分
#include"Queue.h" void test() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); QueuePush(&q, 5); while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } printf("\n"); QueueDestroy(&q); return 0; } int main() { test(); return 0; }
2.结果演示
总结
本篇文章到这里就结束了，栈和队列部分其实还是比较简单的，总体难度不是很难。我只是使用了链表实现了队列，感兴趣的可以尝试使用顺序表来实现一下，相信对自己肯定会有帮助。
文章虽然比较简单，但是也并非绝对不可能出现错误，如果在文章中发现了错误，欢迎指正，谢谢。如果这篇文章对你有所帮助，别忘了三连博主，您的支持是我最大的鼓励，我会尽可能的去写出更加优质的文章。谢谢。
