登录以参加训练计划

一、栈的基本概念

1. 形象比喻

• ​叠盘子：后放的盘子先取用（Last In First Out, LIFO）。
• ​电梯按键：最后按的楼层最先到达。

2. 基本操作

• ​入栈（push）​：将元素放入栈顶。
• ​出栈（pop）​：移除并取出栈顶元素。
• ​查看栈顶（top）​：查看但不移除栈顶元素。
• ​判空（empty）​：判断栈是否为空。
• ​栈中元素个数（size）​：获得栈中元素个数。

---

二、栈的常见应用（信息学奥赛）

1. 括号匹配问题

• ​题目示例：检查字符串 (()()) 的括号是否合法。
• ​解决步骤：
  1. 遇到左括号（(）则入栈。
  2. 遇到右括号（)）则检查栈顶是否有对应的左括号。
  3. 若栈为空或不匹配，则为错误；否则弹出栈顶。
  4. 最后栈必须为空才算合法。
• ​代码逻辑：

  stack<char> s;
  for (char c : str) {
      if (c == '(') s.push(c);
      else if (c == ')') {
          if (s.empty()) return false;
          s.pop();
      }
  }
  return s.empty();
  
  

2. 表达式求值

• 题目示例：逆波兰表达式（后缀表达式）将中缀表达式3 + 5 * 2。转为后缀表达式3 5 2 * +

• ​解决步骤：

  1. 遇到数字直接输出。
  2. 遇到左括号入栈，遇到操作符比较优先级。
  3. 遇到右括号，循环弹出栈顶元素直到找到左括号为止。
  4. 依次弹出栈顶元素，直到栈为空。

• ​代码逻辑：

  int priority(char c) {
    if (c == '+' || c == '-') return 1; 
    if (c == '*' || c == '/') return 2; 
    return 0; // 括号的优先级特殊处理
  }
  int main() {
    string s = "3+4*(5-2)"; // 输入的中缀表达式
    stack<char> op;         // 符号栈
    string postfix;         // 后缀表达式
    
    for (char c : s) {
        if (isdigit(c)) {              
            postfix += c;//如果是数字直接输出
        }  else if (c == '(') { //左括号进栈
            op.push(c);
        } else if (c == ')') { // 循环弹出栈顶直到找到左括号
            while (!op.empty() && op.top() != '(') {
                postfix += op.top();
                op.pop();
            }
            op.pop(); // 弹出左括号但不输出
        } else {                         
            // 比较优先级，弹出优先级>=自己的
            while (!op.empty() && priority(op.top()) >= priority(c)) {
                postfix += op.top();
                op.pop();
            }
            op.push(c);
        }
    }
    
    // 最后弹出所有运算符
    while (!op.empty()) {
        postfix += op.top();
        op.pop();
    }
    
    cout <<postfix << endl;
    return 0;
  

}

3. 单调栈（下一个更大元素）

• ​题目示例：数组 [3, 1, 4, 2]，求每个元素右侧第一个比它大的数。例如：有一群小朋友按身高排成一列，每个小朋友都想知道：​右边第一个比自己高的人是谁？若[3, 1, 4, 2]（数字代表身高），结果应该是：[4, 4, -1, -1]。
• ​解决步骤：
  1. 维护一个单调递减栈。准备一个栈：记录“还在找更高的人”的小朋友编号（注意栈里面存的是待处理元素的素引）。
  2. 循环判断当前元素与栈顶元素的大小，如果比栈顶大，则说明栈顶元素找到了它的目标元素，并记录下来，栈顶元素出栈。
  3. 把当前元素入栈。
  4. 输出res结果数组。
• ​代码逻辑：

  stack<int> s;//这里面放待处理元素的索引
  vector<int> ans(nums.size(), -1);//结果
  for (int i = 0; i < nums.size(); ++i) {
  while (!s.empty() && nums[i] > nums[s.top()]) {
        ans[s.top()] = nums[i];
        s.pop();
    }
    s.push(i);
  }
  
  
  

三、栈与其他结构的对比

1.栈 vs. 队列

• ​栈（LIFO）： ​：深度优先搜索（DFS）、回溯问题。
• ​队列（FIFO）​：：广度优先搜索（BFS）、按顺序处理任务。 ​比喻： 栈像叠盘子，最后放的先处理。 队列像排队，先来的先服务。

2. 递归与栈的关系

​- ​递归调用栈：：每次函数调用时，参数和返回地址压入系统栈。 ​示例：斐波那契数列 fib(n) = fib(n-1) + fib(n-2)。 系统自动用栈保存每层调用的状态。