栈

​ 栈是限制插入和删除只能在一个位置上进行的线性表。

​ 栈是一种后进先出(LIFO)的数据结构，最先被删除的是最近压栈的元素

介绍

栈顶

​ 允许插入和删除的一端位于表的末端，叫做栈顶

栈底

​ 不允许插入和删除的另一端叫做栈底

基本操作

压栈(PUSH)

​ 对表进行插入数据

出栈/弹栈(POP)

​ 对表进行取出数据

栈实现

​ 由于栈是一个表，因此任何实现表的方法都可以用来实现栈。主要有两种方式，链表实现和数组实现。

链表实现栈

1. 可以使用单链表来实现栈
2. 通过在表顶端插入一个元素来实现PUSH，通过删除表顶端元素来实现POP
3. 使用链表方式实现的栈又叫动态栈
4. 动态栈有链表的部分特性，即元素与元素之间在物理存储上可以不连续，但是功能有些受限制
5. 动态栈只能在栈顶处进行插入和删除操作，不能在栈尾或栈中间进行插入和删除操作

数组实现栈

1. 栈可以用数组来实现
2. 使用数组方式实现的栈叫静态栈

栈的应用场景

子程序的调用

​ 在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。

处理递归调用

​ 和子程序的调用类似，只是除了存储写一个指令的地址外，也将参数，区域变量等数据存入堆栈中。

表达式的转换【中缀表达式转后缀表达式】与求值(实际解决)

二叉树的遍历

图形的深度优先(depth-first)搜索法