数据结构之线性表-栈-学习笔记-29

引入

今天,我们开始讲一种特殊的线性表,栈。既然是特殊的线性表,那么有哪些不一样的呢?我们一起来看看!

从弹夹说起

下面的图片是一个弹夹

我们知道,如果子弹没有了,那么我们需要一颗一个的将子弹装入弹夹

  • 第一颗被装入的子弹在弹夹的最上方
  • 第二颗则压在第一颗的上方,循环往复,直到装满
  • 此时如果我们要射击,最上面的一颗子弹会首先被发射出去
  • 然后弹夹下面的弹簧会将压在下面的子弹顶上来

也就是说,最后被装入的子弹,最先被发射出去。我们将这种情况称之为后进先出

栈的定义

栈,是一个后进先出(Last in First out) 的线性表,我们也称后进先出为LIFO,它要求只在表尾进行删除和插入操作。
栈是一种重要的线性结构,可以说,栈是前面讲过的线性表的一种具体形式,也是一种特殊的线性表:

  • 栈的元素必须后进先出
  • 栈的操作只能在这个线性表的表尾进行操作
  • 我们称表尾为栈的栈顶(Top)操作的为顶
  • 我们称表头为栈的栈底(Bottom)不能操作的为底

栈的插入和删除

我们把栈的操作称之为(Push),类似压子弹,叫做进栈、压栈、入栈。
我们把栈的删除称之为(Pop),类似子弹发射,叫做出站、弹栈。

栈的顺序存储结构

因为栈说到底其实是一个线性表,线性表有两种存储形式,即顺序和链式。栈也分为顺序存储和链式存储两种。而我们一般情况下使用的是栈的顺序存储结构。

  • 开始时,栈内没有任何数据,称之为空栈。
  • 空栈时,栈底就是栈顶。
  • 进栈时,从栈顶(表尾)进入,栈顶栈底分离,栈的容量变大。
  • 出栈时,从栈顶(表尾)弹出,栈顶下移,栈的容量变小。

定义栈的结构体

定义一个顺序存储结构的栈的结构体,结构体包含三个元素

  • base,是指向栈底的指针。
  • top,是指向栈顶的指针。
  • StackSize,存储着当前可使用的最大容量。
1
2
3
4
5
struct Stack{
int *base; //指向栈底
int *top; //指向栈顶
int stackSize; //记录当前剩余容量
};

创建一个栈

我们来创建一个空栈

1
2
3
4
5
6
7
8
9
10
11
#define STACK_INIT_SIZE 100
#define LEN sizeof(int)
initStack(sqStack *s){
s->base=(int *)malloc(STACK_INIT_SIZE*LEN);
//创建动态存储空间,100个 int 型
if(!s->base){
exit(0);
}
s->top=s->base; //最开始的时候,栈顶就是栈底
s->stackSize = STACK_INIT_SIZE; //一开始的可用容量
}

其实重要的就几点

  • 申请的空间是最大容量倍的类型长度
  • 栈顶一开始就是栈底
  • 记得把可用容量标记好

尾巴

这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。


-------------The End-------------
欢迎请我喝咖啡哦~!