投资网站排行,军事最新新闻播报,网页设计资料下载网站,各大网站发布信息#x1f308;个人主页#xff1a;聆风吟 #x1f525;系列专栏#xff1a;数据结构、算法模板、汇编语言 #x1f516;少年有梦不应止于心动#xff0c;更要付诸行动。 文章目录 #x1f4cb;前言一. ⛳️模拟栈1.1 #x1f514;用数组模拟实现栈1.1.1 #x1f47b;栈… 个人主页聆风吟 系列专栏数据结构、算法模板、汇编语言 少年有梦不应止于心动更要付诸行动。 文章目录 前言一. ⛳️模拟栈1.1 用数组模拟实现栈1.1.1 栈的定义1.1.2 向栈顶插入一个数 x进栈操作1.1.3 从栈顶弹出一个元素出栈操作1.1.4 判断栈是否为空1.1.5 查询栈顶元素 1.2 模板提取(重点) 二. ⛳️题目练习全文总结 前言 hello! 各位铁子们大家好哇我们上期已经学习了双链表的算法模板不知道大家都已经掌握了吗如果你还有缺漏可以通过下面专栏自行跳转学习今天作者又又又给大家带来了栈的算法模板详细讲解让我们一起加油进步。 系列专栏本期文章收录在《算法模板》大家有兴趣可以浏览和关注后面将会有更多精彩内容 欢迎大家关注点赞收藏⭐️留言 一. ⛳️模拟栈
1.1 用数组模拟实现栈
1.1.1 栈的定义 栈Stack是只允许在一端进行插入或删除的线性表。首先栈是一种线性表但限定这种线性表只能在某一端进行插入和删除操作。如下图是栈的示意图
1.1.2 向栈顶插入一个数 x进栈操作 根据栈的定义可知我们可以将数组看作是横放的栈的示意图即将数组的首元素位置看作栈底、当前元素的位置看作栈顶便可以实现数组模拟栈的相关操作。如果我们要向栈顶插入一个元素将栈顶指针向后移动一位将元素插入进去即可。如下图所示 代码展示建议结合图示看注释
//top表示栈顶
int stk[N], top -1;// 向栈顶插入一个数x
stk[top] x;1.1.3 从栈顶弹出一个元素出栈操作 根据上面所知如果我们要从栈顶弹出一个元素我们只需要将栈顶指针向前移动一位即可。如下图所示 代码展示建议结合图示看注释
// 从栈顶弹出一个数
top--;1.1.4 判断栈是否为空 根据上面所知如果我们要判断栈是否为空我们只需要判断栈顶指针是否指向数组首元素左边的位置即判断top是否等于-1位置。如下图所示 代码展示建议结合图示看注释
// 判断栈是否为空如果 top 0则表示不为空
if (top 0)
{//输出栈不为空
}
else
{//输出栈为空
}1.1.5 查询栈顶元素 根据下图所示查询栈顶元素只需要输出数组下标为top的值即可 代码展示建议结合图示看注释
// 栈顶的值
stk[top];1.2 模板提取(重点)
C代码
// top表示栈顶
int stk[N], top -1;// 向栈顶插入一个数x
stk[top] x;// 从栈顶弹出一个数
top-- ;// 栈顶的值
stk[top];// 判断栈是否为空如果 top 0则表示不为空
if (top 0)
{//输出栈不为空
}
else
{//输出栈为空
}二. ⛳️题目练习 ⌈ 在线OJ链接,可以转至此处自行练习 ⌋ 说明题目取自AcWing官网由于题目需要付费OJ链接只有购买课程的人才可以使用深感抱歉。后面尽量给大家多整理一些测试用例方便大家自行测试。 题目
输入样例 10 push 5 query push 6 pop query pop empty push 4 query empty 输出样例 5 5 YES 4 NO c代码
#include iostreamusing namespace std;const int N 100010;
int stk[N], top -1;int main()
{int m 0;cin m;while(m--){string s;cin s;if(s push){//在栈顶插入一个元素int x 0;cin x;stk[top] x;}else if(s pop){//从栈顶弹出一个元素top--;}else if(s empty){//判断栈是否为空cout (top 0 ? NO:YES ) endl;}else{//查询栈顶元素cout stk[top] endl;}}return 0;
}全文总结
归纳 本文主要讲解栈的定义、使用数组模拟实现栈的相关操作向栈顶插入一个数x、从栈顶弹出一个元素、判断栈是否为空、查询栈顶元素通过栈相关操作的讲解最终我们提取出了栈的算法模板并通过一个题目的练习结束了今天的课程。希望大家课下能够多敲多练孰能生巧。 今天的内容就到这里了你对今天的内容是否有所掌握如果还有疑问的话请在评论区里多多提问大家可以一起帮你解决让我们共同进步。创作不易如果对你有用的的话点个赞支持下作者你们的支持是作者创作最大的动力。关注我不迷路让我们下期再见✋✋。
