南京网站建设招标,那家财经网站做的好,深圳公司注册地址要求,网站用什么做备份#x1f308;个人主页#xff1a;聆风吟 #x1f525;系列专栏#xff1a;算法模板、数据结构 #x1f516;少年有梦不应止于心动#xff0c;更要付诸行动。 文章目录 #x1f4cb;前言一. ⛳️模拟队列1.1 #x1f514;用数组模拟实现队列1.1.1 #x1f47b;队列的定… 个人主页聆风吟 系列专栏算法模板、数据结构 少年有梦不应止于心动更要付诸行动。 文章目录 前言一. ⛳️模拟队列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 iostreamusing 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){//向队尾插入一个数 xcin 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;
}结语 本文主要讲解队列的定义、使用数组模拟实现队列的相关操作入队列、出队列、判断队列是否为空、查询队头元素通过队列相关操作的讲解最终我们提取出了队列的算法模板并通过一个题目的练习结束了今天的课程。希望大家课下能够多敲多练孰能生巧。 今天的干货分享到这里就结束啦如果觉得文章还可以的话希望能给个三连支持一下聆风吟的主页还有很多有趣的文章欢迎小伙伴们前去点评您的支持就是作者前进的最大动力
