算法模版：模拟数据结构之链表
前言
唤我沈七就好啦。
这是模拟数据结构系列。
以下是之前同系列文章。
本次讲解的是栈。
什么是栈？
相关概念
栈顶：允许元素插入与删除的一端称为栈顶。
入栈：栈的插入操作。
出栈：栈的删除操作。
特点：先进后出。
即先入栈的元素需要等后入栈的元素出栈后才能出栈。
这是因为栈只有一个出口，可以通过下图来辅助理解。
栈也是线性表的一种，所以也可以理解为只能在一端操作的数组。
实现思路
前面提到，栈可以理解为只能在一端操作的数组。而这正是我们实现思路。
实现方法
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以上就是对模拟数据结构之栈的全部讲解啦，很感谢你能看到这儿啦。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我，我后期再补充完善。