栈

栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。

栈 (Stack) 是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。先进后出。top= -1 时为空栈，top=0 只能说明栈中只有一个元素，并且元素进栈时 top 应该自增

1. 顺序存储栈：顺序存储结构
2. 链栈：链式存储结构。插入和删除操作仅限制在链头位置上进行。栈顶指针就是链表的头指针。通常不会出现栈满的情况。 不需要判断栈满但需要判断栈空。
3. 两个栈共用静态存储空间, 对头使用也存在空间溢出问题。栈 1 的底在 v[1]，栈 2 的底在 V[m]，则栈满的条件是 top[1]+1=top[2]。
4. 基本操作：删除栈顶元素、判断栈是否为空以及将栈置为空栈等
5. 对于 n 各元素的入栈问题，可能的出栈顺序有 C(2n,n)/(n+1) 个。
6. 堆栈溢出一般是循环的递归调用、大数据结构的局部变量导致的

应用，代码：

1. 进制转换
2. 括号匹配的检验
3. 行编辑程序
4. 迷宫求解：若当前位置 “可通”，则纳入路径，继续前进; 若当前位置 “不可通”，则后退，换方向继续探索; 若四周 “均无通路”，则将当前位置从路径中删除出去。

5. 表达式求解：前缀、中缀、后缀。

   • 操作数之间的相对次序不变;
   • 运算符的相对次序不同;
   • 中缀式丢失了括弧信息，致使运算的次序不确定
   • 前缀式的运算规则为: 连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式
   • 后缀式的运算规则为: 运算符在式中出现的顺序恰为表达式的运算顺序; 每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。
6. 实现递归：多个函数嵌套调用的规则是：后调用先返回。
7. 浏览器历史纪录，Android 中的最近任务，Activity 的启动模式，CPU 中栈的实现，Word 自动保存，解析计算式，解析 xml/json。解析 XML 时，需要校验节点是否闭合，节点闭合的话，有头尾符号相对应，遇到头符号将其放入栈中，遇到尾符号时，弹出栈的内容，看是否有与之对应的头符号，栈的特性刚好符合符号匹配的就近原则。

不是所有的递归程序都需要栈来保护现场，比方说求阶乘的，是单向递归，直接用循环去替代从 1 乘到 n 就是结果了，另外一些需要栈保存的也可以用队列等来替代。不是所有的递归转化为非递归都要用到栈。转化为非递归主要有两种方法：对于尾递归或单向递归，可以用循环结构算法代替

---

Table of contents