读完这篇，你能做什么
能根据访问方向选择结构，并解释链表定位和队列完成顺序的限制。
学习理由、准备要求与知识点
为什么学它
数组、链表、栈与队列是遍历、调度和搜索算法反复使用的基本结构。
先读这些内容
知识点清单
- 数组按下标定位
- 动态扩容与移动
- 链表节点和后继
- 定位与局部修改成本
- 栈后进先出
- 队列先进先出
ArrayDeque方法与空值- 容量和并发规则
运行前先确认Java 17；源码在本机 Microsoft OpenJDK 17.0.20.1 src.zip 核验，在线链接为上游 jdk-17.0.20-ga。深入模块可在掌握基础后回读。
01先弄懂它是什么
选数据结构时，先分清两个问题：数据怎样存，以及先取出哪一项。数组和链表回答怎样存；栈要求最后放入的先取出，队列要求最早放入的先取出。栈和队列都能用数组或链表实现，所以 ArrayDeque 可以承担这两种用途，不需要把它们当成四个互不相干的类别。
数组可以按下标直接找到第 i 项，但在中间插入通常要移动后面的元素。链表把节点一个接一个连起来，找第 i 项通常要一路走过去；已经拿到所需节点或迭代位置时，修改少量连接才比较便宜。双向链表还记录前一个节点，方便反向访问和部分删除操作，代价是每个节点占用更多空间。
Java17 常用 ArrayDeque 表达栈或双端队列：push、pop 在同一端操作，addLast、removeFirst 表达队尾加入、队首移除。它拒绝 null，空时抛异常的方法和返回特殊值的方法需要区分。旧 Stack 类仍存在，但新代码通常可使用 Deque 接口，让操作语义更明确；普通 ArrayDeque 不支持无同步的并发修改。
文中这几个词，先认一认
- 后进先出
- 最后放进去的先拿出来，例如撤销最近一次操作。
- 先进先出
- 最早放进去且还没取出的先拿出来，例如按到达顺序处理任务。
- 环形缓冲
- 数组用到末尾后再从开头利用空位，靠下标循环来复用空间。
- 链节点
- 一个保存数据和相邻节点引用的小对象，多个节点相连组成链表。
02看看它怎么工作
线性数组队列如果每次从头删除都搬运所有剩余项，会付出线性成本。环形缓冲用 head 和 tail 记录逻辑起止位置，消费后只移动指针；到数组末尾时回到零位置。满与空可能出现相同索引关系，需要额外 size、空槽策略或其它约定区分，不能只比较两个数字就猜状态。
链表插入时可能少搬数据，却要为节点分配空间，并沿着引用找下一个节点。相邻节点也未必放在相邻内存中，因此处理器已经取到的那一小片数据不一定能继续派上用场，这与缓存局部性有关。比较花费时，要把找位置、创建节点和改变连接一起算。若主要是顺序读取、在末尾追加，动态数组通常已经够用；只有确实需要某些链接操作时，再评估链表的优势。
两个栈也能组合出队列。输入栈接收新元素，输出栈负责移除最早元素；输出栈为空时，把输入栈全部倒过去，反转顺序后最早元素位于输出栈顶。关键是只有输出为空才转移，否则新元素会插到旧待处理元素前面，破坏先进先出。
正在加载流程图…
查看流程图源码（Mermaid）
flowchart LR
A["新元素"] --> B["输入栈：新元素在顶"]
B -->|"仅输出栈为空时全部倒转"| C["输出栈：最早元素在顶"]
C --> D["移除队首"]
E["仍有输出元素时"] --> F["新元素继续留在输入栈"]
F --> B按顺序看，每一步做了什么
- 先确定栈、队列或双端行为。
- 再选择数组或链节点存储。
- 定义空、满和
null的处理方式。 - 分析定位与修改的总成本。
- 用交错入队出队检验顺序不变量。
03对照实现代码
Microsoft OpenJDK 17.0.20.1；java.base/java/util/ArrayDeque.java · java.util.ArrayDeque#addLast(Object)
以下为原创 Java 17 教学实现，不是原样 JDK 源码；只保留文中明确讨论的机制，省略优化、兼容及内部接口。
import java.util.NoSuchElementException;
public final class SourceModel {
private final int[] data;
private int head, tail, size;
public SourceModel(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException("capacity");
data = new int[capacity];
}
public void addLast(int value) {
if (size == data.length) throw new IllegalStateException("full");
data[tail] = value;
tail = tail + 1 == data.length ? 0 : tail + 1; // 回到数组开头。
size++;
}
public int removeFirst() {
if (size == 0) throw new NoSuchElementException();
int value = data[head];
head = head + 1 == data.length ? 0 : head + 1;
size--;
return value;
}
}真实 ArrayDeque.addLast 首先拒绝 null，把元素写到尾部并移动尾指针；尾指针追上头部时调用增长逻辑。模型是固定容量 int 队列，用额外 size 区分满与空，满时拒绝而不扩容。它只展示环形索引与队列行为，不模拟 JDK 的对象槽位、空槽标记和动态增长。
逻辑顺序与物理下标不必一致。队首可能在数组中间，后面的元素跨越数组末尾再从零继续；因此遍历应依据逻辑数量和回绕规则，不能简单从零扫描到 tail。环形设计复用已消费空间，而不是要求每次删除都把数组内容整体向前搬。
对象队列移除元素时还应清理不再使用的槽位，避免继续持有对象引用而延长其生命周期。模型存 int，没有对象引用保留问题；不能把这一省略推广到 Object 数组实现。存储类型改变后，正确性之外的资源行为也会改变。
JDK 的扩容方式可能随版本调整，调用方更应依赖公开说明。ArrayDeque 不是有界阻塞队列，不能指望它满了就等待消费者。需要限制积压、让生产者等一等时，应选相应并发队列或另加容量控制。名字带 Queue，只说明队列用途，不自动保证等待、线程安全或公平。
代码先调用谁，再调用谁
addLast拒绝null- 写入当前尾槽位
- 尾索引环形推进
- 若追上头部则增长容量并调整布局
04动手写一个例子
只用两个栈实现整数先进先出队列
实现 offer、remove 和 size，保持 FIFO。remove 在空队列抛 NoSuchElementException；允许重复和任意 int 值。两个内部栈均为 ArrayDeque，所有操作按单线程模型执行。
- 输入 1
offer1,offer2,remove,offer3,remove,remove- 输出 1
1,2,3
- 输入 2
空队列remove- 输出 2
抛 NoSuchElementException
- 输入 3
offer0,offer0- 输出 3
size为2
输入栈按到达顺序压入，因此顶部是最新项，底部是最早项。输出栈为空时逐项弹出输入并压入输出，会把整段次序翻转，使最早项位于输出顶部。之后连续移除只需弹输出栈，不必反复搬运。
输出栈尚有元素时，新到元素只能进入输入栈并等待。输出栈中的全部元素都比输入栈中的元素更早到达；若此时提前把输入倒入输出，新元素会盖住旧元素，队列顺序立刻被破坏。交错操作测试比一次性全部入队后全部出队更能发现这个错误。
单次 remove 可能搬运 n 项，因此最坏线性；但每个元素只会被压入输入一次、从输入弹出一次、压入输出一次、最终弹出一次。对任意一串操作，总栈动作与操作数同阶，得到摊还常数成本。这个证明关注元素一生的移动次数，而非假设所有输入随机均匀。
为什么这样写是对的队列逻辑顺序等于输出栈从顶到底的序列，接上输入栈从底到顶的序列。
每个元素最多经历四次栈操作，整个序列总成本线性；底层 ArrayDeque 自身扩容也按摊还成本计入，不保证每次调用延迟相同。
保存为 Main.java，运行 javac --release 17 -encoding UTF-8 Main.java，再运行 java Main。程序包含固定输入自测，断言失败时会抛出错误。
展开收起代码 · Main.java · 完整可运行程序
长行可在代码区域内左右滚动，按 Tab 可把焦点移入代码区。
import java.util.ArrayDeque;
import java.util.NoSuchElementException;
public class Main {
static final class TwoStackQueue {
private final ArrayDeque<Integer> input = new ArrayDeque<>();
private final ArrayDeque<Integer> output = new ArrayDeque<>();
void offer(int value) { input.push(value); }
int size() { return input.size() + output.size(); }
int remove() {
// 只有输出为空才能倒转，避免新元素挡在旧元素之前。
if (output.isEmpty())
while (!input.isEmpty()) output.push(input.pop());
if (output.isEmpty()) throw new NoSuchElementException();
return output.pop();
}
}
static void require(boolean condition) {
if (!condition) throw new AssertionError();
}
public static void main(String[] args) {
TwoStackQueue q = new TwoStackQueue();
q.offer(1); q.offer(2);
require(q.remove() == 1);
q.offer(3); // 交错加入时输出栈仍有旧元素。
require(q.remove() == 2 && q.remove() == 3 && q.size() == 0);
boolean emptyRejected = false;
try { q.remove(); } catch (NoSuchElementException e) { emptyRejected = true; }
require(emptyRejected);
q.offer(0); q.offer(0);
require(q.size() == 2 && q.remove() == 0 && q.remove() == 0);
q.offer(Integer.MIN_VALUE); q.offer(Integer.MAX_VALUE);
require(q.remove() == Integer.MIN_VALUE && q.remove() == Integer.MAX_VALUE);
// 较长序列验证每个元素恰好返回一次且顺序一致。
for (int i = 0; i < 1000; i++) q.offer(i);
for (int i = 0; i < 1000; i++) require(q.remove() == i);
require(q.size() == 0);
System.out.println("PASS 6");
}
}这些特殊情况也要试一试
- 空队列 remove 抛异常。
- 重复值仍是不同队列项。
- 全部
int值合法，不用数值哨兵表示空。 - 输出尚未耗尽时的新入队保持在输入栈。
进阶选读 · 可选深入：有界生产者消费者队列
场景生产速度可能持续超过消费速度，不能无限增长。
做法明确容量上限、阻塞或拒绝策略、取消和超时；使用成熟并发队列，把元素可见性与复合条件交给经过定义的同步协议。
复杂度入出队成本与实现相关，等待时间取决于负载而非单纯 n。
好处与代价背压保护资源但会把等待或拒绝传回生产者，需要业务明确可接受行为。
05项目里怎么用
设计任务队列时，先问最多能排多少项、每秒能处理多少项。没有容量上限的队列，会把“忙不过来”变成越来越长的等待和越来越多的内存占用。即使平均每秒完成的任务数没变，排在后面的少数任务仍可能等很久，这就是需要关注的尾部延迟。一起观察队列长度、等待时间和被拒绝的任务数，比只看有几个消费线程更有用。
双栈队列是理解摊还分析的教学结构，实际 Java 单线程队列通常直接使用 ArrayDeque 更简洁。需要并发时不能在外面零散加几个 synchronized 就宣称完成，size 检查、等待条件与入出队操作之间也可能有竞态，应依据成熟接口契约选择实现。
链表若把节点直接交给外部，调用者可能把前后连接改坏；删除后的节点再次使用，还可能出现错误连接或重复插入。数组则要检查下标、循环回绕，以及删除后是否仍保留对象引用。无论选哪一种，都要约定谁能修改、哪些关系必须保持正确，不能只看到某一步理论上是 O(1) 就忽略维护工作。
容易踩的坑
- 把栈队列与数组链表当成同一层次分类。
- 链表按下标操作时漏算定位成本。
- 环形队列只比较 head与tail，未定义满空区分。
- 输出栈未空就转移输入，破坏 FIFO。
几种做法，怎么选
表格有四列，窄屏可左右滑动查看代价和适用条件。
| 方案 | 优势 | 代价与限制 | 适用条件 |
|---|---|---|---|
| 动态数组实现 | 布局紧凑、索引与尾部操作方便 | 增长或中间移动可能有尖峰 | 通用顺序容器与双端队列 |
| 链式节点实现 | 已知位置时链接修改直接 | 节点开销与定位成本较高 | 需要特定节点操作的结构 |
| 有界并发队列 | 提供容量和线程协调契约 | 阻塞、拒绝与调度成本需要处理 | 生产者消费者与任务分发 |
06检验是否读懂了
先自己想、自己写，再展开答案核对。场景题是假设的练习情境；遇到还没学过的内容，可以做完基础后再回来。
先用自己的话解释
01栈能否用数组实现？
展开参考答案与推导
可以。栈规定后进先出，数组是存储方式，用长度或栈顶下标即可在尾部压入弹出。链表也能实现相同行为，因此抽象接口与具体存储应分开讨论。
02双栈队列为什么摊还常数？
展开参考答案与推导
每个元素只从输入栈转到输出栈一次，整个生命周期只有固定次数压入弹出。某次移除可能集中搬运很多项，但总动作不会随每次操作反复重复全部元素。
03为什么不能用某个 int 值表示空队列？
展开参考答案与推导
所有 int 都可能是合法数据，包括最小值和零。应使用异常、可选结果或独立状态表达空，避免数据与控制标记混淆；接口必须告诉调用者采用哪种方式。
换个情况，还会处理吗
01交错操作输出变成1,3,2，哪里可能错？
展开参考答案与推导
可能在输出栈仍含二时把新输入三倒到输出顶部。只有输出为空才能整体转移，保持输出中的旧元素先于输入中的新元素；用交错序列固定这个不变量。
02队列越积越长，换链表能解决吗？
展开参考答案与推导
不能从根本解决生产超过消费的问题。需要容量、背压、拒绝或扩展消费能力策略；换存储结构最多改变常数和分配行为，不能消除无限积压。
03删除对象后内存仍未释放，数组队列可能漏什么？
展开参考答案与推导
检查被移除槽位是否仍保存对象引用。移动 head 只改变逻辑范围，不自动清空数组内容；应在正确位置置 null，避免容器继续保持对象可达。
写代码试一试
01增加 peek 操作
- 输入 / 条件
队列[1,2]- 输出 / 预期
返回1且size不变
提示 复用按需转移。
展开参考答案与推导
先在输出为空时转移输入，再返回 output.peek 或按约定抛异常。不要弹出元素，测试连续两次 peek 与后续 remove 都看到一，确认只观察不消费。
02实现固定容量拒绝策略
- 输入 / 条件
容量2，连续offer1,2,3- 输出 / 预期
第三次拒绝
提示 检查逻辑总大小。
展开参考答案与推导
在 offer 前依据 size 与容量决定抛异常或返回 false，并明确接口。单线程下检查与写入可直接相邻；并发版本必须保证它们作为一个受控操作完成。
03验证重复值不会去重
- 输入 / 条件
offer7,offer7,remove,remove- 输出 / 预期
7,7
提示 队列保存事件位置而非集合成员。
展开参考答案与推导
加入两次相同值并断言两次都能取到。若使用 Set 代替某个内部结构会丢失重复项，说明数据结构选择必须保持抽象语义，而不只追求某个操作方便。
读完之后，独立完成
课后作业：自己做一遍
本篇共 10 道作业，先完成 8 道基础与综合任务，再按前置知识挑战进阶题。其中包含 1 道思维拓展，试着换个条件，看看原来的办法是否还管用。不附参考答案。
能根据访问方向选择结构，并解释链表定位和队列完成顺序的限制。
本篇重点加练
重点加练定位成本与容量政策，避免只比较插入删除语句而遗漏整体操作。
- 定位与局部修改成本
- 容量和并发规则
重点内容会多练几次。先说清楚怎么做，再试试空数据、出错或条件改变时会发生什么。
先自己做，卡住时记下问题，再回来查。问答题写清“为什么、什么时候适用”；动手题留下输入、输出和运行步骤，方便下次重做。
基础必做
- 作业 01原理问答
动态数组初始容量 2，连续追加 7 个元素，再在首部插入一项。自定并声明扩容政策，逐步列出定位、搬移与分配成本。
- 提交内容
- 容量变化图与操作计数。
- 怎样算完成
- 容量和有效长度分开
- 追加与中间插入成本区分
练到的知识点数组按下标定位 · 动态扩容与移动
- 作业 02代码推演
单链表 A→B→C→D，分别给定头引用与直接持有 C 节点引用，比较删除或插入某位置需要读取的引用；对首节点与尾节点分别推演。
- 提交内容
- 节点图和逐步操作表。
- 怎样算完成
- 定位与局部链接操作分开
- 首尾边界完整
练到的知识点链表节点和后继 · 定位与局部修改成本
综合应用
- 作业 03编程实践
用
ArrayDeque分别实现撤销栈与待办队列，输入操作序列包含 push/add、peek、remove 和清空；自行规定空结构和null输入政策。- 提交内容
- Java 实现、自写交错/空结构/重复值测试及运行证据。
- 怎样算完成
- 分别规定先进先出与后进先出的操作行为
- 空状态不与合法数据混淆
练到的知识点栈后进先出 · 队列先进先出 · ArrayDeque 方法与空值
- 作业 04面试场景
日志队列生产速度长期高于消费速度，开发者提议换
LinkedList。定义容量、拒绝或等待政策以及共享访问约束，说明需采集哪些指标。- 提交内容
- 队列合同、负载时间线和指标表。
- 怎样算完成
- 容量问题与容器实现分开
- 并发责任明确
练到的知识点容量和并发规则
- 作业 05编程实践
实现容量为 4 的整数环形队列，支持 offer、poll、peek，允许所有
int值；测试多次绕回、队满、队空和交错操作。- 提交内容
- Java 实现、自写状态序列及参考队列对照测试、运行证据。
- 怎样算完成
- 索引和有效数量一致
- 失败操作不破坏已有内容
- 内存容量固定
练到的知识点数组按下标定位 · 动态扩容与移动 · 队列先进先出 · 容量和并发规则
- 作业 06编程实践
实现容量上限为 5 的最近访问列表，访问已有编号要按合同移动位置，新编号到来可能淘汰；记录查找与修改各自操作量。
- 提交内容
- Java 实现、自写满容量/重复/空输入测试与运行证据。
- 怎样算完成
- 定位和改动成本分开记录
- 容量与顺序合同同时检验
练到的知识点定位与局部修改成本 · 容量和并发规则
- 作业 07设计评审
编辑器需要按行号删除与持有节点后插入两种操作。比较数组与链表在两种入口的完整成本，不把已持有节点当作所有请求的前提。
- 提交内容
- 入口条件和成本矩阵。
- 怎样算完成
- 查找前提明确
- 结构选择与工作负载相符
练到的知识点定位与局部修改成本
- 作业 08面试场景
任务队列满时可拒绝新任务、丢弃旧任务或让调用者等待。为个人通知与账务任务分别制定政策和可观察反馈。
- 提交内容
- 两种业务的容量合同。
- 怎样算完成
- 丢弃和等待后果被纳入需求
- 失败不会被静默当成成功
练到的知识点容量和并发规则
进阶挑战 · 掌握前置后选做
- 作业 09设计评审
完成并发基础后：工作队列支持取消尚未开始任务。比较数组队列、链表和附加索引方案，定义取消与取出同时发生时的合同。
- 提交内容
- 操作复杂度表与竞态验收场景。
- 怎样算完成
- 查找取消成本纳入分析
- 任务身份与执行状态可追踪
练到的知识点定位与局部修改成本 · 栈后进先出 · 队列先进先出 · 容量和并发规则
思维拓展
先写出你的猜想，再用例子或实验验证。答案可以不同，但要说清依据、适用情况，以及还有什么没弄懂。
- 作业 10思维拓展 · 条件变化
最近访问列表增加“随时删除任意编号”，同时要求严格内存上限。评估是否需要辅助索引，比较删除定位成本与额外空间。
- 提交内容
- 数据结构候选、资源账本和验收样本。
- 怎样算完成
- 额外索引维护成本被计算
- 容量规则覆盖全部内部结构
练到的知识点定位与局部修改成本 · 容量和并发规则
完成后，再检验一次
给每题标记“独立完成 / 查阅后完成 / 尚未完成”。查过资料或没做出的题，记下卡在哪里。隔一天换一组输入再试，能解释结果和出错原因，再把这个知识点标为掌握。
继续阅读
先看能帮你完成当前练习的部分。例子跑通后，再读更深入的解释。
- 必读教程英文
Harvard CS50：数据结构 （新标签页）↗
阅读数组、链表、栈队列、树与哈希表；C 指针示例只用于理解结构，练习以 Java 17 改写。
- 实践参考文档英文
Java 17 API：ArrayDeque （新标签页）↗
比较栈和队列方向的 offer
/poll/push/pop，并了解空值限制。 - 深入参考文档英文
Java 17 API：Arrays （新标签页）↗
查阅
copyOf、equals、sort、binarySearch和asList的具体契约。 - 实践实践指南中文
Hello 算法：用图和 Java 理解数组、链表与查找 （新标签页）↗
先读第 2 章和第 4—6 章，再读二分查找。小练习：在五个数字的数组中插入一个数，先画出移动过程，再用 Java 实现；说明容量不够时怎么办。 正文和代码公开，部分可视化依赖外部工具。教材支持多种语言，建议先固定 Java 学习。
- 深入参考文档英文
OpenJDK 17u java.util.ArrayDeque （新标签页）↗
定位
ArrayDeque.addLast的null禁止、环形尾索引与增长触发，区分模型的固定容量策略。 - 深入参考文档英文
Princeton 栈与队列 （新标签页）↗
学习数组和链式实现，以及摊还增长分析。