盖子的c++小课堂——第十八讲栈
目录
前言
OK呀,说到做到,我们的粉丝们也是很给力呀,终于破了400粉~~
我太感动了aaaaaaaaaaaaaaaaaaaaaaaa
话不多说,我们直接开始!
栈的定义
栈,是什么?
例1-弹夹
你见过手枪吗?它长什么样?
啊对,就是这个~
那弹夹呢,总该见过吧,就是这样的,那你知道手枪发射子弹的方式吗
问题
手枪先打出的是先状填的子弹还是后装填的子弹呢?
手枪弹夹的出入口在哪里呢?
给大家配了副图,可以自己思考思考,我想肯定难不住你们~~嘿嘿
例2-停车场
问题
停车场只有一个出入口,你想先离开,需要先进去还是后进去呢?
栈的概念
栈是线性表,但只有一个出入口
允许插入或删除的栈称为栈顶,另一端称为栈底
空栈
空栈指不含任何数据元素的栈
进栈、出栈
特点
后进先出(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方向驶出,请来判断能否得到指定的车厢顺序。
如何操作
或者这样?
数组模拟栈
设定栈的最大容量为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粉丝就去认证!!!等我好消息哟~~
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanheaeaec
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
excel图片置于文字下方的方法
PHP中文网 06-27 -
excel下划线不显示怎么办
PHP中文网 06-23 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
微信运动停用后别人还能看到步数吗
PHP中文网 07-22