栈：线性结构中的 “后进先出” 王者，从底层逻辑到实战应用全解析

果酱带你啃java

发布于 2026-04-14 13:44:54

260

栈：线性结构中的“后进先出”王者，从底层逻辑到实战应用全解析

在数据结构的世界里，栈（Stack）是最基础也最“低调”的线性结构之一，但它却贯穿于计算机科学的方方面面——从JVM的方法调用栈到浏览器的前进后退功能，从表达式求值到括号匹配校验，栈的“后进先出”（LIFO）特性如同一条隐形的线索，支撑着无数核心场景的运转。本文将从栈的底层逻辑出发，拆解其实现原理、核心操作与实战应用，让你不仅“知其然”，更“知其所以然”。

一、栈的基础认知：什么是“后进先出”？

1.1 栈的定义（权威来源：《数据结构与算法分析：Java语言描述》Mark Allen Weiss）

栈是一种限定仅在表尾进行插入和删除操作的线性表，表尾被称为“栈顶（Top）”，表头被称为“栈底（Bottom）”。由于插入和删除只能在栈顶进行，最早进入栈的元素会最后被取出，形成“后进先出”（Last In First Out，LIFO）的特性。

打个通俗的比方：栈就像你往笔筒里放笔——最后放进去的笔总是最先被拿出来，而最先放进去的笔则藏在最底部，需要等上面的笔都拿完才能取出。

1.2 栈的核心特性与基本操作

栈的特性可总结为“三限定一特性”：

限定插入位置：仅栈顶；
限定删除位置：仅栈顶；
限定访问位置：仅栈顶；
核心特性：LIFO（后进先出）。

栈的基本操作（ISO/IEC 14882:2020（Java SE 17）标准定义）：

push(E e)：将元素e压入栈顶（插入）；
pop()：移除并返回栈顶元素（删除）；
peek()：返回栈顶元素但不移除（访问）；
isEmpty()：判断栈是否为空；
size()：返回栈中元素个数。

1.3 栈与其他线性结构的区别（易混淆点）

很多人会把栈和队列混淆，这里用表格明确区分：

结构	操作特性	典型应用场景
栈（Stack）	后进先出（LIFO）	函数调用、括号匹配
队列（Queue）	先进先出（FIFO）	任务排队、消息队列

二、栈的底层实现：数组栈 vs 链表栈

栈的实现有两种经典方式：基于数组的“数组栈”和基于链表的“链表栈”。两者各有优劣，需根据场景选择。

2.1 数组栈：基于动态数组的实现

数组栈的核心是用数组存储元素，栈顶指针指向数组末尾的元素。由于数组长度固定，需要实现“动态扩容”机制（权威参考：《算法（第4版）》Robert Sedgewick）。

2.1.1 数组栈的实现代码

package com.ken.stack;

import lombok.extern.slf4j.Slf4j;
import org.springframework.util.ObjectUtils;

import java.util.Arrays;

/**
 * 数组实现的栈（动态扩容）
 * 作者：ken
 */
@Slf4j
public class ArrayStack<E> {
    /**
     * 存储元素的数组
     */
    private Object[] elements;
    /**
     * 栈顶指针（初始为-1，表示空栈）
     */
    private int top;
    /**
     * 默认初始容量
     */
    private static final int DEFAULT_CAPACITY = 10;
    /**
     * 最大容量（避免OOM）
     */
    private static final int MAX_CAPACITY = Integer.MAX_VALUE - 8;

    /**
     * 构造方法：初始化默认容量
     */
    public ArrayStack() {
        elements = new Object[DEFAULT_CAPACITY];
        top = -1;
    }

