浅谈 stack——栈

栈

了解栈

• 栈为数据结构的一种，是 STL 中实现的一个先进后出的容器。

• 随后我们可以了解一下应该怎么定义和头文件：

  定义方法：stack<数据类型> 变量名;

  头文件：#include <stack>

  比如说我们可以看一下下面的例子：

  #include <stack>//栈的头文件
  
  //声明栈
  
  stack<int> st;
  stack<double> st1;
  
  stack<Node> stc;//Node 为数据类型

栈遍历

• 栈只能对栈顶元素进行操作，如果想要进行遍历，只能将栈中元素一个个取出来存在数组中

stack<int> st; //栈 

for (int i = 0;i < 10;i++) {
    st.push(i); //入栈 
} 

while (!st.empty()) {  //判断栈是否不为空 
    int tp = st.top(); //栈顶元素
    cout<<tp<<endl; //打印栈顶 
    st.pop(); //出栈 
} 

实例

接下来我们可以来看一下实例：

1. 表达式求值：

   表达式有三种：前缀表达式、中缀表达式和后缀表达式（逆波兰表达式）。

   这种题目我们可以用栈来做。

   我们可以来看一道题目的例子：P10473 表达式计算4

   此题思路：

   1. 表达式可以用字符串来输入。

   2. 可以自定义函数来计算。

   3. 扫描数字就存入栈中，扫描符号就计算弹出，优先级的要注意（左括号最低，右括号最高）。

   4. 要弄字符栈和数字栈。

2. 括号匹配：

   判断字符串中括号是否成对匹配 (如 {[()()]})。

   题目：P1739 表达式括号匹配

   按照题目要求判断即可，比如弄个函数 check。

3. 深度优先搜索（DFS）：

   在图或树的深度遍历中，栈用于存储节点。

   P1135 奇怪的电梯 就是一个非常好的例子。

   这题有点像二联通。

   同时这题也可以 队列加广度优先搜索（BFS） 完成（下期会讲）。

单调栈

单调栈 的基本概念：

• 单调递增栈：栈中的元素从底到顶是单调递增的。就是说，在任何时候，栈顶的元素都是当前遍历元素的最小的值。

• 单调递减栈：栈中的元素从底到顶是单调递减的。就是说，在任何时候，栈顶的元素都是当前遍历元素的最大的值。

我们可以写一个单调栈的伪代码：

stack<int> st;
//此处一般需要给数组最后添加结束标志符，具体下面例题会有详细讲解
for(遍历这个数组){
    if (栈空 || 栈顶元素大于等于当前比较元素){
        入栈;
    }
    else{
        while (栈不为空 && 栈顶元素小于当前元素){
            栈顶元素出栈;
            更新结果;
        }
        当前数据入栈;
    }
}