一、队列的基本概念
队列和我们之前学习的栈一样，它也是一种特殊的线性表。它只允许在一端插入数据，在另一端删除数据，不允许对中间的元素进行操作，因而也不支持随机访问。队列具有先进先出的特性FIFO（(First In First Out）。
入队： 队列 的插入操作叫做入队，插入数据的一端称作队头
出队： 队列 的删除操作叫做出队，删除数据的一端称作队尾
二、队列实现方法的选择
2.1 引入
在上次栈的实现中，我们说到可以用顺序存储结构和链式存储结构来表示栈。经过之前我们的分析，我们选择了使用顺序表来实现栈，这是由于栈的插入删除操作完美适配顺序表尾插尾删效率高的特性。
2.2 选择
由于队列需要在两端进行操作，而顺序表在头部的操作效率很低，需要移动大量数据，直接pass掉。我们本期将采用单链表的形式来实现队列。特别的，为了提高单链表尾插的效率，除了必要的头指针我们又定义了一个尾指针指向链表的尾部，大幅提高了单链表尾插的效率。当然，实现队列的方式多种多样，并不是只能用单链表来实现队列。
三、队列接口的实现
📖3.1 初始化
在我们使用队列结构进行操作之前需要对其进行初始化，具体代码如下：
void QueueInit(Que* pq) { assert(pq); pq->first = NULL; pq->tail = NULL; pq->size = 0; }
📖3.2 销毁
当我们不再使用它是要对它进行销毁，，具体代码如下：
// 销毁队列 void QueueDestroy(Que* pq) { assert(pq); QNode* cur = pq->first; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->first = pq->tail = NULL; pq->size = 0; }
📖3.3 入队
由于队列只允许在固定的一端插入，我们又将链表尾当做队尾，因此入队就是尾插。在没有尾指针之前，我们还要先找到链表尾，但我们现在有了尾指针，一切都方便起来了。效果和代码如下：
// 队尾入队列 void QueuePush(Que* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; if (pq->tail == NULL) { pq->tail = pq->first = newnode; } else { pq->tail->next = newnode; pq->tail = pq->tail->next; } pq->size++; }
📖3.4 出队
入队在链表尾，那么出队就是在链表头了；入队对应着链表的尾插，则出队就是头删。链表的头删很简单，只需要释放结点，将头指针指向下一个结点即可。效果如下：
但是，如果只是这样还不够！试想一下，当队列只剩下一个元素时，如果我们再进行出队，头指针没问题指向空，那尾指针呢？由于我们没有去修改，它指向了已经释放空间，显然是不合理的。因此在这种情况下我们还需将尾指针置为NULL。
// 队头出队列 void QueuePop(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->first->next == NULL) { free(pq->first); pq->first = pq->tail = NULL; } else { QNode* next = pq->first->next; free(pq->first); pq->first = next; } pq->size--; }
📖3.5 求队头元素
很简单，我们可以直接根据头指针得到队头的元素，如下：
// 获取队列头部元素 QDataType QueueFront(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->first->data; }
📖3.6 求队尾元素
一样的，通过尾指针可以快速定位队尾的位置，得到队尾的元素，如下：
// 获取队列队尾元素 QDataType QueueBack(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; }
📖3.7 判空
当队列为空时，队头指针和队尾指针都为NULL，我们选其一判断即可。代码如下：
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 bool QueueEmpty(Que* pq) { assert(pq); return pq->first == NULL; }
📖3.8 求队列元素个数
直接返回size即可，代码如下：
// 获取队列中有效元素个数 int QueueSize(Que* pq) { assert(pq); return pq->size; }
📖3.9 总结
- 与栈同理，队列也是一种限制型的数据结构，不支持随机访问。其只允许在固定的两端进行操作。因此也不存在查找，打印，修改等需要对其他位置进行操作的接口，否则会破坏队列的特性。
- 数据结构的实现方式多种多样，为了在隐藏设计细节的情况下使用方依旧能够很方便的使用，尽管有一些操作仅仅只有一两行代码，我们还是封装成函数作为对外的接口供使用方调用。
四、队列的完整代码及效果展示
老样子，我们采用多文件编写的形式，将上述接口的定义实现放在Queue.c文件中，然后将接口的声明和结构体的定义放于Queue.h头文件中，以达到封装的效果。这样我们如果需要使用队列，就只需要在文件中包含对应的头文件Queue.h就可以使用我们上面定义的各种接口。以下为本文实现的队列完整代码以及效果展示：
Queue.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int QDataType; // 链式结构：表示队列 typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; // 队列的结构 typedef struct Queue { QNode* first; QNode* tail; int size; }Que; // 初始化队列 void QueueInit(Que* pq); // 销毁队列 void QueueDestroy(Que* pq); // 队尾入队列 void QueuePush(Que* pq, QDataType x); // 队头出队列 void QueuePop(Que* pq); // 获取队列头部元素 QDataType QueueFront(Que* pq); // 获取队列队尾元素 QDataType QueueBack(Que* pq); // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 bool QueueEmpty(Que* pq); // 获取队列中有效元素个数 int QueueSize(Que* pq);
Queue.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" // 初始化队列 void QueueInit(Que* pq) { assert(pq); pq->first = NULL; pq->tail = NULL; pq->size = 0; } // 队尾入队列 void QueuePush(Que* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; if (pq->tail == NULL) { pq->tail = pq->first = newnode; } else { pq->tail->next = newnode; pq->tail = pq->tail->next; } pq->size++; } // 队头出队列 void QueuePop(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); if (pq->first->next == NULL) { free(pq->first); pq->first = pq->tail = NULL; } else { QNode* next = pq->first->next; free(pq->first); pq->first = next; } pq->size--; } // 获取队列头部元素 QDataType QueueFront(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->first->data; } // 获取队列队尾元素 QDataType QueueBack(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; } // 获取队列中有效元素个数 int QueueSize(Que* pq) { assert(pq); return pq->size; } // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 bool QueueEmpty(Que* pq) { assert(pq); return pq->first == NULL; } // 销毁队列 void QueueDestroy(Que* pq) { assert(pq); QNode* cur = pq->first; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->first = pq->tail = NULL; pq->size = 0; }
test.c
#include"Queue.h" void test() { Que q; //初始化 QueueInit(&q); //求元素个数 printf("入队前队列的元素个数为:%d\n", QueueSize(&q)); //入队，插入5个元素 for (int i = 1; i <= 5; i++) { QueuePush(&q, i); } printf("入队后队列的元素个数为:%d\n", QueueSize(&q)); //由于无法遍历打印，我们就交替使用 求队头元素-出队 来显示队中元素 printf("队中元素:> "); while (!QueueEmpty(&q)) { //求队头元素 printf("%d ", QueueFront(&q)); //出队 QueuePop(&q); } //全部出队 printf("\n全部出队后队列的元素个数为:%d\n", QueueSize(&q)); //销毁 QueueDestroy(&q); } int main() { test(); return 0; }
测试效果：
本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言，小羊一定认真修改，写出更好的文章~~
