个人主页:聆风吟
系列专栏:算法模板、数据结构
少年有梦不应止于心动,更要付诸行动。
文章目录
- 前言
- 一. ⛳️模拟栈
- 1.1 用数组模拟实现栈
- 1.1.1 栈的定义
- 1.1.2 向栈顶插入一个数 x(进栈操作)
- 1.1.3 从栈顶弹出一个元素(出栈操作)
- 1.1.4 判断栈是否为空
- 1.1.5 查询栈顶元素
- 1.2 模板提取(重点)
- 二. ⛳️题目练习
- 2.1 题目
- 2.2 输入样例
- 2.3 输出样例
- 2.4 c++代码
- 结语
前言
hello! 各位铁子们大家好哇,我们上期已经学习了双链表的算法模板,不知道大家都已经掌握了吗?如果你还有缺漏可以通过下面专栏自行跳转学习,今天作者又又又给大家带来了栈的算法模板详细讲解,让我们一起加油进步。
系列专栏:本期文章收录在《算法模板》,大家有兴趣可以浏览和关注,后面将会有更多精彩内容!
欢迎大家关注点赞收藏⭐️留言
一. ⛳️模拟栈
1.1 用数组模拟实现栈
1.1.1 栈的定义
栈(Stack):是只允许在一端进行插入或删除的线性表。首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作。如下图是栈的示意图:
1.1.2 向栈顶插入一个数 x(进栈操作)
根据栈的定义可知,我们可以将数组看作是横放的栈的示意图,即将数组的首元素位置看作栈底、当前元素的位置看作栈顶,便可以实现数组模拟栈的相关操作。如果我们要向栈顶插入一个元素,将栈顶指针向后移动一位将元素插入进去即可。如下图所示:
代码展示(建议结合图示看注释):
//top表示栈顶int stk[N], top = -1;// 向栈顶插入一个数xstk[++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;// 向栈顶插入一个数xstk[++top] = x;// 从栈顶弹出一个数top-- ;// 栈顶的值stk[top];// 判断栈是否为空,如果 top >= 0,则表示不为空if (top >= 0){//输出栈不为空}else{//输出栈为空}
二. ⛳️题目练习
⌈ 在线OJ链接,可以转至此处自行练习 ⌋
2.1 题目
2.2 输入样例
10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty
2.3 输出样例
5
5
YES
4
NO
2.4 c++代码
#include using 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、从栈顶弹出一个元素、判断栈是否为空、查询栈顶元素,通过栈相关操作的讲解最终我们提取出了栈的算法模板,并通过一个题目的练习结束了今天的课程。希望大家课下能够多敲多练,孰能生巧。
今天的干货分享到这里就结束啦!如果觉得文章还可以的话,希望能给个三连支持一下,聆风吟的主页还有很多有趣的文章,欢迎小伙伴们前去点评,您的支持就是作者前进的最大动力!