什么是栈?

• 栈是一种单端线性数据结构，它通过两个主要操作（即推送和弹出）模拟真实世界的栈。

• 栈是一个先入后出(FILO-First In Last Out)的有序列表。

• 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。

• 使用场景

  • 由文本编辑器中的撤消机制使用。
  • 用于编译器语法检查以匹配括号和花括号。[(){}]
  • 在后台使用以通过跟踪以前的函数调用来支持递归。
  • 图的深度优先搜索 (DFS)
  • 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中
  • 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
  • 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。
  • 二叉树的遍历。
  • 汉诺塔
  • 问题:表达式2x7x1+5计算机底层怎么计算,计算机收到的是一个字符串

• 复杂度分析
  pushing O(1)
  popping O(1)
  peeking O(1)
  searching O(n)因为可能要搜索整个链表
  size O(1)
  单调栈是一种特殊的栈，它的特点是栈内的元素保持某种单调性。根据单调性的不同，可以分为单调递增栈和单调递减栈。

• 单调递增栈

  • 定义: 单调递增栈中的元素从栈底到栈顶是严格递增的（即：栈顶元素小于或等于栈底元素）。
  • 维护规则:当新元素要入栈时，如果栈顶元素大于或等于新元素，则弹出栈顶元素，直到栈顶元素小于新元素或栈为空时，再将新元素入栈。
  • 作用:栈顶找到右边第一个比他小的元素
  • 应用场景: 典型的应用是在解决“柱状图中最大的矩形面积”问题时，利用单调递增栈来确定每个柱子的左、右边界。

• 单调递减栈

  • 定义: 单调递减栈中的元素从栈底到栈顶是严格递减的（即：栈顶元素大于或等于栈底元素）。
  • 维护规则:当新元素要入栈时，如果栈顶元素小于或等于新元素，则弹出栈顶元素，直到栈顶元素大于新元素或栈为空时，再将新元素入栈。
  • 作用:栈顶找到右边第一个比他大的元素
  • 应用场景: 单调递减栈常用于寻找“下一个更大元素”的问题，例如在股票价格、温度变化等场景中。

• 区别与选择
  单调递增栈:主要用于寻找数组中比当前元素小的值或寻找最小值问题。可以帮助在 O(n) 的时间复杂度内找到某个元素的左右边界。
  通常用于“最小值”问题，比如找到某个柱子左右最近的高度小于等于它的柱子。