盖子的c++小课堂——第十八讲：栈

这篇具有很好参考价值的文章主要介绍了盖子的c++小课堂——第十八讲：栈。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

栈的定义

栈，是什么？

例1-弹夹

问题

例2-停车场

问题

栈的概念

空栈

进栈、出栈

特点

例题

车厢调度

如何操作

数组模拟栈

入栈

出栈

栈的基本操作

判断空栈

求栈的元素数量

读栈顶元素

总结

前言

OK呀，说到做到，我们的粉丝们也是很给力呀，终于破了400粉~~

盖子的c++小课堂——第十八讲：栈,盖子的c++小课堂（1）,c++

我太感动了aaaaaaaaaaaaaaaaaaaaaaaa

话不多说，我们直接开始！

栈的定义

栈，是什么？

例1-弹夹

你见过手枪吗？它长什么样？

啊对，就是这个~

那弹夹呢，总该见过吧，就是这样的，那你知道手枪发射子弹的方式吗

问题

手枪先打出的是先状填的子弹还是后装填的子弹呢？

手枪弹夹的出入口在哪里呢？

给大家配了副图，可以自己思考思考，我想肯定难不住你们~~嘿嘿

盖子的c++小课堂——第十八讲：栈,盖子的c++小课堂（1）,c++

例2-停车场

问题

停车场只有一个出入口，你想先离开，需要先进去还是后进去呢？

盖子的c++小课堂——第十八讲：栈,盖子的c++小课堂（1）,c++

栈的概念

栈是线性表，但只有一个出入口

盖子的c++小课堂——第十八讲：栈,盖子的c++小课堂（1）,c++

允许插入或删除的栈称为栈顶，另一端称为栈底

空栈

空栈指不含任何数据元素的栈

进栈、出栈

盖子的c++小课堂——第十八讲：栈,盖子的c++小课堂（1）,c++

特点

后进先出（Last in first out），简称LIFO

先进后出（First in last out），简称FILO

插入操作：进展 push

删除操作：出栈 pop

例题

车厢调度

有一个火车站，每辆火车从A驶入，再从B方向驶出，同时它的车厢可以重新组合。假设从A方向驶来的火车有n节（n<=1000），分别按照顺序编号为1，2，3，…，n。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任意多节车厢。但是一旦进入车站C，它就不能再回到A方向的铁轨上了，并且一旦当它进入B方向的铁轨，它就不能再回到车站C。负责车厢调度的工作人员需要知道能否使它以a1,a2,…,an的顺序从B方向驶出，请来判断能否得到指定的车厢顺序。

盖子的c++小课堂——第十八讲：栈,盖子的c++小课堂（1）,c++

如何操作

盖子的c++小课堂——第十八讲：栈,盖子的c++小课堂（1）,c++ 或者这样？

数组模拟栈

设定栈的最大容量为N

const int N=10009;

定义栈，用整数数组储存

int stk[N];

定义栈顶编号，初始化为零

int top=0;

入栈

入栈前判断栈是否已满
栈定编号向上移动一位
存入新入栈元素

void push(int x){
	if(top==N-1)
	    cout<<"overflow"<<endl;
	else
	    stk[++top]=x;
}

时间复杂度O（1）

出栈

出栈前判断栈是否为空
栈定编号向下移动一位
删除栈顶元素

void pop(){
	if(top==0)
	    cout<<"underflow"<<endl;
	else
	    top--;
}

时间复杂度O（1）

栈的基本操作

判断空栈

bool empty(){
	return top==0;
}

求栈的元素数量

int size(){
	return top;
}

读栈顶元素

int getTop(){
	return stk[top];
}

总结

今天的小课堂就到这里了，记得点赞关注加收藏哦~~

破500粉丝就去认证！！！等我好消息哟~~文章来源地址https://www.toymoban.com/news/detail-537745.html

到了这里，关于盖子的c++小课堂——第十八讲：栈的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

Toy模板网

盖子的c++小课堂——第十八讲：栈

栈的定义

栈，是什么？

例1-弹夹

问题

例2-停车场

问题

栈的概念

空栈

进栈、出栈

特点

例题

车厢调度

如何操作

数组模拟栈

入栈

出栈

栈的基本操作

判断空栈

求栈的元素数量

读栈顶元素

总结

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2