数据结构——栈
定义
栈:仅在表尾进行插入和删除操作的线性表
与之对应的:当一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
特性:前进后出
可以想象一下沙漠之鹰的手枪,进栈为子弹弹入弹夹,出栈为子弹弹出弹夹
栈的应用
像浏览器的后退功能也是用栈来实现的,
单击后可以按访问顺序的逆序加载浏览过的网页
还有许多的文本编辑软件的ctrl+z”的撤销功能,也是通过栈来实现的
栈中的专业名词
栈顶:允许插入和删除的一端
栈底:栈顶的另一端
空栈:不含任何元素的
还可以说是栈是限定仅在表尾(栈顶)进行插入和删除操作的线性表
插入就叫进栈
删除称为出栈
例题
某城市有一个火车站,铁轨铺设如图。有n节车厢从A方向驶入车站,按进站的顺序编号为1~n。你的任务是判断是否能让他们按照某种特定的顺序进入B方向的铁轨并驶出车站。例如,出栈顺序(5 4 1 2 3)是不可能的,但(5 4 3 2 1)是可能的。 为了重组车厢,你可以借助中转站C。这是一个可以停放任意多节车厢的车站,但由于末端封顶,驶入C的车厢必须按照相反的顺序驶出C。对于每节车厢,一旦从A移入C,就不能返回A了;一旦从C移入B,就不能返回C了。也就是说,在任意时刻,只有两种选择:A到C和C到B。
//首先中转站C中,车厢符合先进后出的原则,是一个栈
#include<cstdio>
#include<stack>
using namespace std;
const int maxn = 1000 + 10;
int n, target[maxn];
int main()
{
while (scanf_s("%d", &n) == 1)
{
stack<int> s;
int a = 1, b = 1;
for (int i = 1; i <= n; i++)
{
scanf_s("%d", &target[i]);
}
int ok = 1;
while (b <= n)
{
if (a == target[b])
{
a++;
b++;
}
else if (!s.empty() && s.top() == target[b])
//运用empty和top函数,包含头文件《stack》
{
s.pop();
b++;
}
else if (a <= n)
s.push(a++);
else
{
ok = 0;
break;
}
}
printf("%s\n", ok ? "yes" : "no");
}
return 0;
}
习题巩固
题目:设计一个有getMin功能的栈
实现一个特殊的栈,在实现栈的基本功能上,再实现返回栈中最小元素的操作
要求:
1.pop,push,getMin操作的时间复杂度为O(1)
设计时候可以使用现成的栈结构
- 点赞
- 收藏
- 关注作者
评论(0)