    /**
     * 构造方法：指定初始容量
     * @param initialCapacity 初始容量
     * @throws IllegalArgumentException 初始容量非法时抛出
     */
    public ArrayStack(int initialCapacity) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("初始容量不能为负数：" + initialCapacity);
        }
        int capacity = initialCapacity == 0 ? DEFAULT_CAPACITY : initialCapacity;
        elements = new Object[capacity];
        top = -1;
    }

    /**
     * 压入元素到栈顶
     * @param e 待压入的元素
     */
    public void push(E e) {
        ensureCapacity(top + 2); // 检查容量，栈顶+1是新元素位置，需保证数组长度≥top+2
        elements[++top] = e;
        log.debug("元素{}已压入栈顶，当前栈顶指针：{}", e, top);
    }

    /**
     * 弹出栈顶元素
     * @return 栈顶元素
     * @throws IllegalStateException 栈为空时抛出
     */
    @SuppressWarnings("unchecked")
    public E pop() {
        if (isEmpty()) {
            throw new IllegalStateException("栈为空，无法执行pop操作");
        }
        E topElement = (E) elements[top];
        elements[top--] = null; // 清空引用，避免内存泄漏
        log.debug("元素{}已弹出栈顶，当前栈顶指针：{}", topElement, top);
        return topElement;
    }

    /**
     * 查看栈顶元素（不移除）
     * @return 栈顶元素
     * @throws IllegalStateException 栈为空时抛出
     */
    @SuppressWarnings("unchecked")
    public E peek() {
        if (isEmpty()) {
            throw new IllegalStateException("栈为空，无法执行peek操作");
        }
        return (E) elements[top];
    }

    /**
     * 判断栈是否为空
     * @return true=空栈，false=非空
     */
    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * 获取栈的大小
     * @return 元素个数
     */
    public int size() {
        return top + 1;
    }

    /**
     * 确保数组容量足够，不足则扩容
     * @param minCapacity 最小需要的容量
     */
    private void ensureCapacity(int minCapacity) {
        int oldCapacity = elements.length;
        if (minCapacity > oldCapacity) {
            int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容50%
            // 检查扩容后的容量是否超过最大限制，或仍不足
            if (newCapacity - minCapacity < 0) {
                newCapacity = minCapacity;
            }
            if (newCapacity - MAX_CAPACITY > 0) {
                newCapacity = handleMaxCapacity(minCapacity);
            }
            // 数组拷贝扩容
            elements = Arrays.copyOf(elements, newCapacity);
            log.debug("数组栈已扩容，旧容量：{}，新容量：{}", oldCapacity, newCapacity);
        }
    }

    /**
     * 处理最大容量限制
     * @param minCapacity 最小需要的容量
     * @return 最终容量
     * @throws OutOfMemoryError 容量超过最大值时抛出
     */
    private int handleMaxCapacity(int minCapacity) {
        if (minCapacity < 0) {
            throw new OutOfMemoryError("数组栈容量溢出");
        }
        return minCapacity > MAX_CAPACITY ? Integer.MAX_VALUE : MAX_CAPACITY;
    }

    /**
     * 清空栈
     */
    public void clear() {
        // 遍历清空元素引用
        for (int i = 0; i <= top; i++) {
            elements[i] = null;
        }
        top = -1;
        log.debug("数组栈已清空");
    }

    @Override
    public String toString() {
        if (isEmpty()) {
            return "ArrayStack[]";
        }
        StringBuilder sb = new StringBuilder("ArrayStack[");
        for (int i = 0; i <= top; i++) {
            sb.append(elements[i]);
            if (i != top) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

2.1.2 数组栈的测试代码

package com.ken.stack;

import lombok.extern.slf4j.Slf4j;

/**
 * 数组栈测试类
 * 作者：ken
 */
@Slf4j
public class ArrayStackTest {
    public static void main(String[] args) {
        ArrayStack<String> stack = new ArrayStack<>();
        // 压入元素
        stack.push("Java");
        stack.push("Python");
        stack.push("Go");
        log.info("当前栈内容：{}", stack); // 输出：ArrayStack[Java, Python, Go]
        log.info("栈顶元素：{}", stack.peek()); // 输出：Go
        log.info("栈大小：{}", stack.size()); // 输出：3

        // 弹出元素
        String popElement = stack.pop();
        log.info("弹出的元素：{}", popElement); // 输出：Go
        log.info("弹出后栈内容：{}", stack); // 输出：ArrayStack[Java, Python]

        // 清空栈
        stack.clear();
        log.info("清空后栈是否为空：{}", stack.isEmpty()); // 输出：true
    }
}

2.1.3 数组栈的优缺点

优点：随机访问快（数组下标直接定位）、实现简单；
缺点：扩容需要拷贝数组（耗时）、初始容量设置不当会浪费空间。

2.2 链表栈：基于单向链表的实现

链表栈用单向链表存储元素，栈顶指向链表的头节点（权威参考：《数据结构与算法（Java版）》邓俊辉）。由于链表是动态结构，无需扩容，但需要额外存储节点指针。

2.2.1 链表栈的实现代码

package com.ken.stack;

import lombok.extern.slf4j.Slf4j;

/**
 * 单向链表实现的栈
 * 作者：ken
 */
@Slf4j
public class LinkedStack<E> {
    /**
     * 链表节点类（static避免外部类引用导致内存泄漏）
     */
    private static class Node<E> {
        E item;
        Node<E> next;

        Node(E item, Node<E> next) {
            this.item = item;
            this.next = next;
        }
    }

    /**
     * 栈顶节点（初始为null，表示空栈）
     */
    private Node<E> top;
    /**
     * 栈大小
     */
    private int size;

    /**
     * 构造方法：初始化空栈
     */
    public LinkedStack() {
        top = null;
        size = 0;
    }

    /**
     * 压入元素到栈顶
     * @param e 待压入的元素
     */
    public void push(E e) {
        // 新节点指向原栈顶，栈顶更新为新节点
        top = new Node<>(e, top);
        size++;
        log.debug("元素{}已压入栈顶，当前栈大小：{}", e, size);
    }

    /**
     * 弹出栈顶元素
     * @return 栈顶元素
     * @throws IllegalStateException 栈为空时抛出
     */
    public E pop() {
        if (isEmpty()) {
            throw new IllegalStateException("栈为空，无法执行pop操作");
        }
        E topElement = top.item;
        Node<E> oldTop = top;
        top = top.next; // 栈顶更新为下一个节点
        oldTop.item = null; // 清空引用，避免内存泄漏
        oldTop.next = null;
        size--;
        log.debug("元素{}已弹出栈顶，当前栈大小：{}", topElement, size);
        return topElement;
    }

    /**
     * 查看栈顶元素（不移除）
     * @return 栈顶元素
     * @throws IllegalStateException 栈为空时抛出
     */
    public E peek() {
        if (isEmpty()) {
            throw new IllegalStateException("栈为空，无法执行peek操作");
        }
        return top.item;
    }

    /**
     * 判断栈是否为空
     * @return true=空栈，false=非空
     */
    public boolean isEmpty() {
        return top == null;
    }

    /**
     * 获取栈的大小
     * @return 元素个数
     */
    public int size() {
        return size;
    }

    /**
     * 清空栈
     */
    public void clear() {
        // 遍历链表，清空所有节点引用
        Node<E> current = top;
        while (current != null) {
            Node<E> next = current.next;
            current.item = null;
            current.next = null;
            current = next;
        }
        top = null;
        size = 0;
        log.debug("链表栈已清空");
    }

    @Override
    public String toString() {
        if (isEmpty()) {
            return "LinkedStack[]";
        }
        StringBuilder sb = new StringBuilder("LinkedStack[");
        Node<E> current = top;
        while (current != null) {
            sb.append(current.item);
            if (current.next != null) {
                sb.append(", ");
            }
            current = current.next;
        }
        sb.append("]");
        return sb.toString();
    }
}

2.2.2 链表栈的测试代码

package com.ken.stack;

import lombok.extern.slf4j.Slf4j;

/**
 * 链表栈测试类
 * 作者：ken
 */
@Slf4j
public class LinkedStackTest {
    public static void main(String[] args) {
        LinkedStack<Integer> stack = new LinkedStack<>();
        // 压入元素
        stack.push(10);
        stack.push(20);
        stack.push(30);
        log.info("当前栈内容：{}", stack); // 输出：LinkedStack[30, 20, 10]
        log.info("栈顶元素：{}", stack.peek()); // 输出：30
        log.info("栈大小：{}", stack.size()); // 输出：3

        // 弹出元素
        Integer popElement = stack.pop();
        log.info("弹出的元素：{}", popElement); // 输出：30
        log.info("弹出后栈内容：{}", stack); // 输出：LinkedStack[20, 10]

        // 清空栈
        stack.clear();
        log.info("清空后栈是否为空：{}", stack.isEmpty()); // 输出：true
    }
}

2.2.3 数组栈 vs 链表栈（性能对比）

操作	数组栈	链表栈
push	O(1)（扩容时O(n)）	O(1)
pop	O(1)	O(1)
peek	O(1)	O(1)
内存占用	可能有空闲空间浪费	每个节点额外存储指针
访问速度	快（数组连续内存）	慢（链表分散内存）

选型建议：如果元素数量可预测、追求访问速度，选数组栈；如果元素数量动态变化大、避免空间浪费，选链表栈。

三、栈的核心应用场景：从理论到实战

栈的“后进先出”特性使其成为解决特定问题的“利器”，以下是最经典的应用场景。

3.1 括号匹配校验（LeetCode 20题）

3.1.1 原理（权威参考：《算法导论》Thomas H. Cormen）

遇到左括号（(、[、{）时压入栈；
遇到右括号（)、]、}）时，弹出栈顶元素并匹配：
- 若栈为空或不匹配，直接返回false；
- 若匹配，继续遍历；
遍历结束后，栈为空则所有括号匹配，否则不匹配。

3.1.2 流程图

3.1.3 实现代码

package com.ken.stack.application;

import com.google.common.collect.Maps;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.CollectionUtils;

import java.util.Deque;
import java.util.Map;
import java.util.ArrayDeque;

/**
 * 括号匹配校验工具类
 * 作者：ken
 */
@Slf4j
public class BracketMatcher {
    /**
     * 右括号到左括号的映射（避免多次if判断）
     */
    private static final Map<Character, Character> BRACKET_MAP = Maps.newHashMap();

    static {
        BRACKET_MAP.put(')', '(');
        BRACKET_MAP.put(']', '[');
        BRACKET_MAP.put('}', '{');
    }

    /**
     * 校验括号是否匹配
     * @param s 待校验的字符串（仅包含括号）
     * @return true=匹配，false=不匹配
     * @throws IllegalArgumentException 字符串为空时抛出
     */
    public static boolean isValid(String s) {
        if (org.springframework.util.StringUtils.hasText(s, "待校验字符串不能为空")) {
            Deque<Character> stack = new ArrayDeque<>(); // 推荐用Deque代替Stack（Java官方建议）
            for (char c : s.toCharArray()) {
                if (BRACKET_MAP.containsValue(c)) {
                    // 左括号压栈
                    stack.push(c);
                    log.debug("左括号{}压入栈", c);
                } else if (BRACKET_MAP.containsKey(c)) {
                    // 右括号匹配
                    if (CollectionUtils.isEmpty(stack) || !stack.pop().equals(BRACKET_MAP.get(c))) {
                        log.debug("括号不匹配，当前字符：{}", c);
                        return false;
                    }
                    log.debug("右括号{}匹配成功", c);
                }
            }
            boolean result = stack.isEmpty();
            log.debug("括号匹配校验结果：{}", result);
            return result;
        }
        return false;
    }

    public static void main(String[] args) {
        String validStr = "({[]})";
        String invalidStr = "({[})";
        log.info("字符串{}的括号匹配结果：{}", validStr, isValid(validStr)); // true
        log.info("字符串{}的括号匹配结果：{}", invalidStr, isValid(invalidStr)); // false
    }
}

3.2 中缀表达式转后缀表达式（逆波兰表示法）

3.2.1 原理（权威参考：《编译原理》Alfred V. Aho）

中缀表达式（如3+4*2）是人类习惯的写法，但计算机难以直接计算，需转为后缀表达式（如3 4 2 * +）。转换规则：

初始化栈存储运算符；
遍历中缀表达式的每个元素：
- 若为操作数，直接输出；
- 若为左括号，压入栈；
- 若为右括号，弹出栈顶运算符直到左括号（左括号不输出）；
- 若为运算符，弹出栈顶优先级≥当前运算符的元素，再压入当前运算符；
遍历结束后，弹出栈中所有运算符。

3.2.2 实现代码

package com.ken.stack.application;

import com.google.common.collect.Maps;
import lombok.extern.slf4j.Slf4j;
import org.springframework.util.StringUtils;

import java.util.Deque;
import java.util.ArrayDeque;
import java.util.List;
import java.util.Map;

/**
 * 中缀表达式转后缀表达式工具类
 * 作者：ken
 */
@Slf4j
public class InfixToPostfixConverter {
    /**
     * 运算符优先级：越高优先级越大
     */
    private static final Map<Character, Integer> OP_PRIORITY = Maps.newHashMap();

    static {
        OP_PRIORITY.put('+', 1);
        OP_PRIORITY.put('-', 1);
        OP_PRIORITY.put('*', 2);
        OP_PRIORITY.put('/', 2);
        OP_PRIORITY.put('(', 0); // 左括号优先级最低
    }

    /**
     * 中缀表达式转后缀表达式
     * @param infix 中缀表达式（如"3+4*2-(5+1)"）
     * @return 后缀表达式（空格分隔）
     * @throws IllegalArgumentException 表达式非法时抛出
     */
    public static String convert(String infix) {
        if (!StringUtils.hasText(infix, "中缀表达式不能为空")) {
            throw new IllegalArgumentException("中缀表达式不能为空");
        }

        Deque<Character> opStack = new ArrayDeque<>();
        StringBuilder postfix = new StringBuilder();
        List<Character> operators = List.of('+', '-', '*', '/', '(', ')');

        for (char c : infix.toCharArray()) {
            if (Character.isDigit(c)) {
                // 操作数直接输出
                postfix.append(c).append(" ");
            } else if (c == '(') {
                // 左括号压栈
                opStack.push(c);
            } else if (c == ')') {
                // 右括号：弹出直到左括号
                while (!opStack.isEmpty() && opStack.peek() != '(') {
                    postfix.append(opStack.pop()).append(" ");
                }
                opStack.pop(); // 弹出左括号（不输出）
            } else if (operators.contains(c)) {
                // 运算符：弹出优先级≥当前的
                while (!opStack.isEmpty() && OP_PRIORITY.get(opStack.peek()) >= OP_PRIORITY.get(c)) {
                    postfix.append(opStack.pop()).append(" ");
                }
                opStack.push(c);
            }
        }

        // 弹出剩余运算符
        while (!opStack.isEmpty()) {
            postfix.append(opStack.pop()).append(" ");
        }

        String result = postfix.toString().trim();
        log.debug("中缀表达式{}转为后缀表达式：{}", infix, result);
        return result;
    }

    public static void main(String[] args) {
        String infix = "3+4*2-(5+1)";
        String postfix = convert(infix);
        log.info("转换结果：{}", postfix); // 输出：3 4 2 * + 5 1 + -
    }
}

3.3 后缀表达式求值（逆波兰计算器）

3.3.1 原理

遍历后缀表达式的每个元素：
- 若为操作数，压入栈；
- 若为运算符，弹出栈顶两个元素（先弹出的是右操作数，后弹出的是左操作数），计算后将结果压入栈；
遍历结束后，栈顶元素即为结果。

3.3.2 实现代码

package com.ken.stack.application;

import lombok.extern.slf4j.Slf4j;
import org.springframework.util.StringUtils;

import java.util.Deque;
import java.util.ArrayDeque;

/**
 * 后缀表达式求值工具类
 * 作者：ken
 */
@Slf4j
public class PostfixEvaluator {
    /**
     * 计算后缀表达式的值
     * @param postfix 后缀表达式（空格分隔，如"3 4 2 * + 5 1 + -"）
     * @return 计算结果
     * @throws IllegalArgumentException 表达式非法时抛出
     */
    public static int evaluate(String postfix) {
        if (!StringUtils.hasText(postfix, "后缀表达式不能为空")) {
            throw new IllegalArgumentException("后缀表达式不能为空");
        }

        Deque<Integer> numStack = new ArrayDeque<>();
        String[] tokens = postfix.split(" ");

        for (String token : tokens) {
            if (token.matches("\\d+")) {
                // 操作数压栈
                numStack.push(Integer.parseInt(token));
            } else {
                // 运算符计算
                if (numStack.size() < 2) {
                    throw new IllegalArgumentException("后缀表达式格式错误：操作数不足");
                }
                int right = numStack.pop();
                int left = numStack.pop();
                int result = switch (token) {
                    case "+" -> left + right;
                    case "-" -> left - right;
                    case "*" -> left * right;
                    case "/" -> {
                        if (right == 0) {
                            throw new ArithmeticException("除数不能为0");
                        }
                        yield left / right;
                    }
                    default -> throw new IllegalArgumentException("不支持的运算符：" + token);
                };
                numStack.push(result);
                log.debug("计算{} {} {} = {}", left, token, right, result);
            }
        }

        if (numStack.size() != 1) {
            throw new IllegalArgumentException("后缀表达式格式错误：剩余操作数");
        }

        int finalResult = numStack.pop();
        log.debug("后缀表达式{}的计算结果：{}", postfix, finalResult);
        return finalResult;
    }

    public static void main(String[] args) {
        String postfix = "3 4 2 * + 5 1 + -";
        int result = evaluate(postfix);
        log.info("最终结果：{}", result); // 输出：3 + (4*2) - (5+1) = 3+8-6=5
    }
}

3.4 浏览器的前进后退功能

3.4.1 原理

用两个栈：forwardStack（前进栈）和backStack（后退栈）；
访问新页面时：将当前页面压入backStack，清空forwardStack；
点击后退时：将当前页面压入forwardStack，从backStack弹出页面作为当前页；
点击前进时：将当前页面压入backStack，从forwardStack弹出页面作为当前页。

3.4.2 实现代码

package com.ken.stack.application;

import lombok.extern.slf4j.Slf4j;
import org.springframework.util.StringUtils;

import java.util.Deque;
import java.util.ArrayDeque;

/**
 * 模拟浏览器前进后退功能
 * 作者：ken
 */
@Slf4j
public class BrowserHistory {
    /**
     * 后退栈（存储已访问的页面）
     */
    private Deque<String> backStack;
    /**
     * 前进栈（存储可前进的页面）
     */
    private Deque<String> forwardStack;
    /**
     * 当前页面
     */
    private String currentPage;

    /**
     * 构造方法：初始化首页
     * @param homepage 首页URL
     */
    public BrowserHistory(String homepage) {
        if (!StringUtils.hasText(homepage, "首页URL不能为空")) {
            throw new IllegalArgumentException("首页URL不能为空");
        }
        backStack = new ArrayDeque<>();
        forwardStack = new ArrayDeque<>();
        currentPage = homepage;
        log.debug("初始化浏览器，首页：{}", currentPage);
    }

    /**
     * 访问新页面
     * @param url 新页面URL
     */
    public void visit(String url) {
        if (!StringUtils.hasText(url, "页面URL不能为空")) {
            throw new IllegalArgumentException("页面URL不能为空");
        }
        backStack.push(currentPage); // 当前页压入后退栈
        currentPage = url;
        forwardStack.clear(); // 清空前进栈
        log.debug("访问新页面：{}，后退栈：{}", currentPage, backStack);
    }

    /**
     * 后退操作
     * @param steps 后退步数
     * @return 后退后的当前页面
     */
    public String back(int steps) {
        if (steps < 0) {
            throw new IllegalArgumentException("后退步数不能为负数");
        }
        for (int i = 0; i < steps; i++) {
            if (backStack.isEmpty()) {
                log.debug("已到最开始页面，无法继续后退");
                break;
            }
            forwardStack.push(currentPage); // 当前页压入前进栈
            currentPage = backStack.pop();
            log.debug("后退一步，当前页面：{}", currentPage);
        }
        return currentPage;
    }

    /**
     * 前进操作
     * @param steps 前进步数
     * @return 前进后的当前页面
     */
    public String forward(int steps) {
        if (steps < 0) {
            throw new IllegalArgumentException("前进步数不能为负数");
        }
        for (int i = 0; i < steps; i++) {
            if (forwardStack.isEmpty()) {
                log.debug("已到最新页面，无法继续前进");
                break;
            }
            backStack.push(currentPage); // 当前页压入后退栈
            currentPage = forwardStack.pop();
            log.debug("前进一步，当前页面：{}", currentPage);
        }
        return currentPage;
    }

    /**
     * 获取当前页面
     * @return 当前页面URL
     */
    public String getCurrentPage() {
        return currentPage;
    }

    public static void main(String[] args) {
        BrowserHistory browser = new BrowserHistory("https://www.ken.com");
        browser.visit("https://www.ken.com/page1");
        browser.visit("https://www.ken.com/page2");
        log.info("当前页面：{}", browser.getCurrentPage()); // page2

        browser.back(1);
        log.info("后退1步后页面：{}", browser.getCurrentPage()); // page1

        browser.forward(1);
        log.info("前进1步后页面：{}", browser.getCurrentPage()); // page2

        browser.back(2);
        log.info("后退2步后页面：{}", browser.getCurrentPage()); // 首页
    }
}

3.5 JVM的方法调用栈（实战底层原理）

JVM中的“Java虚拟机栈”是栈结构的典型应用（权威参考：《Java虚拟机规范（Java SE 17版）》）：

每个方法调用时，JVM会创建一个“栈帧”（Stack Frame）并压入虚拟机栈；
栈帧存储方法的局部变量表、操作数栈、方法返回地址等；
方法执行完毕后，栈帧弹出，控制权返回给调用方；
若方法嵌套调用过深（如递归无终止条件），会导致栈溢出（StackOverflowError）。

示例：递归求阶乘（栈溢出演示）

package com.ken.stack.application;

import lombok.extern.slf4j.Slf4j;

/**
 * JVM方法调用栈演示
 * 作者：ken
 */
@Slf4j
public class MethodCallStackDemo {
    /**
     * 递归求阶乘
     * @param n 正整数
     * @return n的阶乘
     */
    public static long factorial(int n) {
        if (n == 1) {
            return 1;
        }
        log.debug("计算{}!，调用{}!，当前栈深度：{}", n, n-1, Thread.currentThread().getStackTrace().length);
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        try {
            // 当n足够大时（如10000），会抛出StackOverflowError
            long result = factorial(5);
            log.info("5! = {}", result); // 输出：120
        } catch (StackOverflowError e) {
            log.error("栈溢出：{}", e.getMessage());
        }
    }
}

四、实战项目：基于栈的日志处理系统（Spring Boot + MyBatis Plus）

以下是一个结合栈的实战项目：用栈存储用户操作日志，实现“撤销”（undo）和“重做”（redo）功能，并将日志持久化到MySQL。

4.1 技术栈

Spring Boot 3.2.0（最新稳定版）
MyBatis Plus 3.5.5（最新稳定版）
MySQL 8.0.35
Lombok 1.18.30
Swagger 3（SpringDoc OpenAPI 2.3.0）

4.2 项目结构

com.ken.stack.logsystem
├── controller      // 控制器
├── entity          // 实体类
├── mapper          // Mapper接口
├── service         // 服务层
├── util            // 工具类
└── LogSystemApplication.java // 启动类

4.3 核心代码

4.3.1 pom.xml（依赖配置）

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <parent>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-parent</artifactId>
        <version>3.2.0</version>
        <relativePath/>
    </parent>

    <groupId>com.ken</groupId>
    <artifactId>stack-log-system</artifactId>
    <version>1.0.0</version>

    <properties>
        <maven.compiler.source>17</maven.compiler.source>
        <maven.compiler.target>17</maven.compiler.target>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
        <mybatis-plus.version>3.5.5</mybatis-plus.version>
        <springdoc.version>2.3.0</springdoc.version>
        <lombok.version>1.18.30</lombok.version>
    </properties>

    <dependencies>
        <!-- Spring Boot核心 -->
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-web</artifactId>
        </dependency>

        <!-- MyBatis Plus -->
        <dependency>
            <groupId>com.baomidou</groupId>
            <artifactId>mybatis-plus-boot-starter</artifactId>
            <version>${mybatis-plus.version}</version>
        </dependency>

        <!-- MySQL驱动 -->
        <dependency>
            <groupId>com.mysql</groupId>
            <artifactId>mysql-connector-j</artifactId>
            <scope>runtime</scope>
        </dependency>

        <!-- Lombok -->
        <dependency>
            <groupId>org.projectlombok</groupId>
            <artifactId>lombok</artifactId>
            <version>${lombok.version}</version>
            <scope>provided</scope>
        </dependency>

        <!-- SpringDoc OpenAPI（Swagger 3） -->
        <dependency>
            <groupId>org.springdoc</groupId>
            <artifactId>springdoc-openapi-starter-webmvc-ui</artifactId>
            <version>${springdoc.version}</version>
        </dependency>

        <!-- Spring Utils -->
        <dependency>
            <groupId>org.springframework</groupId>
            <artifactId>spring-core</artifactId>
        </dependency>

        <!-- Guava -->
        <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>32.1.3-jre</version>
        </dependency>
    </dependencies>

    <build>
        <plugins>
            <plugin>
                <groupId>org.springframework.boot</groupId>
                <artifactId>spring-boot-maven-plugin</artifactId>
                <configuration>
                    <excludes>
                        <exclude>
                            <groupId>org.projectlombok</groupId>
                            <artifactId>lombok</artifactId>
                        </exclude>
                    </excludes>
                </configuration>
            </plugin>
        </plugins>
    </build>
</project>

4.3.2 实体类（OperationLog.java）

package com.ken.stack.logsystem.entity;

import com.baomidou.mybatisplus.annotation.IdType;
import com.baomidou.mybatisplus.annotation.TableId;
import com.baomidou.mybatisplus.annotation.TableName;
import lombok.Data;

import java.time.LocalDateTime;

/**
 * 操作日志实体类
 * 作者：ken
 */
@Data
@TableName("operation_log")
public class OperationLog {
    /**
     * 主键ID
     */
    @TableId(type = IdType.AUTO)
    private Long id;

    /**
     * 用户ID
     */
    private Long userId;

    /**
     * 操作内容
     */
    private String operationContent;

    /**
     * 操作时间
     */
    private LocalDateTime operationTime;
}

4.3.3 Mapper接口（OperationLogMapper.java）

package com.ken.stack.logsystem.mapper;

import com.baomidou.mybatisplus.core.mapper.BaseMapper;
import com.ken.stack.logsystem.entity.OperationLog;
import org.apache.ibatis.annotations.Mapper;

/**
 * 操作日志Mapper
 * 作者：ken
 */
@Mapper
public interface OperationLogMapper extends BaseMapper<OperationLog> {
}

4.3.4 服务层（LogService.java）

package com.ken.stack.logsystem.service;

import com.baomidou.mybatisplus.extension.service.impl.ServiceImpl;
import com.ken.stack.logsystem.entity.OperationLog;
import com.ken.stack.logsystem.mapper.OperationLogMapper;
import lombok.extern.slf4j.Slf4j;
import org.springframework.stereotype.Service;

import java.time.LocalDateTime;
import java.util.Deque;
import java.util.ArrayDeque;

/**
 * 日志服务（包含undo/redo功能）
 * 作者：ken
 */
@Slf4j
@Service
public class LogService extends ServiceImpl<OperationLogMapper, OperationLog> {
    /**
     * 操作栈（存储已执行的操作）
     */
    private final Deque<OperationLog> operationStack = new ArrayDeque<>();
    /**
     * 重做栈（存储已撤销的操作）
     */
    private final Deque<OperationLog> redoStack = new ArrayDeque<>();

    /**
     * 记录操作日志并压入栈
     * @param userId 用户ID
     * @param content 操作内容
     * @return 保存的日志对象
     */
    public OperationLog recordLog(Long userId, String content) {
        OperationLog log = new OperationLog();
        log.setUserId(userId);
        log.setOperationContent(content);
        log.setOperationTime(LocalDateTime.now());
        // 保存到数据库
        save(log);
        // 压入操作栈
        operationStack.push(log);
        // 清空重做栈
        redoStack.clear();
        log.debug("记录操作日志：{}，操作栈大小：{}", content, operationStack.size());
        return log;
    }

    /**
     * 撤销最后一次操作
     * @return 撤销的日志对象
     */
    public OperationLog undo() {
        if (operationStack.isEmpty()) {
            log.warn("操作栈为空，无法撤销");
            return null;
        }
        OperationLog undoneLog = operationStack.pop();
        // 压入重做栈
        redoStack.push(undoneLog);
        // 从数据库删除（模拟撤销）
        removeById(undoneLog.getId());
        log.debug("撤销操作：{}，重做栈大小：{}", undoneLog.getOperationContent(), redoStack.size());
        return undoneLog;
    }

    /**
     * 重做最后一次撤销的操作
     * @return 重做的日志对象
     */
    public OperationLog redo() {
        if (redoStack.isEmpty()) {
            log.warn("重做栈为空，无法重做");
            return null;
        }
        OperationLog redoneLog = redoStack.pop();
        // 重新保存到数据库
        save(redoneLog);
        // 压入操作栈
        operationStack.push(redoneLog);
        log.debug("重做操作：{}，操作栈大小：{}", redoneLog.getOperationContent(), operationStack.size());
        return redoneLog;
    }

    /**
     * 获取当前操作栈的大小
     * @return 操作栈大小
     */
    public int getOperationStackSize() {
        return operationStack.size();
    }

    /**
     * 获取当前重做栈的大小
     * @return 重做栈大小
     */
    public int getRedoStackSize() {
        return redoStack.size();
    }
}

4.3.5 控制器（LogController.java）

package com.ken.stack.logsystem.controller;

import com.ken.stack.logsystem.entity.OperationLog;
import com.ken.stack.logsystem.service.LogService;
import io.swagger.v3.oas.annotations.Operation;
import io.swagger.v3.oas.annotations.Parameter;
import io.swagger.v3.oas.annotations.tags.Tag;
import lombok.RequiredArgsConstructor;
import lombok.extern.slf4j.Slf4j;
import org.springframework.web.bind.annotation.*;

/**
 * 日志控制器
 * 作者：ken
 */
@Slf4j
@RestController
@RequestMapping("/api/log")
@RequiredArgsConstructor
@Tag(name = "日志管理接口", description = "包含记录、撤销、重做日志的接口")
public class LogController {
    private final LogService logService;

    @PostMapping("/record")
    @Operation(summary = "记录操作日志", description = "记录用户操作日志并压入栈")
    public OperationLog recordLog(
            @Parameter(description = "用户ID", required = true) @RequestParam Long userId,
            @Parameter(description = "操作内容", required = true) @RequestParam String content
    ) {
        return logService.recordLog(userId, content);
    }

    @PostMapping("/undo")
    @Operation(summary = "撤销操作", description = "撤销最后一次操作日志")
    public OperationLog undo() {
        return logService.undo();
    }

    @PostMapping("/redo")
    @Operation(summary = "重做操作", description = "重做最后一次撤销的操作日志")
    public OperationLog redo() {
        return logService.redo();
    }

    @GetMapping("/stack/size")
    @Operation(summary = "获取栈大小", description = "获取操作栈和重做栈的大小")
    public String getStackSize() {
        return String.format("操作栈大小：%d，重做栈大小：%d",
                logService.getOperationStackSize(), logService.getRedoStackSize());
    }
}

4.3.6 启动类（LogSystemApplication.java）

package com.ken.stack.logsystem;

import org.mybatis.spring.annotation.MapperScan;
import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;

/**
 * 日志系统启动类
 * 作者：ken
 */
@SpringBootApplication
@MapperScan("com.ken.stack.logsystem.mapper")
public class LogSystemApplication {
    public static void main(String[] args) {
        SpringApplication.run(LogSystemApplication.class, args);
    }
}

4.3.7 配置文件（application.yml）

spring:
  datasource:
    url: jdbc:mysql://localhost:3306/stack_log_db?useUnicode=true&characterEncoding=utf8&useSSL=false&serverTimezone=Asia/Shanghai
    username: root
    password: root
    driver-class-name: com.mysql.cj.jdbc.Driver

mybatis-plus:
  configuration:
    map-underscore-to-camel-case: true
    log-impl: org.apache.ibatis.logging.stdout.StdOutImpl
  global-config:
    db-config:
      id-type: auto

springdoc:
  swagger-ui:
    path: /swagger-ui.html
    operationsSorter: method
  api-docs:
    path: /v3/api-docs

4.3.8 MySQL表结构（stack_log_db.operation_log）

CREATE DATABASE IF NOT EXISTS stack_log_db DEFAULT CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_ci;

USE stack_log_db;

CREATE TABLE IF NOT EXISTS operation_log (
    id BIGINT AUTO_INCREMENT PRIMARY KEY COMMENT '主键ID',
    user_id BIGINT NOT NULL COMMENT '用户ID',
    operation_content VARCHAR(255) NOT NULL COMMENT '操作内容',
    operation_time DATETIME NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '操作时间'
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT='操作日志表';

4.4 测试接口（Swagger）

启动项目后，访问http://localhost:8080/swagger-ui.html，可测试以下接口：

POST /api/log/record：记录操作日志；
POST /api/log/undo：撤销最后一次操作；
POST /api/log/redo：重做最后一次撤销的操作；
GET /api/log/stack/size：查看栈大小。

五、总结：栈的“简单”与“强大”

栈作为一种“受限”的线性结构，看似功能单一，却凭借“后进先出”的特性成为解决特定问题的关键。从底层的数组/链表实现，到上层的括号匹配、表达式求值，再到实战中的日志撤销/重做、JVM方法调用，栈的应用无处不在。

掌握栈的核心逻辑，不仅能夯实数据结构基础，更能在实际开发中用“极简”的结构解决复杂问题。正如《算法（第4版）》中所说：“简单的结构往往蕴含着强大的力量”——这正是栈的魅力所在。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2025-11-24，如有侵权请联系 cloudcommunity@tencent.com 删除

链表

本文分享自果酱带你啃java 微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

栈：线性结构中的 “后进先出” 王者，从底层逻辑到实战应用全解析

栈：线性结构中的 “后进先出” 王者，从底层逻辑到实战应用全解析

栈：线性结构中的“后进先出”王者，从底层逻辑到实战应用全解析

一、栈的基础认知：什么是“后进先出”？

1.1 栈的定义（权威来源：《数据结构与算法分析：Java语言描述》Mark Allen Weiss）

1.2 栈的核心特性与基本操作

1.3 栈与其他线性结构的区别（易混淆点）

二、栈的底层实现：数组栈 vs 链表栈

2.1 数组栈：基于动态数组的实现

2.1.1 数组栈的实现代码

2.1.2 数组栈的测试代码

2.1.3 数组栈的优缺点

2.2 链表栈：基于单向链表的实现

2.2.1 链表栈的实现代码

2.2.2 链表栈的测试代码

2.2.3 数组栈 vs 链表栈（性能对比）

三、栈的核心应用场景：从理论到实战

3.1 括号匹配校验（LeetCode 20题）

3.1.1 原理（权威参考：《算法导论》Thomas H. Cormen）

3.1.2 流程图

3.1.3 实现代码

3.2 中缀表达式转后缀表达式（逆波兰表示法）

3.2.1 原理（权威参考：《编译原理》Alfred V. Aho）

3.2.2 实现代码

3.3 后缀表达式求值（逆波兰计算器）

3.3.1 原理

3.3.2 实现代码

3.4 浏览器的前进后退功能

3.4.1 原理

3.4.2 实现代码

3.5 JVM的方法调用栈（实战底层原理）

四、实战项目：基于栈的日志处理系统（Spring Boot + MyBatis Plus）

4.1 技术栈

4.2 项目结构

4.3 核心代码

4.3.1 pom.xml（依赖配置）

4.3.2 实体类（OperationLog.java）

4.3.3 Mapper接口（OperationLogMapper.java）

4.3.4 服务层（LogService.java）

4.3.5 控制器（LogController.java）

4.3.6 启动类（LogSystemApplication.java）

4.3.7 配置文件（application.yml）

4.3.8 MySQL表结构（stack_log_db.operation_log）

4.4 测试接口（Swagger）

五、总结：栈的“简单”与“强大”

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