一、核心知识点与记忆要点

1. 栈的基础概念

• 定义：栈是一种后进先出（LIFO） 的线性数据结构，只允许在一端（栈顶）进行操作。
• 核心操作：
  • 入栈（push）：在栈顶添加元素。
  • 出栈（pop）：从栈顶移除元素。
  • 查看栈顶（peek）：获取栈顶元素但不移除。
• 记忆点：栈的操作遵循 “最后进去的最先出来”，类似叠盘子（最后放的盘子最先拿）。

2. 栈的实现方式对比

• 记忆点：单链表实现栈必须用头插法（尾插法出栈会是 O (n) 复杂度），双向链表因有头 / 尾指针，两端均可作为栈顶。

3. 栈的典型应用场景

1. 括号匹配：左括号入栈，右括号与栈顶匹配，最终栈空则合法。
2. 表达式求值：将中缀表达式转为后缀表达式（逆波兰式），用栈计算。
3. 逆序操作：如逆序打印链表（先入栈再出栈）。
4. 函数调用：程序运行时的函数调用栈（每个函数对应一个栈帧）。
5. 浏览器历史记录：前进 / 后退功能本质是两个栈的操作。

• 记忆点：栈擅长解决 “需要回溯或逆序处理” 的问题。

4. 关键算法案例代码

1. 括号匹配：

   • 核心：左括号入栈，右括号与栈顶匹配，不匹配则无效。
   • 特殊情况：栈为空时遇到右括号（无效）；遍历结束后栈非空（有未匹配的左括号）。

     import java.util.HashMap;
     import java.util.Map;
     
     public class BracketMatching {
         public static boolean isValid(String s) {
             // 创建栈存储左括号
             LinkedStack<Character> stack = new LinkedStack<>();
             
             // 右括号与左括号的映射关系
             Map<Character, Character> map = new HashMap<>();
             map.put(')', '(');
             map.put(']', '[');
             map.put('}', '{');
             
             // 遍历字符串
             for (int i = 0; i < s.length(); i++) {
                 char c = s.charAt(i);
                 
                 if (map.containsValue(c)) {
                     // 左括号入栈
                     stack.push(c);
                 } else if (map.containsKey(c)) {
                     // 右括号：判断栈顶是否匹配
                     if (stack.isEmpty() || stack.pop() != map.get(c)) {
                         return false;
                     }
                 }
                 // 忽略其他字符
             }
             
             // 最终栈必须为空（所有左括号都有匹配）
             return stack.isEmpty();
         }
         
         // 测试示例
         public static void main(String[] args) {
             System.out.println(isValid("()"));       // true
             System.out.println(isValid("()[]{}"));   // true
             System.out.println(isValid("(]"));       // false
             System.out.println(isValid("([)]"));     // false
             System.out.println(isValid("{[]}"));     // true
         }
     }
     

2. 逆波兰表达式求值：

   • 规则：数字入栈，遇到运算符则弹出两个数字计算，结果再入栈。
   • 注意：弹出顺序是 “后入栈的数字先参与运算”（如 “a b +” 表示 a+b）。

     import java.util.StringTokenizer;
     
     public class ReversePolishNotation {
         public static int evalRPN(String[] tokens) {
             // 创建栈存储数字
             LinkedStack<Integer> stack = new LinkedStack<>();
             
             for (String token : tokens) {
                 // 判断是否为运算符
                 if (token.equals("+") || token.equals("-") || 
                     token.equals("*") || token.equals("/")) {
                     // 弹出两个操作数（注意顺序：后弹出的是第一个操作数）
                     int b = stack.pop();
                     int a = stack.pop();
                     int result = 0;
                     
                     switch (token) {
                         case "+":
                             result = a + b;
                             break;
                         case "-":
                             result = a - b;
                             break;
                         case "*":
                             result = a * b;
                             break;
                         case "/":
                             result = a / b; // 假设输入合法，不会除零
                             break;
                     }
                     stack.push(result);
                 } else {
                     // 数字入栈
                     stack.push(Integer.parseInt(token));
                 }
             }
             
             // 最终栈顶元素即为结果
             return stack.pop();
         }
         
         // 测试示例
         public static void main(String[] args) {
             // 示例1：3 + 4 → 后缀表达式：["3","4","+"] → 结果7
             System.out.println(evalRPN(new String[]{"3","4","+"})); // 7
             
             // 示例2：(3+4)*5 → 后缀表达式：["3","4","+","5","*"] → 结果35
             System.out.println(evalRPN(new String[]{"3","4","+","5","*"})); // 35
             
             // 示例3：10 - (6 + 3) → 后缀表达式：["10","6","3","+","-"] → 结果1
             System.out.println(evalRPN(new String[]{"10","6","3","+","-"})); // 1
         }
     }
     

3. 出入栈次序判断：

   • 模拟过程：按入栈顺序入栈，每次入栈后检查是否与出栈序列匹配，匹配则出栈。
   • 结果：所有元素入栈后，栈为空则出栈序列合法。

public class StackOrderCheck {
    public static boolean isPopOrder(int[] pushOrder, int[] popOrder) {
        if (pushOrder == null || popOrder == null || 
            pushOrder.length != popOrder.length) {
            return false;
        }
        
        int n = pushOrder.length;
        LinkedStack<Integer> stack = new LinkedStack<>();
        int popIndex = 0; // 出栈序列的当前索引
        
        // 遍历入栈序列
        for (int value : pushOrder) {
            stack.push(value); // 入栈
            
            // 检查栈顶是否与当前出栈元素匹配，可能连续出栈
            while (!stack.isEmpty() && stack.peek() == popOrder[popIndex]) {
                stack.pop();       // 出栈
                popIndex++;        // 移动出栈索引
                if (popIndex == n) { // 所有元素都匹配完成
                    break;
                }
            }
        }
        
        // 若栈为空，说明所有元素都正确出栈
        return stack.isEmpty();
    }
    
    // 测试示例
    public static void main(String[] args) {
        int[] push = {1,2,3,4,5};
        int[] pop1 = {4,5,3,2,1}; // 合法
        int[] pop2 = {4,3,5,1,2}; // 非法
        
        System.out.println(isPopOrder(push, pop1)); // true
        System.out.println(isPopOrder(push, pop2)); // false
    }
}

• 记忆点：数据结构的栈是逻辑概念，虚拟栈和栈帧是 JVM 内存管理的物理概念。