栈和队列

1、栈的定义

栈(stack)是限定仅在表尾进行插入和删除操作的线性表。

栈顶top：在允许插入和删除的一端 栈底bottom: 栈顶的另一端 空栈：不含任何数据元素的栈 栈是LIFO结构，称为后进先出（Last In First Out）

2、进栈出栈

进栈：栈的插入操作，也称压栈，入栈
出栈：栈的删除操作，也称弹栈

3、栈的存储

• 顺序存储

顺序栈：栈的顺序存储其实也是线性表存储的简化

实现：使用数组的方式

• 链式存储

链栈：栈的链式存储结构

4、栈空间共享

实现方式：使用一个数组，两个栈有两个栈底，让一个栈的栈底为数组的开始，即下标为0处，另一个栈的的栈底为数组的末端，即n-1处。这样两个栈增加元素，就是向数组的中间延伸。

5、栈的作用

栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更聚焦于我们要解决的问题核心。

• 递归

递归函数：把一个直接调用自己或通过一系列的调用语句间接的调用自己的函数
⚠️：每一个递归定义必须至少有一个条件，满足时递归不在进行，即不再引用自身而是返回值退出。

• 四则运算（数学表达式的求值）
  • 后缀（逆波兰）表达式
    • 示例：9 3 1 - 3 * +10 2 / +
  • 中缀表达式
    • 示例：9 + （3 -1）x 3 + 10 ➗ 2

6、队列

• 定义

是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是先进先出（First In First Out）的线性表，简称FIFO。 允许插入的一端称为队尾，允许删除的一端称为队头

• 抽象数据类型

• 顺序存储

同线性表的顺序存储

• 链式存储

同线性表的链式存储

7、循环队列

• 定义

把队列的这种头尾相接的顺序存储结构

8、栈和队列对比