前言：
在学习完数据结构顺序表和链表之后，其实我们就可以做很多事情了，后面的栈和队列，其实就是对前面的顺序表和链表的灵活运用，今天我们就来学习一下队列的原理和应用。
准备工作：本人习惯将文件放在test.c、SeqList.c、SeqList.h三个文件中来实现，其中test.c用来放主函数，SeqList.c用来放调用的函数，SeqList.h用来放头文件和函数声明
什么是队列？
队列中的数据是按照先进先出的顺序的，也就是说先进去的数字也先出来
因为队列的这种性质，所以队列我们用链表来实现比顺序表方便很多，因为用顺序表每插入一个数或者删除一个数都需要遍历整个数组，这样就会很容易出错且不够方便，我们一般采用单链表来实现队列
队列的节点结构
队列采用的单链表的结构，所以与单链表差异不大
typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }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); //取长度 QDataType QueueSize(Queue* pq); //判断是否为空 bool QueueEmpty(Queue* pq);
看上面的函数声明部分我们就可以看到我们每一步要实现的内容，接下来，我们就来一步一步进行实现
1、初始化
//初始化 void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; }
参数全是一个结构体指针，而且肯定不能为空，所以我们下面的函数基本都要对pq进行断言
2、销毁
将头指针指向的空间逐个释放，最后把头指针和尾指针均赋为空指
//销毁 void QueueDestroy(Queue* pq) { QNode* cur = pq->phead; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; }
3、增加（插入数据）
因为先进先出，实际上数据就是从尾部插入，从头部出去，即插入形式为尾插
//插入 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); newnode->data = x; newnode->next = NULL; //判断头部是否为空 if (pq->phead == NULL) { pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; }
用单链表插入数据必须要考虑头部为空和不为空两种情况
4、删除
栈和队列都有一个特点就是，数据只会输出一遍，也就是数据一经输出就会销毁删除
如下：
1在输出之后就会被删除，删除的代码如下：
//删除 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); //1、一个节点 //2、多个节点 if (pq->phead->next == NULL) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { QNode* ptr = pq->phead->next; free(pq->phead); pq->phead = ptr; } }
这里面又分为两种情况，难度不大，根据注释自行体会即可
5、取队头、取队尾、取长度、判断头指针是否为空
这几步难度不大，放在一起看看
取队头
//取队头 QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->phead->data; }
取队尾
//取队尾 QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->ptail->data; }
取长度
//取长度 QDataType QueueSize(Queue* pq) { assert(pq); return pq->size; }
判断头指针是否为空（这个函数应用上可以在下面的完整案列上体会一下）
bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL; }
完整的队列实例
test.c
//队列 void TestQNode() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); printf("%d\n", QueueSize(&q)); while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } QueueDestroy(&q); } int main() { TestQNode(); return 0; }
SeqList.h
//队列 typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }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); //取长度 QDataType QueueSize(Queue* pq); //判断是否为空 bool QueueEmpty(Queue* pq);
SeqList.c
//初始化 void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; } //销毁 void QueueDestroy(Queue* pq) { QNode* cur = pq->phead; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; } //插入 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); newnode->data = x; newnode->next = NULL; if (pq->phead == NULL) { pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } //删除 void QueuePop(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); //1、一个节点 //2、多个节点 if (pq->phead->next == NULL) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { QNode* ptr = pq->phead->next; free(pq->phead); pq->phead = ptr; } } //取队头 QDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->phead->data; } //取队尾 QDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->ptail->data; } //取长度 QDataType QueueSize(Queue* pq) { assert(pq); return pq->size; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL; }
运行后结果：
总结
总之，其实队列就是对链表的应用，熟练栈和队列，对我们巩固顺序表和链表帮助很大，当然，队列在一些场景下很实用，后面我会出一个专门的习题讲解篇章，讲数据结构的一些经典题型，感兴趣的可以点赞关注一下
创作不易，还请各位大佬点赞支持一下！！！
