栈(Stack)

栈的基本概念

栈可以看作是操作受限的线性表，限制在表的一端进行插入和删除操作的线性表。成为先进先出(LIFO)，先进后出(FILO)线性表。

栈顶(Top):允许插入删除操作的一段，称为表尾。

栈底(Bottom):固定端，称为表头。

进栈(push):又称为压栈。

出栈(pop):又称为弹栈。

栈的修改是按先进后出原则进行的

顺序栈

由数组是否可以扩充可分为静态顺序栈，动态顺序栈。

静态顺序栈:实现简单，但不能做扩充

动态顺序栈:实现较复杂，可以扩充

结点进栈:将数据元素存到top指针所指的位置，top移向栈的下一存储位置，即top+1

结点出栈: 先将top指向上一存储位置，即top-1，再将top指向的当前结点的数据元素取出，

初始化栈:top = bottom = -1 / 0 / n / n - 1

0 / n - 1 的设置方式 top 始终指向下一个值为空的结点，且要先赋值再top++ / --，而 -1 / n 的设置方式要先top++ / --再赋值

动态栈:

静态栈:

对顶栈:

• 两个栈共享一片空间

• 把两个栈的栈底设置在数组的两端

• |top1 - top2| == 1 表示栈满

链栈

栈的链式存储结构，是运算受限的单链表，其插入和删除操作只能在表头位置上进行，头出头插的单链表结构

栈的应用

1.检查一个字符串或者一个表达式中的括号是否相匹配，例如:[4 + (2 + 8) * [ 5 / (9 - 7)] * 3

算法思想:

• 设置一个栈

• 当读到左括号时，左括号进栈。

• 当读到右括号时，则从栈中弹出一个元素，与读到的右括号进行匹配，若匹配成功，继续读入；

• 否则匹配失败，返回false。

上代码👇

2.中缀表达式:b - (a + 5) * 3 转后缀表达式: b a5+ 3 * -

①初始化一个数字栈（s1）和符号栈（s2），从左到右扫描表达式，若遇到数字直接铺设到数字栈

②遇到符号，设符号为 ch

Ⅰ.若符号栈为空，则s2.push(ch)

Ⅱ.若ch为左括号，则s2.push(ch)

Ⅲ.若s2的栈顶为左括号 则s2.push(ch)

Ⅳ.若ch优先级大于s2栈顶元素的优先级，则s2.push(ch)，否则将从s2中弹出栈顶元素，压到s1中（若要计算结果的，则从s1中弹出两个数完成运算，然后将运算结果压回s1中，回到Ⅱ 继续执行）