数据结构——队列
目录
一、队列的定义
队列中的数据元素的逻辑关系呈线性关系，可以说队列也是一种线性表，队列可以像线性表一样采用顺序存储结构存储，也可以使用链式存储结构进行存储。使用顺序存储结构的队列称为顺序队，使用链式存储结构的队列称为链队。
队列和栈类似，栈只能在一端进行删除和插入操作，而队列也是一种操作受限的线性表，其限制为仅允许在表的一端进行插入操作，而在表的另一端进行删除操作。进行插入的一端称为队尾，进行删除的一端称为队首。向队列中插入新元素称为进队或入队，新元素进入队列后就成为新的队尾元素；从中删除元素称为出队或离队，元素出队后，其直接后继元素就成为队首元素。如下图所示。
二、队列的实现
1. 队列的顺序存储结构
队列使用顺序存储结构存储相对比较简单，操作和栈类似，但有几点地方需要注意，队列有两端可以操作，需要两个指针或索引，队列是否为空和入队和出队需要队考虑几种情况。
要使用顺序存储结构存储队列，需要将队列元素映射到顺序表中，顺序表地址都是连续的，队列元素可以直接按照顺序映射到属性表中，如下图所示。
只要确定了队首元素所在顺序表的位置，其他的元素按照顺序接入即可。一般队首元素是位于顺序表的首地址，不过在顺序队进行出队操作后队首元素位置会不断后移。
顺序队的定义：
template<typename T>
class MyQueue
{
private:
T* data; // 队列顺序存储结构
int front, rear; // 队首索引，队尾索引
int size; // 队列长度
public:
// 构造函数
MyQueue();
// 析构函数
~MyQueue();
// 入队
bool push(T value);
// 出队
bool pop();
// 判断队满
bool full();
// 判断队空
bool empty();
// 获取队首元素
T getFront();
// 获取队列长度
int getSize();
};
?顺序队有两种实现方式，一种是普通的顺序队，即元素按顺序存储，入队后队尾位置不断后移，出队后队首位置也不断后移，也就是队列可存储的空间只会越来越少，就算队首出队，队列的空间也不会增多，队列会在一次次入队操作后接近满队，会存在大量的空间浪费。另一种就是改进的顺序队，即环形队，环形队会在空间不够用时，从数组首地址从新开始存储，类似于循环链表，能够循环利用数组空间。
1.1. 顺序队
顺序队按顺序存储队列元素，插入元素时与栈类似，先将队尾索引加一再将对应位置写入新元素的值，不过在第一次插入元素时需要多一步操作。删除元素是将队首索引先加一再新索引位置写入新元素的值，在队列只剩一个元素的时候需要进行特殊的处理。
1. 创建顺序队
创建一个空的顺序队需要申请一片连续的存储空间（数组）用于存储队列元素，再初始化索引front和rear以及队列长度size。front和size初始化都为-1，size初始化为0 。
MyQueue() {
data = new T[MAXSIZE2];
front = rear = -1;
size = 0;
}2.?删除顺序队
删除顺序队只需要将申请的存储空间全部释放即可。
~MyQueue() {
delete[] data;
}3. 判断队列是否为空
判断条件是front和rear的值为初始值-1（队列出队得只剩一个元素的时候也会将front和rear设置为初始值-1）。
bool empty() {
return (front == -1 && rear == -1);
}4. 判断队列是否已满
顺序队的存储空间跟存储数组的大小有关，存储数组的大小是事先设定的宏定义值MAXSIZE，判断队尾索引是否等于MAXSIZE-1（数组地址从0开始）。
bool full() {
return rear == MAXSIZE2 - 1;
}5. 入队
入队和出队相较于栈要麻烦一点，需要多一步判断。在队列为空的时候入队不能只将rear的值加一，因为此时front为-1，只修改rear的值的话，访问队首的时候front为-1就会出错，因此需要同时修改front和rear的值，将它们的值都修改为0 。此外，顺序队因为存储结构的原因，队列是会满的（跟存储数组的大小相关），队列满时无法入队，返回false。
其他正常情况下，入队的操作为，将rear索引后移一位，将新元素的值写入新rear的位置，即将新元素插入到存储数组的末尾。如下图所示。
bool push(T value) {
// 队列满
if (full()) {
return false;
}
// 队列空，修改rear和front的值为0，否则无法访问队首元素
if (empty()) {
rear = front = 0;
}
// 其他情况，在原队尾元素的下一个位置插入元素
else {
rear++;
}
// 写入新元素的值
data[rear] = value;
// 入队操作后队列长度加一
size++;
return true;
}6. 出队
出队操作只需将front索引后移一位即可，不用修改front索引元素的值。但在队列只有一个元素的时候需要将front和rear的值都改为初始值，因为队列为空的条件是front和rear的值都为-1 。如下图。
bool pop() {
// 队列空
if (empty()) {
return false;
}
if (front == rear) {
front = rear = -1;
}
else {
front++;
}
size--;
return true;
}7. 获取队列长度
int getSize() {
return size;
}完整MyQueue类：
#pragma once
#define MAXSIZE2 10000
#include<stdexcept>
using namespace std;
template<typename T>
class MyQueue
{
private:
T* data;
int front, rear;
int size;
public:
MyQueue() {
data = new T[MAXSIZE2];
front = rear = -1;
size = 0;
}
~MyQueue() {
delete[] data;
}
bool push(T value) {
// 队列满
if (full()) {
return false;
}
// 队列空，修改rear和front的值为0，否则无法访问队首元素
if (empty()) {
rear = front = 0;
}
// 其他情况，在原队尾元素的下一个位置插入元素
else {
rear++;
}
// 写入新元素的值
data[rear] = value;
// 入队操作后队列长度加一
size++;
return true;
}
bool pop() {
// 队列空
if (empty()) {
return false;
}
// 队列只剩一个元素，出队后将front和rear的值都设为初始值
// front和rear都为初始值才能判断队列为空
if (front == rear) {
front = rear = -1;
}
// 其他情况，将front索引后移一位即可
else {
front++;
}
size--;
return true;
}
bool full() {
return rear == MAXSIZE2 - 1;
}
bool empty() {
return (front == -1 && rear == -1);
}
T getFront() {
if (empty()) {
throw out_of_range("队列为空，无法访问队首元素");
}
return data[front];
}
int getSize() {
return size;
}
};
8. 获取队首元素?
T getFront() {
if (empty()) {
throw out_of_range("队列为空，无法访问队首元素");
}
return data[front];
}测试：
对队列的empty()、getSize()、push()、pop()操作都测试一遍。
MyQueue<string> qu;
cout << "队列是否为空：" << qu.empty() << "\t队列长度：" << qu.getSize() << endl;
cout << "入队：'lin'" << endl;
qu.push("lin");
cout << "队列是否为空：" << qu.empty() << "\t队列长度：" << qu.getSize() << "\t队首元素：" << qu.getFront() << endl;
cout << "入队：'zixi'" << endl;
qu.push("zixi");
cout << "队列是否为空：" << qu.empty() << "\t队列长度：" << qu.getSize() << "\t队首元素：" << qu.getFront() << endl;
cout << "出队" << endl;
qu.pop();
cout << "队列是否为空：" << qu.empty() << "\t队列长度：" << qu.getSize() << "\t队首元素：" << qu.getFront() << endl;
cout << "出队" << endl;
qu.pop();
cout << "队列是否为空：" << qu.empty() << "\t队列长度：" << qu.getSize() << endl;测试结果：
测试结果正确。?
1.2. 环形队
1. 创建环形队
环形队只在rear和front索引操作上与顺序队不同，其他的操作都是一样的。
CirQueue() {
data = new T[MAXSIZE2];
front = rear = -1;
size = 0;
}2. 删除环形队
~CirQueue() {
delete[] data;
}3. 判断环形队列是否为空?
bool empty() {
return (front == -1 && rear == -1);
}4. 判断环形队列是否已满
判断环形队列是否已满与顺序队不同，顺序队只需要判断尾索引是否达到最大的索引，而环形队列的存储空间是循环利用的，队尾索引到达最大索引时会返回数组首地址再顺序往下，判断环形队列已满的条件应该时rear的下一个位置刚好时front的位置，因为环形队列时循环利用数组空间的，rear+1需要对MAXSIZE取余。下图就是一个满的环形队列。
bool full() {
return (rear + 1) % MAXSIZE2 == front;
}5. 入队
具体操作其实和顺序队很相似，只是rear加一的时候需要队MAXSIZE取余。如下图所示。
bool push(T value) {
// 队列满
if (full()) {
return false;
}
// 队列空，修改rear和front的值为0，否则无法访问队首元素
if (empty()) {
rear = front = 0;
}
else {
rear = (rear + 1) % MAXSIZE2;
}
data[rear] = value;
size++;
return true;
}6. 出队
与入队一样，元素出队的时候front+1时需要对MAXSIZE取余，其余操作与顺序队一样。
bool pop() {
// 队列空
if (empty()) {
return false;
}
// 队中只有一个元素
if (front == rear) {
front = rear = -1;
}
else {
front = (front + 1) % MAXSIZE2;
}
size--;
return true;
}7. 获取队列长度
int getSize() {
return size;
}8. 获取队首元素
T getFront() {
if (empty()) {
throw out_of_range("队列为空，无法访问队首元素");
}
return data[front];
}测试：
对于环形队列，测试需要体现它的特性，即存储空间循环利用，再一个元素出队列后，队列可用空间会增加。回了简化测试，将MAXSIZE的值改为2，先插入两个元素，再插入一个元素，此时队列满了，无法插入，进行出队操作后可以插入。
// 循环队列
CirQueue<string> qu;
cout << "队列是否为空：" << qu.empty() << "\t队列长度：" << qu.getSize() << endl << endl;
cout << "入队：'lin'" << endl;
qu.push("lin");
cout << "队列是否为空：" << qu.empty() << "\t队列长度：" << qu.getSize() << "\t队首元素：" << qu.getFront() << endl << endl;
cout << "入队：'zi'" << endl;
qu.push("zi");
cout << "队列是否为空：" << qu.empty() << "\t队列长度：" << qu.getSize() << "\t队首元素：" << qu.getFront() << endl << endl;
cout << "入队：'xi'" << endl;
cout << "入队是否成功：" << qu.push("xi") << endl;
cout << "队列是否为空：" << qu.empty() << "\t队列长度：" << qu.getSize() << "\t队首元素：" << qu.getFront() << endl << endl;
cout << "出队" << endl;
qu.pop();
cout << "队列是否为空：" << qu.empty() << "\t队列长度：" << qu.getSize() << "\t队首元素：" << qu.getFront() << endl << endl;
cout << "入队：'xi'" << endl;
cout << "入队是否成功：" << qu.push("xi") << endl;
cout << "队列是否为空：" << qu.empty() << "\t队列长度：" << qu.getSize() << "\t队首元素：" << qu.getFront() << endl << endl;
cout << "出队" << endl;
qu.pop();
cout << "队列是否为空：" << qu.empty() << "\t队列长度：" << qu.getSize() << "\t队首元素：" << qu.getFront() << endl << endl;
cout << "出队" << endl;
qu.pop();
cout << "队列是否为空：" << qu.empty() << "\t队列长度：" << qu.getSize() << endl;测试结果：
?从上图可以看到，再插入两个元素”lin”和“zi”后，队列此时已满，再插入一个元素会失败，将队首出队后，"xi"就能成功插入了。
2. 队列的链式存储结构
顺序队有一个很明显的缺陷，可用空间有限，而且是实现定义的，无法动态扩充，且会出现空间浪费的情况。为了解决这些问题，可以使用链式存储结构来存储队列。链式存储就是使用链表存储。
链队实现起来其实也比较简单，因为只需要对两端进行操作，比链表的操作简单很多。
链队需要一个结点结构，包含结点的信息和下一个结点的地址，同时为其定义一个有参构造函数，定义如下：
template<typename T>
struct QueNode
{
T data;
QueNode* next;
QueNode(T value) {
data = value;
next = NULL;
}
};链队的定义如下：
template<typename T>
class LkQueue
{
private:
// 队首结点指针
QueNode<T>* front;
// 队尾结点指针
QueNode<T>* rear;
// 队列长度
int size;
public:
// 无参构造，创建空链队
LkQueue();
// 析构函数，删除链队
~LkQueue();
// 判断链队是否为空
bool empty();
// 入队
void push(T value);
// 出队
bool pop();
// 获取队首元素
T getFront();
// 获取队列长度
int getSize();
};1. 创建链队
初始化front和rear指针为空指针NULL，size为0。
LkQueue() {
front = rear = NULL;
size = 0;
}2. 删除链队
删除链队即删除链队存储的链表，链表删除方式之前已经介绍过了。遍历链表的每一个结点，删除即可。
~LkQueue() {
while (front != NULL)
{
// 保存front指针，用于删除
QueNode<T>* temp = front;
// front继续指向下一个结点，需要在删除结点前，否则无法取next
front = front->next;
delete temp;
}
}3. 判断链队是否为空
判断链队是否为空的条件式front和rear指针都为NULL；
bool empty() {
return (front == NULL && rear == NULL);
}4. 入队
链队不用担心空间不够的问题，只需要在首次入队的时候将front和rear同时指向新结点，其他情况使用尾插法插入新结点即可。
void push(T value) {
QueNode<T>* newNode = new QueNode<T>(value);
// 如果是空链队，则初始化front和rear同时指向新结点
if (empty()) {
front = rear = newNode;
}
else {
// 尾插法添加新结点
rear->next = newNode;
rear = newNode;
}
size++;
}5. 出队
链队出队与顺序队不一样，顺序队只需要将指针往下移就可以了，因为数组的存储空间不能只释放一块的地址，所以不需要释放空间也不需要修改该位置的值（环形队也不需要，它会在下一次插入到该位置时修改该位置的值），而链队的结点出队后不会再使用到它，而且它是单独存放在一个地址，可以直接释放。出队时，front指向front->next，同时释放front指向的地址空间。
bool pop() {
if (empty()) {
return false;
}
// 链队和顺序队不一样，链队结点出队后，这块空间就不会再被使用了，需要删除
QueNode<T>* temp = front;
front = front->next;
delete temp;
size--;
}6. 获取队首元素
T getFront() {
if (empty()) {
throw out_of_range("队列为空，无法访问队首元素");
}
return front->data;
}7. 获取链队长度?
int getSize() {
return size;
}完整的链队类：
#pragma once
template<typename T>
struct QueNode
{
T data;
QueNode* next;
QueNode(T value) {
data = value;
next = NULL;
}
};
template<typename T>
class LkQueue
{
private:
QueNode<T>* front;
QueNode<T>* rear;
int size;
public:
// 无参构造，创建空链队
LkQueue() {
front = rear = NULL;
size = 0;
}
// 析构函数，删除链队
~LkQueue() {
while (front != NULL)
{
// 保存front指针，用于删除
QueNode<T>* temp = front;
// front继续指向下一个结点，需要在删除结点前，否则无法取next
front = front->next;
delete temp;
}
}
bool empty() {
return (front == NULL && rear == NULL);
}
void push(T value) {
QueNode<T>* newNode = new QueNode<T>(value);
// 如果是空链队，则初始化front和rear同时指向新结点
if (empty()) {
front = rear = newNode;
}
else {
// 尾插法添加新结点
rear->next = newNode;
rear = newNode;
}
size++;
}
bool pop() {
if (empty()) {
return false;
}
// 链队和顺序队不一样，链队结点出队后，这块空间就不会再被使用了，需要删除
QueNode<T>* temp = front;
front = front->next;
delete temp;
size--;
}
T getFront() {
if (empty()) {
throw out_of_range("队列为空，无法访问队首元素");
}
return front->data;
}
int getSize() {
return size;
}
};
三、队列的应用
使用队列完成两道pta的题目来实际应用一下队列。
1. 银行业务队列简单模拟
设某银行有A、B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时，B窗口处理完1个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口顾客优先输出。
输入格式:
输入为一行正整数，其中第1个数字N(≤1000)为顾客总数，后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务，为偶数的顾客则去B窗口。数字间以空格分隔。
输出格式:
按业务处理完成的顺序输出顾客的编号。数字间以空格分隔，但最后一个编号后不能有多余的空格。
输入样例:
8 2 1 3 9 4 11 13 15
输出样例:
1 3 2 9 11 4 13 15#include<iostream>
#include<queue>
using namespace std;
int main()
{
int n,s,x,l=0;
cin>>n;
queue<int> q1,q2;
while(n--)
{
cin>>s;
if(s%2==0)
q2.push(s);
else
q1.push(s);
}
while(!q2.empty() || !q1.empty())
{
// 格式问题，需要分两种情况输出
if(l==0 && !q1.empty()){
x=q1.front();
cout<<x;
q1.pop();
x=q1.front();
cout<<" "<<x;
q1.pop();
l++;
}
else{
for(int i=0;i<2;i++)
if(!q1.empty()){
x=q1.front();
cout<<" "<<x;
q1.pop();
}
}
if(!q2.empty())
{
x=q2.front();
if(l==0){
cout<<x;l++;}
else
cout<<" "<<x;
q2.pop();
}
}
}这是当初学数据结构时写的代码，写得有点乱，为了偷懒还直接用的c++的queue类，没有自己实现。这题也没什么难度，就是q1和q2依次出队，每轮出队，q1优先出队，而且出队两个，q2次之，每次出一个，依次输出就好了。
2. 求解迷宫从入口到出口的一条最短路径
求解迷宫从入口到出口的一条最短路径。输入一个迷宫，求从入口通向出口的一条可行最短路径。为简化问题，迷宫用二维数组 int maze[10][10]来存储障碍物的分布，假设迷宫的横向和纵向尺寸的大小是一样的，并由程序运行读入, 若读入迷宫大小的值是n（3<n<=10），则该迷宫横向或纵向尺寸都是n，规定迷宫最外面的一圈是障碍物，迷宫的入口是maze[1][1]，出口是maze[n-2][n-2], 若maze[i][j] = 1代表该位置是障碍物，若maze[i][j] = 0代表该位置是可以行走的空位（0<=i<=n-1, 0<=j<=n-1）。求从入口maze[1][1]到出口maze[n-2][n-2]可以走通的路径。要求迷宫中只允许在水平或上下四个方向的空位上行走，走过的位置不能重复走，规定必须按向右、向下、向左、向上的顺序向前搜索试探，输出先到达出口的最短路径。
如下这样一个迷宫：
对应的二维数组表示：
int maze[10][10]={
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,1,1},
{1,0,0,0,1,0,0,0,1,1},
{1,0,1,0,0,0,1,0,0,1},
{1,1,1,1,0,1,1,0,1,1},
{1,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}};
输入格式:
输入迷宫大小的整数n, 以及n行和n列的二维数组（数组元素1代表障碍物，0代表空位）。
输出格式:
输出按规定搜索试探顺序先到达出口的首条最短路径，依次输出从入口到出口可行最短路径每个位置的行列下标（i,j），每个位置间用“,”分隔。若没有通路，输出：NO。
输入样例1:
4
1 1 1 1
1 0 1 1
1 0 0 1
1 1 1 1
输出样例1:
(1,1)(2,1)(2,2)
输入样例2:
10
1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 1 0 1
1 0 0 1 0 0 0 1 0 1
1 0 0 0 0 1 1 0 0 1
1 0 1 1 1 0 0 0 0 1
1 0 0 0 1 0 0 0 0 1
1 0 1 0 0 0 1 0 0 1
1 0 1 1 1 0 1 1 0 1
1 1 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1
输出样例2:
(1,1)(2,1)(3,1)(4,1)(5,1)(5,2)(5,3)(6,3)(6,4)(6,5)(7,5)(8,5)(8,6)(8,7)(8,8)求迷宫的最短路径用广度优先搜索最合适，广度优先搜索跟树的层次遍历一样，从根依次向下遍历，每次优先遍历一层的结点，然后再向下一层遍历。
使用广度优先搜索求解的步骤是：首先将起点可以达到的点添加进队列中，然后从这个队列中依次取结点出来遍历，当前结点扩展完结点后将子结点全部加入到队列中，重复上面的步骤直到找到一条通路，这题通路就是最短路径。由于子结点都是在父结点的兄弟结点都添加进队列后才进入的队列，因此遍历时会是前一层的结点都遍历完后才到下一层的结点，依次就可以实现广度优先遍历。为什么广度遍历求出的解是最短路径呢？因为广度优先搜索是按层次遍历的，每一层都是当前路径长度下所有的路径，每次增加一个路径长度，遍历该路径长度下所有的路径，第一次出现通路那就一定是最短的路径。
代码：
#include<iostream>
#include<queue>
#define Maxsize 100
struct Box
{
int i;
int j;
}e,pre[Maxsize][Maxsize];
void print(Box t);
using namespace std;
int main()
{
int di_x[4]={-1,0,1,0};int di_y[4]={0,1,0,-1};
int n,i,j,x,y,flag=0,tx,ty;
queue<Box> qe;
cin>>n;
int sx,sy,fx,fy;
sx=sy=1;fx=fy=n-2; //定义起点和终点
e.i=sx;e.j=sy;
qe.push(e);
int mg[n][n]={0};
mg[sx][sy]=-1;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>mg[i][j];
while(!qe.empty())
{
e=qe.front();
x=e.i;y=e.j;
if(x==n-2 && y==n-2){
flag=1;
break;
}
for(i=0;i<4;i++){
tx=x+di_x[i],ty=y+di_y[i];
if(mg[tx][ty]==0){
e.i=tx;
e.j=ty;
pre[tx][ty]=qe.front();
qe.push(e);
mg[tx][ty]=-1;
}
}
qe.pop();
}
if(flag==0){
cout<<"NO"<<endl;exit(0);
}
Box fin={fx,fy};
print(fin);
cout<<endl;
}
void print(Box t)
{
if(t.i==1 && t.j==1){
cout<<"("<<t.i<<","<<t.j<<")";
return;
}
print(pre[t.i][t.j]);
cout<<"("<<t.i<<","<<t.j<<")";
}这个也是当初初学的时候写的代码，我记得当初还没教广度优先遍历，这题应该是要用深度优先遍历暴力求解所有路径找出最短路径的，当时我为了偷懒就直接用广度优先遍历了。
上述代码实现起来也不难，每个结点都对应数组中的一个元素，找每个结点的可通往的结点就是寻找该元素上下左右四个元素中不是障碍物的因素，然后依次将这些结点加入队列就行了，终止条件是当前点是终点。
四、总结
队列与栈一样都是访问受限的线性表，栈是只能在一端进行删除和插入操作的线性表，而队列是只能在一端进行删除操作，在另一端进行插入操作。栈由于只能在一端操作，因此实现起来会很简单，而队列是在两端操作，实现起来比栈稍微麻烦一点，因为需要考虑两端的指针关系问题。
队列能在两端操作的特点导致如果向栈一样使用顺序表存储时会出现存储空间浪费的问题，因为队首和队尾位置会不断后移，而前面的地址空间都将不会在被使用到，导致大量的空间浪费，而且这样的队列很容易满，因为存储空间不会因为元素出队而增大，因此这种简单的顺序队我们一般都不会使用，而是使用更好的环形队，环形队列能够在rear达到最大索引的时候返回首地址继续往下存储，能够循环利用地址空间，不会有空间被浪费。
虽然环形队列相比顺序队列不会浪费空间，但它仍然收到数组空间的限制，不能超出申请的数组空间大小，而数组大小申请后就不能更改，通常会申请一个较大的空间，这样会和顺序表的缺陷一样，会有部分空间浪费，或者空间容易满，解决这个问题的方法就是使用链表存储队列，使用链表存储队列就不用担心存储空间不够的问题，且存储空间是动态变化的，不会有空间浪费。
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！