数组和链表是线性结构的两种存储实现，差异不在接口而在内存布局：是否连续决定了随机访问成本与缓存友好度。栈和队列则是在线性结构上叠加访问约束，用 LIFO 与 FIFO 的语义表达处理顺序。吃透这四个结构，分析一切复杂结构就有了起点。

它解决什么问题

程序里的数据很少孤立存在，更多时候是一批同类型元素的集合：一串日志、一组订单、一条调用链。第一个要回答的问题不是”用哪个类”，而是”这批元素在内存里怎么摆”。摆放方式只有两种基本选择——紧挨着连续存放（数组），或者分散存放再用指针串起来（链表）。布局一旦确定，每种操作的成本就被物理规律锁死了。

栈和队列回答的是另一类问题：元素按什么秩序进出。它们不关心底层用什么存，只规定访问端点——栈只暴露栈顶，队列一头进另一头出。约束越强，语义越清晰，能表达的处理模型也越明确：撤销、递归、层级遍历，背后都是这两种进出秩序。

核心原理

数组 vs 链表：差异来自内存布局

数组占据一整块连续内存，第 i 个元素的地址可以直接算出来：基地址 + i × 元素大小。一次加法、一次寻址，这就是 O(1) 随机访问的全部秘密。链表的节点散落在堆中，彼此靠指针相连，想找第 i 个节点只能从头逐个跳过去，O(n) 无法避免。

更深一层的差异是缓存局部性。CPU 读内存按 cache line（通常 64 字节）整块加载进缓存，顺序遍历数组时，后续元素大概率已经在缓存里，硬件预取器还会提前把下一块搬进来。链表节点地址毫无规律，每次解引用都可能触发 cache miss，实际遍历速度往往比复杂度分析暗示的还要慢一个量级。所以即便插入删除更频繁，现代工程里数组也常常跑赢链表。

数组的短板是容量固定、中间插删要整体搬移。动态数组（ArrayList）用倍增扩容缓解：容量耗尽时申请更大空间整体复制，单次搬移 O(n)，均摊到每次追加仍是 O(1)。链表”插入 O(1)”则有严格前提——已经拿到目标位置的前驱节点；若还要先查找定位，整体仍是 O(n)。

栈与队列：约束即语义

栈（Stack）只允许在同一端 push/pop，后进先出（LIFO）。队列（Queue）尾部进、头部出，先进先出（FIFO）。两者的端点操作都是 O(1)，”慢”的部分被刻意藏起来——放弃随机访问，换取语义的确定性。

双端队列与优先级队列

双端队列（Deque）放开两端，addFirst/addLast/removeFirst/removeLast 都是 O(1)，既能当栈又能当队列，还能支撑滑动窗口这类需要在两端裁剪的场景。优先级队列（Priority Queue）则抛弃”按到达顺序出队”的规则，每次取出优先级最高的元素，底层通常用堆实现，入队出队都是 O(log n)，只保证队头最优先，不承诺全局有序。

深入机制

栈：括号匹配

左括号入栈，右括号弹出栈顶比对，失配即失败，扫完栈空则合法：

public boolean isValid(String s) {
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (!pairs.containsKey(c)) {
            stack.push(c);                       // 左括号入栈
        } else if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
            return false;                        // 右括号找不到匹配的左括号
        }
    }
    return stack.isEmpty();
}

栈的进阶：单调栈

在栈里维护一个单调递增或递减的序列，可以 O(n) 回答”每个元素右侧第一个比它大的值”。以每日温度为例：栈中存下标且对应温度单调递减，遇到更高温就持续弹出并记录天数差：

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] answer = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();   // 栈存下标，温度自栈底到栈顶递减
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int prev = stack.pop();
            answer[prev] = i - prev;
        }
        stack.push(i);
    }
    return answer;
}

每个下标最多入栈、出栈各一次，总复杂度 O(n)。单调栈、单调队列的本质相同：靠结构内维持的偏序跳过无效比较。

队列：BFS 的层次遍历

