目录

前言

栈的定义

栈是什么

例1-弹夹

问题

例2-停车场

问题

栈的概念

空栈

进栈、出栈

特点

例题

车厢调度

 如何操作

数组模拟栈

入栈

出栈

栈的基本操作

判断空栈

 求栈的元素数量

读栈顶元素

总结

---

前言

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

我太感动了aaaaaaaaaaaaaaaaaaaaaaaa 

话不多说我们直接开始

栈的定义

栈是什么

例1-弹夹

你见过手枪吗它长什么样

啊对就是这个~

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

问题

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

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

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

例2-停车场

问题

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

栈的概念

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

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

空栈

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

进栈、出栈

特点

后进先出Last in first out简称LIFO

先进后出First in last out简称FILO

插入操作进展 push

删除操作出栈 pop

例题

车厢调度

有一个火车站每辆火车从A驶入再从B方向驶出同时它的车厢可以重新组合。假设从A方向驶来的火车有n节n<=1000分别按照顺序编号为123…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;
}

 时间复杂度O1

出栈

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

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

  时间复杂度O1

栈的基本操作

判断空栈

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

 求栈的元素数量

int size(){
	return top;
}

读栈顶元素

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

总结

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

破500粉丝就去认证等我好消息哟~~