栈与队列是数据结构里最基础也最容易被轻视的两个结构。很多初学者觉得它们“不就是个数组加点限制吗”但实际工作中从函数调用栈到消息队列从浏览器的前进后退到操作系统的任务调度到处都有它们的影子。面试的时候这两个结构也是最常被拿出来考手写代码的题目。这篇文章我不打算写成教科书式的枯燥讲义而是用一篇完整的实战笔记把栈和队列从原理讲到应用再讲到源码最后给出可直接复用的代码实现。不管你是刚学数据结构的新手还是准备面试的开发者这篇文章都能给你一个足够清晰完整的视角。1. 栈后进先出的世界1.1 为什么说栈是一种“受限”的线性表栈的本质是一个线性表但它只在表尾进行插入和删除操作。这个“表尾”在栈的语境里叫栈顶top另一端叫栈底bottom。所以栈的所有操作都被限制在一个端点这就是“受限”的含义。想象一个叠盘子的场景你只能从最上面取盘子也只能把新盘子放到最上面。如果你想要最底下的那个盘子就得先把上面所有的盘子都移开。这就是后进先出LIFOLast In First Out的直观感受。栈的核心操作只有五个push(x)元素入栈放到栈顶pop()弹出栈顶元素并返回peek()查看栈顶元素但不弹出isEmpty()判断栈是否为空size()返回栈中元素个数这些操作的共同特点是时间复杂度为O(1)不管栈里有多少元素每次操作都只涉及栈顶这一个位置。1.2 基于数组的栈实现动态扩容是核心用数组实现栈是最自然的方式。但直接用固定数组会遇到一个问题栈满了怎么办所以实战中我们需要实现一个动态扩容的版本。来看一段完整的Java实现public class ArrayStackT { private static final int DEFAULT_CAPACITY 10; private Object[] elements; private int top -1; // 栈顶指针-1表示空栈 public ArrayStack() { this(DEFAULT_CAPACITY); } public ArrayStack(int initialCapacity) { if (initialCapacity 0) { throw new IllegalArgumentException(容量必须大于0); } elements new Object[initialCapacity]; } public boolean push(T item) { ensureCapacity(); elements[top] item; return true; } SuppressWarnings(unchecked) public T pop() { if (isEmpty()) { throw new IllegalStateException(栈为空无法弹出); } T result (T) elements[top]; elements[top] null; // 帮助GC回收 top--; return result; } SuppressWarnings(unchecked) public T peek() { if (isEmpty()) { throw new IllegalStateException(栈为空无法查看); } return (T) elements[top]; } public boolean isEmpty() { return top -1; } public int size() { return top 1; } private void ensureCapacity() { if (top 1 elements.length) { int newCapacity elements.length * 2; elements Arrays.copyOf(elements, newCapacity); } } }这里有几个细节值得注意栈顶指针为什么初始化为-1因为数组下标从0开始空栈时栈顶指针指向“数组第一个位置的前一个位置”也就是-1。这样第一个元素入栈后栈顶指针变成0正好指向该元素的位置。pop的时候为什么要手动置null如果只是把top减一数组里那个位置还持有对象引用这个对象就永远无法被垃圾回收造成内存泄漏。在大数据量高频率的栈操作场景下这个细节很关键。扩容为什么是翻倍而不是加固定值翻倍扩容的均摊时间复杂度是O(1)——每次扩容后可以继续执行O(n)次push才需要再次扩容。如果固定加10扩容过于频繁push的均摊复杂度会退化到O(n)。1.3 基于链表的栈实现无容量限制的灵活方案数组栈的好处是内存连续缓存友好但扩容时有数据拷贝开销。链表栈的优势则是不存在扩容概念天然动态但每个节点都有指针的内存开销。链表栈实现public class LinkedStackT { private NodeT topNode; private int size; private static class NodeT { T data; NodeT next; Node(T data, NodeT next) { this.data data; this.next next; } } public void push(T item) { topNode new Node(item, topNode); size; } public T pop() { if (isEmpty()) { throw new IllegalStateException(栈为空无法弹出); } T data topNode.data; topNode topNode.next; size--; return data; } public T peek() { if (isEmpty()) { throw new IllegalStateException(栈为空无法查看); } return topNode.data; } public boolean isEmpty() { return topNode null; } public int size() { return size; } }链表版的关键在于push操作新节点直接指向原来的栈顶节点然后更新栈顶指针。整个过程不需要遍历链表时间复杂度O(1)。两种实现各有优劣以下是实际选型时的对比维度数组栈链表栈内存连续性连续缓存友好不连续缓存不友好扩容需要动态扩容和拷贝天然动态无需扩容空间占用可能有预留空间浪费每个节点额外存储指针访问速度快随机访问相对慢节点分散适用场景元素数量可预估数量不可预估且变化大1.4 栈的经典应用别小看这五个场景场景一函数调用栈程序每一次函数调用系统都会在栈上压入一个栈帧保存局部变量、返回地址、参数等信息。函数返回时栈帧被弹出。递归之所以容易栈溢出就是因为每一层递归都在压栈而系统栈空间是有限的。// 这段代码会导致栈溢出 public void infiniteLoop() { infiniteLoop(); // 每调用一次压一帧直到栈空间耗尽 }场景二括号匹配检验编译器检查代码中括号是否匹配本质就是栈的应用。遍历整个字符串遇到左括号就push遇到右括号就pop并比对是否匹配。public static boolean isValidBracket(String s) { DequeCharacter stack new ArrayDeque(); MapCharacter, Character map Map.of( ), (, ], [, }, { ); for (char c : s.toCharArray()) { 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(); }场景三表达式求值中缀表达式转后缀表达式逆波兰式是栈的经典应用。操作符栈用于保存等待处理的运算符当遇到优先级较低的运算符时先把栈里高优先级的运算符弹出。场景四浏览器前进后退这其实是两个栈配合使用。当前页面作为分界线一个栈存“后退”页面另一个栈存“前进”页面。点后退时把当前页面压入前进栈从后退栈弹出页面点前进时反过来。场景五撤销操作文本编辑器里的CtrlZ每次操作把状态快照或操作反动作压入栈撤销时从栈顶弹出恢复。2. 队列先进先出的管道2.1 队列的本质与核心操作队列和栈正好相反它在一端队尾插入在另一端队头删除遵循先进先出FIFO, First In First Out原则。生活中的例子很好找食堂排队打饭先到的人先打到饭打印机任务队列先提交的任务先打印。队列的核心操作有enqueue(x)入队在队尾添加元素dequeue()出队移除队头元素并返回front()查看队头元素isEmpty()判断队列是否为空size()获取队列长度2.2 数组队列的致命问题假溢出如果直接用数组头尾两个指针实现队列会出现一个严重问题。随着元素的入队和出队尾部指针不断后移当尾部指针到达数组末尾时即便数组前面有空闲位置也无法再入队了。这就是“假溢出”。解决假溢出的方案是循环队列把数组看成一个首尾相接的环当tail到达数组末尾时如果头部位置有空间就绕回到数组开头继续插入。public class CircularQueueT { private Object[] elements; private int head 0; private int tail 0; private int size 0; public CircularQueue(int capacity) { elements new Object[capacity]; } public boolean enqueue(T item) { if (isFull()) { return false; } elements[tail] item; tail (tail 1) % elements.length; size; return true; } SuppressWarnings(unchecked) public T dequeue() { if (isEmpty()) { throw new IllegalStateException(队列为空); } T result (T) elements[head]; elements[head] null; head (head 1) % elements.length; size--; return result; } public boolean isEmpty() { return size 0; } public boolean isFull() { return size elements.length; } public int size() { return size; } }这里最需要理解的是(tail 1) % elements.length这个操作。取模运算让指针在到达数组末尾后自动回到开头实现“循环”效果。关于循环队列有两个容易踩坑的点必须说明坑一空和满的区分。如果不维护size字段单靠head tail无法区分队列是空还是满两种情况都满足。经典做法是牺牲一个存储单元队满条件写成(tail 1) % capacity head此时实际存储最多capacity-1个元素。我在实现中选择了单独维护size字段这样逻辑更直观空间利用率也更高。坑二出队时置null。和栈一样出队时如果不把原位置置null对象引用会一直存在造成隐性内存泄漏。2.3 链表队列另一种自然的实现方案链表实现队列时需要维护两个引用队头head和队尾tail。入队操作在tail处进行出队操作在head处进行。public class LinkedQueueT { private NodeT head; private NodeT tail; private int size; private static class NodeT { T data; NodeT next; Node(T data) { this.data data; } } public void enqueue(T item) { NodeT oldTail tail; tail new Node(item); if (head null) { head tail; } else { oldTail.next tail; } size; } public T dequeue() { if (head null) { throw new IllegalStateException(队列为空); } T data head.data; head head.next; if (head null) { tail null; } size--; return data; } public T front() { if (head null) { throw new IllegalStateException(队列为空); } return head.data; } public boolean isEmpty() { return head null; } }链表队列的细节在于维护tail。当队列为空时head和tail都为null。第一个元素入队时head和tail都指向它。当最后一个元素出队时head变为null此时必须把tail也置为null否则tail会悬垂指向一个已经出队的节点。2.4 双端队列与优先队列双端队列Deque是队列的进阶版它允许在队头和队尾都进行插入和删除操作。Java的ArrayDeque是双端队列的标准实现它既可以当栈用push/pop在头部操作也可以当普通队列用addLast/removeFirst性能都很优秀。优先队列PriorityQueue则彻底打破了FIFO的规则。它按照元素的优先级出队而不是按照入队顺序。底层实现是二叉堆插入和删除的时间复杂度都是O(log n)。任务调度、Dijkstra最短路径算法等都依赖优先队列。3. 栈和队列的实战应用不只是数据结构课3.1 用两个栈实现队列这道面试经典题思路非常巧妙。一个栈专门负责入队inputStack一个栈专门负责出队outputStack。public class TwoStackQueueT { private DequeT inputStack new ArrayDeque(); private DequeT outputStack new ArrayDeque(); public void enqueue(T item) { inputStack.push(item); } public T dequeue() { if (outputStack.isEmpty()) { // 把inputStack的全部元素倒入outputStack顺序正好反转 while (!inputStack.isEmpty()) { outputStack.push(inputStack.pop()); } } if (outputStack.isEmpty()) { throw new IllegalStateException(队列为空); } return outputStack.pop(); } }理解这个实现的关键栈是后进先出但把元素从一个栈倒到另一个栈顺序就反过来了。倒完一次之后outputStack的栈顶就是最先入队的元素。这里有个性能优化点出队时不是每次都要倒数据只有outputStack为空时才从inputStack批量搬运。所以均摊时间复杂度是O(1)每个元素最多被压入两个栈各一次、弹出两个栈各一次总操作次数是常数上界。3.2 用两个队列实现栈这个思路也很有意思。两个队列交替使用始终保持一个队列有元素另一个用来辅助“倒腾”。public class TwoQueueStackT { private QueueT queue1 new LinkedList(); private QueueT queue2 new LinkedList(); public void push(T item) { // 将新元素放入空队列再把另一个队列的元素全部移过来 if (queue1.isEmpty()) { queue1.offer(item); while (!queue2.isEmpty()) { queue1.offer(queue2.poll()); } } else { queue2.offer(item); while (!queue1.isEmpty()) { queue2.offer(queue1.poll()); } } } public T pop() { if (!queue1.isEmpty()) { return queue1.poll(); } return queue2.poll(); } }核心思路每次push都把新元素放到已经清空的辅助队列中然后让另一个队列里的所有元素依次出队并入队到辅助队列这样新元素始终在队尾也就成了栈顶。这个方法的push操作是O(n)pop是O(1)。3.3 滑动窗口最大值的单调队列解法这是单调队列的经典应用。所谓单调队列就是队列中的元素保持单调递增或递减的顺序。求滑动窗口最大值时维护一个递减序列队头就是当前窗口的最大值。public int[] maxSlidingWindow(int[] nums, int k) { if (nums null || nums.length 0) return new int[0]; int[] res new int[nums.length - k 1]; DequeInteger deque new ArrayDeque(); // 存储下标 for (int i 0; i nums.length; i) { // 移除超出窗口范围的队头元素 while (!deque.isEmpty() deque.peekFirst() i - k 1) { deque.pollFirst(); } // 保持队列递减移除所有比当前元素小的队尾元素 while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); } deque.offerLast(i); // 从第k-1个位置开始记录结果 if (i k - 1) { res[i - k 1] nums[deque.peekFirst()]; } } return res; }这个算法的精妙之处在于每个元素最多入队一次、出队一次所以总时间复杂度是O(n)空间复杂度O(k)。如果你用暴力解法每次窗口都要遍历k个元素总复杂度O(n*k)数据量一大就非常慢。3.4 最小栈如何在O(1)时间内获取最小值面试中的另一道高频题。设计一个栈除了常规操作外还能在O(1)时间内返回栈中的最小值。思路是维护两个栈数据栈和最小栈。最小栈的栈顶始终保存当前数据栈中的最小值。public class MinStack { private DequeInteger dataStack new ArrayDeque(); private DequeInteger minStack new ArrayDeque(); public void push(int val) { dataStack.push(val); // 如果新元素比当前最小值小或相等同步压入minStack if (minStack.isEmpty() || val minStack.peek()) { minStack.push(val); } } public void pop() { int val dataStack.pop(); // 如果弹出的元素就是当前最小值minStack也要弹出 if (val minStack.peek()) { minStack.pop(); } } public int top() { return dataStack.peek(); } public int getMin() { return minStack.peek(); } }注意一个细节push时条件是val minStack.peek()等号不能去掉。因为如果压入两个相等的值pop掉一个后另一个还应该作为最小值存在。没有等号的话minStack只保存一份相等值pop掉之后最小值就错乱了。4. 到底什么时候用栈什么时候用队列很多人学完理论基础后遇到实际问题还是不知道选哪个。这不是因为笨而是因为缺少了“需求到结构”的映射训练。我的经验是从三个角度来判断第一个角度顺序要求。如果后产生的数据需要先被处理用栈。比如撤销操作后做的操作最先被撤销再比如递归回溯后进入的递归先返回。如果你处理的任务需要保持产生顺序不变先来的先处理用队列。最典型的就是消息队列谁先发谁先被消费。第二个角度操作的端点数量。只在一端操作选栈。在两端操作头部插入尾部删除或头部删除尾部插入选队列。如果两端都可能插入删除选双端队列Deque。第三个角度是否需要优先级干预。如果任务本身有优先级区分比如黄金会员的请求优先处理普通队列做不到要用优先队列。这里顺便聊聊Java集合框架里的命名陷阱。Java的Stack类从JDK 1.0就有但它继承自Vector所有方法都加了synchronized性能有损耗而且它的行为设计不符合现代Java集合的规范化接口。官方文档以及实际项目里都建议用ArrayDeque代替// 不要这样写 StackInteger stack new Stack(); // 推荐这样写 DequeInteger stack new ArrayDeque(); // 不要用LinkedList当栈虽然它也有push/pop但LinkedList的节点开销更大 DequeInteger stack new LinkedList();同样用LinkedList当普通队列是常见的做法但如果对性能要求比较高ArrayDeque比LinkedList更合适因为它底层是循环数组用数组实现队列没有链表的节点对象开销在缓存局部性上也更好。唯一的问题是ArrayDeque不能装null元素因为它用null作为判断空位的标记。5. 源码里的栈和队列看看JDK是怎么做的5.1 Stack为何被官方“嫌弃”JDK的Stack类确实存在很大的设计问题。它继承了Vector所以它拥有很多栈不该有的方法比如add(int index, E element)可以在任意位置插入元素、get(int index)可以随机访问任意位置的元素——这些操作彻底破坏栈的“只能访问栈顶”特性。更糟糕的是Vector的所有方法都是synchronized的单线程环境下白白多一道锁开销。所以Java官方在Deque接口的文档中明确建议优先使用ArrayDeque而不是Stack。5.2 ArrayDeque的设计亮点ArrayDeque的底层是一个循环数组它用两个指针head和tail表示队头和队尾。扩容时直接翻倍。它的push/pop/addFirst/removeFirst等操作都在数组头部通过指针前移实现不需要移动元素。// ArrayDeque中关键的addFirst实现略简化 public void addFirst(E e) { if (e null) throw new NullPointerException(); elements[head (head - 1) (elements.length - 1)] e; if (head tail) doubleCapacity(); }注意(head - 1) (elements.length - 1)这个位运算。因为数组长度始终是2的幂所以取模操作可以优化成位与操作效率比%高得多。这是JDK源码中常见的性能优化技巧。5.3 LinkedList作为Deque的问题LinkedList也实现了Deque接口但它内部是双向链表。每次push/pop都要创建新的节点对象节点还要维护prev和next两个引用。在大量的入栈出栈操作中对象创建和垃圾回收的开销很大。所以虽然它能用但不是最优解。6. 实战中的拦路虎常见问题与排查实录6.1 用栈实现括号匹配时字符串里有其他字符怎么办很多初版实现只处理括号字符遇到字母、数字、运算符就直接跳过。这样做是可以的。但如果题目要求校验“所有成对符号”比如引号、尖括号就需要扩展映射表。关键要理解栈里存的应该是左括号遇到右括号时去和栈顶的左括号比对比对失败直接返回false。6.2 循环队列的队空队满判断错乱这是最常见的问题。如果你不维护size用head tail判断空用(tail 1) % capacity head判断满那么队列的容量实际上只有capacity-1。很多人在写代码时忘记这个“牺牲一个位置”的设计导致入队时覆盖了未出队的元素数据被静默破坏。排查建议先把size版本实现好确认逻辑再考虑是否优化成不存size的精简版本。6.3 用LinkedList当队列遍历时死循环如果你用LinkedList的get(int index)或者迭代器遍历队列一切正常。但如果你自己实现链表队列遍历时没有保存next节点就先更新了当前节点引用就会死循环。排查方法打印每轮遍历的节点哈希值观察是否有重复。6.4 优先队列里的元素排序错乱优先队列堆只能保证堆顶是优先级最高/最低的元素它不保证全局有序。你想按顺序取出所有元素时必须重复poll。如果你试图通过迭代器直接有序遍历结果是乱序的。这是很多人的认知误区。6.5 栈深度过大导致StackOverflowError这不一定是你代码写错了而可能是递归深度太大。例如递归处理一个超长链表或深度优先搜索DFS递归实现时递归层数过深。排查方向有两个一是把递归改成显式栈迭代二是检查基础条件是否有遗漏导致无限递归。7. 实战总结我见过太多人在纸上写栈和队列的代码很流畅一到了解“为什么循环队列要浪费一个空间”“为什么ArrayDeque比Stack好用”就答不上来。根本原因是只背了结论没理解设计背后的权衡。我自己带人的时候经常给他们三个练习建议练习一用数组和链表各实现一遍栈和队列然后跑一遍性能对比测试。你会发现数据量小的时候差别不大但到百万级操作时数组版本的性能优势非常明显。这能帮助你建立“结构选择影响性能”的直觉。练习二把题目“用两个栈实现队列”和“用两个队列实现栈”都写一遍并分析时间复杂度的均摊情况。这两道题几乎是面试必考而且写完之后你对栈和队列特性的理解会完全不同。练习三找几道单调栈和单调队列的题目做一做。比如“柱状图中最大的矩形”“滑动窗口最大值”。这些题表面上没有“栈”和“队列”字样但解法本质就是在用这两个结构维护候选答案区间是数据结构应用的最佳训练。最后再分享一个我踩过的坑用ArrayDeque时如果你需要存入null代码会直接抛NullPointerException。我当时在做一个缓存系统从数据库查出的结果可能为null存进队列时瞬间就崩了。排查了半天才发现是这个原因。所以选型之前先确认你的数据流里会不会出现null。如果会要么换LinkedList要么用特殊占位对象代替null。栈和队列确实简单但越是简单的东西越能考验你是否真的理解“为什么”。把这两个结构的原理、实现、应用和坑全部打通你在数据结构的路上就算是真正入了门。