前言
唤我沈七就好啦。
这是模拟数据结构系列。
以下是之前同系列文章。
本次讲解的是栈。
什么是栈？
相关概念
栈顶：允许元素插入与删除的一端称为栈顶。
入栈：栈的插入操作。
出栈：栈的删除操作。
特点：先进后出。
即先入栈的元素需要等后入栈的元素出栈后才能出栈。
这是因为栈只有一个出口，可以通过下图来辅助理解。
栈也是线性表的一种，所以也可以理解为只能在一端操作的数组。
实现思路
前面提到，栈可以理解为只能在一端操作的数组。而这正是我们实现思路。
实现方法
1 .创建变量
const int N=1e6+10; int stk[N],top=-1; 初始化
定义一个数组，一个放在栈顶的变量
将栈顶变量初始化为 -1 是为了方便最后判断栈是否为空。
2 . 插入操作
if(a=="push") { cin>>x; stk[++top]=x; 只能在栈顶插入 }
当输入 push 5 时 ，5这个元素就入栈了。
注意这里一定要是 ++top 让下标是0， 因为 top 初始化的是 -1。
如果 top++ 下标就是 - 1 了。
3 .删除操作
else if(a=="pop") top--; 只能在栈顶弹出
当输入 pop 5 时 ，5这个元素就出栈了。
注意这里确实并没有真正删除放在栈顶的元素，但栈顶下降了一位，就可以理解为删除了上一位。
因为等下一次 stk[++top]=x;之前没被删除的元素就会被新插入的元素覆盖。
这里也不需要考虑空间浪费问题。
4 .判断栈空
if(a=="empty") { if(top==-1) // 如果栈顶还为 -1 栈就为空 puts("YES"); else puts("NO"); } } return 0; }
当输入 empty 时 ，返回 YES 栈就为空 ， 返回 NO 栈就非空。
完整模板
# include<bits/stdc++.h> using namespace std; const int N=1e6+10; int stk[N],top=-1;//初始化 int main() { int n; cin>>n; while(n--) { int x; string a; cin>>a; if(a=="push") { cin>>x; stk[++top]=x;//只能在栈顶插入 } else if(a=="pop") top--;//只能在栈顶弹出 else if(a=="empty") { if(top==-1) puts("YES"); else puts("NO"); } else cout<<stk[top]<<endl;//取出栈顶 } return 0; }
完结散花
ok以上就是对模拟数据结构之栈的全部讲解啦，很感谢你能看到这儿啦。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我，我后期再补充完善。
