算法模板之队列图文详解

在这里插入图片描述
🌈个人主页：聆风吟
🔥系列专栏：算法模板、数据结构
🔖少年有梦不应止于心动，更要付诸行动。

文章目录

📋前言
一. ⛳️模拟队列
- 1.1 🔔用数组模拟实现队列
- - 1.1.1 👻队列的定义
  - 1.1.2 👻初始化队列
  - 1.1.3 👻向队尾插入一个数 x（入队列）
  - 1.1.4 👻从队头弹出一个数（出队列）
  - 1.1.5 👻判断队列是否为空
  - 1.1.6 👻查询队头元素
- 1.2 🌟模板提取(重点)🌟
- - 1.2.1 👻无详细注释版
  - 1.2.2 👻有详细注释版
二. ⛳️题目练习
- 2.1 题目
- 2.2 输入样例
- 2.3 输出样例
- 2.4 c++代码
📝结语

📋前言

💬 hello! 各位铁子们大家好哇，我们上期已经带大家学习了栈的模板，相信爱学习的你都熟练掌握了，如果你还需要查漏不缺可以通过下面专栏自行跳转学习，今天作者给大家带来了队列的算法模板讲解，让我们一起加油进步。
📚 系列专栏：本期文章收录在《算法模板》，大家有兴趣可以浏览和关注，后面将会有更多精彩内容！
🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

一. ⛳️模拟队列

1.1 🔔用数组模拟实现队列

1.1.1 👻队列的定义

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。如下图所示：
在这里插入图片描述
由于我们使用数组去模拟队列，因此可以将队列看成是一个特殊的数组：这个数组，最前面叫队头，最后面叫队尾。只允许在最后面添加元素，并并且只允许在最前面删除元素。如下图所示：

1.1.2 👻初始化队列

初始状态：我们可以将数组的队头指针指向数组下表为0的位置，队尾指向-1位置，因为满足 tt < hh，所以初始状态队列为空。
在这里插入图片描述 代码展示（建议结合图示看注释）：

//初始化
//定义一个数组q用于存储队列中的元素
int q[N];
int hh = 0;//hh表示队头
int tt = -1;//tt表示队尾

1.1.3 👻向队尾插入一个数 x（入队列）

根据以上可知：如果我们想向队尾插入一个元素x（即进行入队列操作），我们只需要将队尾指针tt向后移动一位，并将待插入元素 x 存入队尾指针tt指向的位置。
在这里插入图片描述 代码展示（建议结合图示看注释）：

//向队尾插入一个数
//入队：队尾先往后移动一格，再放入要插入的数据 x
q[++tt] = x;

1.1.4 👻从队头弹出一个数（出队列）

根据以上可知：如果我们要将一个队列从队头弹出一个数（即进行出队列操作），我们只需要将队头指针向后移动一位即可将队头元素移除。如下图所示：
在这里插入图片描述 代码展示（建议结合图示看注释）：

//从队头弹出一个数
//出队：队头往后移动一格
hh++;

1.1.5 👻判断队列是否为空

根据以上可知：判断一个队列是否为空，我们只需要判断队头指针hh和队尾指针tt大小：

如果tt >= hh，说明队列不为空；
如果tt < hh，说明队列为空。

在这里插入图片描述 代码展示（建议结合图示看注释）：

//判断队列是否为空
//[hh, tt]表示队列区间，当tt >= hh时，区间不为空
if(tt >= hh)
{
	//输出队列不为空
}
else
{
	//输出队列为空
}

1.1.6 👻查询队头元素

根据以上可知：查询队头元素只需要将头指针指向的数据输出即可，如下图所示：
在这里插入图片描述 代码展示（建议结合图示看注释）：

//查询队头元素
//hh指向队头，q[hh]代表队头元素
q[hh];

1.2 🌟模板提取(重点)🌟

1.2.1 👻无详细注释版

c++代码模板：

//初始化
int q[N];
int hh = 0;//hh表示队头
int tt = -1;//tt表示队尾

//向队尾插入一个数
q[++tt] = x;

//从队头弹出一个数
hh++;

//判断队列是否为空
if(tt >= hh)
{
	//输出队列不为空
}
else
{
	//输出队列为空
}

//查询队头元素
q[hh];

1.2.2 👻有详细注释版

c++代码模板：

//初始化
int q[N];//定义一个数组q用于存储队列中的元素
int hh = 0;//hh表示队头
int tt = -1;//tt表示队尾

//向队尾插入一个数
//入队：队尾先往后移动一格，再放入要插入的数据 x
q[++tt] = x;

//从队头弹出一个数
//出队：队头往后移动一格
hh++;

//判断队列是否为空
//[hh, tt]表示队列区间，当tt >= hh时，区间不为空
if(tt >= hh)
{
	//输出队列不为空
}
else
{
	//输出队列为空
}

//查询队头元素
//hh指向队头，q[hh]代表队头元素
q[hh];

二. ⛳️题目练习

⌈ 在线OJ链接,可以转至此处自行练习 ⌋

2.1 题目

在这里插入图片描述

2.2 输入样例

10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6

2.3 输出样例

NO
6
YES
4

2.4 c++代码

#include <iostream>

using namespace std;

const int N = 100010;
int q[N];
int hh = 0;//队头
int tt = -1;//队尾

int main()
{
    int m = 0;
    cin >> m;
    
    while(m--)
    {
        int x = 0;
        string s;
        cin >> s;
        if(s == "push")
        {
            //向队尾插入一个数 x
            cin >> x;
            q[++tt] = x;
        }
        else if(s == "pop")
        {
            //从队头弹出一个数
            hh++;
        }
        else if(s == "empty")
        {
            //判断队列是否为空
            cout << (tt < hh ? "YES":"NO") << endl;
        }
        else
        {
            //查询队头元素
            cout << q[hh] << endl;
        }
    }
    
    return 0;
}