企业官网建设流程全解析

栈与队列是数据结构里最基础也最容易被轻视的两个结构。很多初学者觉得它们“不就是个数组加点限制吗”，但实际工作中，从函数调用栈到消息队列，从浏览器的前进后退到操作系统的任务调度，到处都有它们的影子。面试的时候，这两个结构也是最常被拿出来考手写代码的题目。

这篇文章我不打算写成教科书式的枯燥讲义，而是用一篇完整的实战笔记，把栈和队列从原理讲到应用，再讲到源码，最后给出可直接复用的代码实现。不管你是刚学数据结构的新手，还是准备面试的开发者，这篇文章都能给你一个足够清晰完整的视角。

1. 栈：后进先出的世界

1.1 为什么说栈是一种“受限”的线性表

栈的本质是一个线性表，但它只在表尾进行插入和删除操作。这个“表尾”在栈的语境里叫栈顶（top），另一端叫栈底（bottom）。所以栈的所有操作都被限制在一个端点，这就是“受限”的含义。

想象一个叠盘子的场景：你只能从最上面取盘子，也只能把新盘子放到最上面。如果你想要最底下的那个盘子，就得先把上面所有的盘子都移开。这就是后进先出（LIFO，Last In First Out）的直观感受。

栈的核心操作只有五个：

• push(x)：元素入栈，放到栈顶
• pop()：弹出栈顶元素并返回
• peek()：查看栈顶元素但不弹出
• isEmpty()：判断栈是否为空
• size()：返回栈中元素个数

这些操作的共同特点是时间复杂度为O(1)，不管栈里有多少元素，每次操作都只涉及栈顶这一个位置。

1.2 基于数组的栈实现：动态扩容是核心

用数组实现栈是最自然的方式。但直接用固定数组会遇到一个问题：栈满了怎么办？所以实战中我们需要实现一个动态扩容的版本。

来看一段完整的Java实现：

public class ArrayStack<T> { 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 LinkedStack<T> { private Node<T> topNode; private int size; private static class Node<T> { T data; Node<T> next; Node(T data, Node<T> 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) { Deque<Character> stack = new ArrayDeque<>(); Map<Character, 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(); }

场景三：表达式求值

中缀表达式转后缀表达式（逆波兰式），是栈的经典应用。操作符栈用于保存等待处理的运算符，当遇到优先级较低的运算符时，先把栈里高优先级的运算符弹出。

场景四：浏览器前进后退

这其实是两个栈配合使用。当前页面作为分界线：一个栈存“后退”页面，另一个栈存“前进”页面。点后退时，把当前页面压入前进栈，从后退栈弹出页面；点前进时反过来。

场景五：撤销操作

文本编辑器里的Ctrl+Z，每次操作把状态快照（或操作反动作）压入栈，撤销时从栈顶弹出恢复。

2. 队列：先进先出的管道

2.1 队列的本质与核心操作

队列和栈正好相反，它在一端（队尾）插入，在另一端（队头）删除，遵循先进先出（FIFO, First In First Out）原则。

生活中的例子很好找：食堂排队打饭，先到的人先打到饭；打印机任务队列，先提交的任务先打印。

队列的核心操作有：

• enqueue(x)：入队，在队尾添加元素
• dequeue()：出队，移除队头元素并返回
• front()：查看队头元素
• isEmpty()：判断队列是否为空
• size()：获取队列长度

2.2 数组队列的致命问题：假溢出

如果直接用数组头尾两个指针实现队列，会出现一个严重问题。随着元素的入队和出队，尾部指针不断后移，当尾部指针到达数组末尾时，即便数组前面有空闲位置，也无法再入队了。这就是“假溢出”。

解决假溢出的方案是循环队列：把数组看成一个首尾相接的环，当tail到达数组末尾时，如果头部位置有空间，就绕回到数组开头继续插入。

public class CircularQueue<T> { 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 LinkedQueue<T> { private Node<T> head; private Node<T> tail; private int size; private static class Node<T> { T data; Node<T> next; Node(T data) { this.data = data; } } public void enqueue(T item) { Node<T> 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 TwoStackQueue<T> { private Deque<T> inputStack = new ArrayDeque<>(); private Deque<T> 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 TwoQueueStack<T> { private Queue<T> queue1 = new LinkedList<>(); private Queue<T> 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]; Deque<Integer> 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 Deque<Integer> dataStack = new ArrayDeque<>(); private Deque<Integer> 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代替：

// 不要这样写 Stack<Integer> stack = new Stack<>(); // 推荐这样写 Deque<Integer> stack = new ArrayDeque<>(); // 不要用LinkedList当栈，虽然它也有push/pop，但LinkedList的节点开销更大 Deque<Integer> 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。

栈和队列确实简单，但越是简单的东西，越能考验你是否真的理解“为什么”。把这两个结构的原理、实现、应用和坑全部打通，你在数据结构的路上就算是真正入了门。