队列的 FIFO 恰好对应”先发现的先处理”，这正是广度优先搜索的定义。入队即标记，出队时把邻居依次入队，就得到按层展开的遍历：

public void bfs(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();            // 先入队的先处理：层层推进
        visit(node);
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

把 Queue 换成栈，同样的骨架立刻变成 DFS——这个对照最能说明两种结构的语义差异。

工程实践

  • Java 里不要再 new Stack：它继承 Vector，方法级 synchronized 带来无谓开销，还暴露了下标访问等破坏栈语义的能力。官方推荐 Deque——栈语义用 ArrayDeque 的 push/pop，队列语义用 offer/poll。
  • ArrayList 与 LinkedList 之争早有定论：除非在迭代器当前位置高频插删，否则一律 ArrayList。LinkedList 的节点对象开销和缓存不友好，让”理论优势”在真实硬件上很难兑现。
  • 队列在工程中的角色远超算法题：线程池的任务队列、消息中间件的缓冲、生产者-消费者解耦、限流的削峰填谷，本质都是”按序缓冲待处理项”。
  • 用数组实现队列务必用环形下标（front/rear 取模回绕），否则出队后头部空间无法复用，出现”假溢出”；环形队列还要约定空与满的判定规则（牺牲一个槽位或单独维护 size）。

对比与权衡

结构 随机访问 头部插删 尾部插删 缓存局部性 什么时候用
动态数组 O(1) O(n) 摊还 O(1) 极好 按下标读多、顺序遍历多、规模可预估
链表 O(n) O(1) O(1)（带尾指针） 差 已知节点位置高频插删、大小极不确定
栈 仅栈顶 — O(1) 取决于底层 括号匹配、撤销、递归消除、DFS、单调栈
队列 仅队头 O(1) 出队 O(1) 入队 取决于底层 BFS、任务排队、削峰缓冲
双端队列 无 O(1) O(1) 好（数组实现） 滑动窗口、同时需要栈和队列语义
优先级队列 仅堆顶 — O(log n) 较好（堆用数组） Top K、任务调度、合并多路有序序列

选型的决策路径：先问”主要操作发生在哪一端”，再问”是否需要随机访问”，最后看”规模是否可预估”。三个问题答完，候选结构通常只剩一个。

面试视角

数组查询 O(1)、链表 O(n) 的根本原因是什么？ 数组连续存储，下标可直接换算成内存地址；链表节点靠指针串联，定位第 i 个节点必须从头跳 i 次。能补上缓存局部性（cache line 预取对数组友好、对链表无效），答案会更有深度。

链表的插入删除真的是 O(1) 吗？ 仅当已持有目标位置的前驱节点。如果把”先找到它”算进去，整体仍是 O(n)。主动点明这个前提，能避免被追问时翻车。

为什么用 Deque 替代 Stack？ Stack 继承自 Vector，每个方法加 synchronized 造成无谓开销，继承结构还暴露了按位访问等破坏栈语义的接口；ArrayDeque 基于循环数组，无锁、缓存友好，两端操作都是 O(1)。

单调栈解决哪类问题？ “下一个更大/更小元素”类问题：每日温度、柱状图最大矩形、接雨水。识别信号是——每个元素的答案取决于它右侧（或左侧）第一个满足某种大小关系的元素。

循环队列如何区分空与满？ front == rear 既可能是空也可能是满。两种常规方案：牺牲一个存储槽，以 (rear + 1) % capacity == front 判满；或者单独维护元素计数。

小结

  • 数组与链表的分野在内存布局：连续带来 O(1) 寻址与缓存友好，分散带来指针级的灵活但失去局部性。
  • 动态数组的追加是摊还 O(1)；链表的 O(1) 插删永远附带”已知位置”这个前提。
  • 栈和队列的价值不在性能而在语义：LIFO 对应回溯与嵌套，FIFO 对应次序与缓冲；Deque 放开两端，优先级队列改为按权重出队。
  • 选型先定主要操作端点，再看随机访问需求与规模可预估性；Java 中默认 ArrayList 与 ArrayDeque，几乎总是对的。