作为后端开发者我们在日常的业务开发和算法实现中经常会遇到需要使用栈Stack或队列Queue的场景。然而许多开发者在使用Deque时往往只是机械地使用其中的某几个方法却未曾深究过Deque庞大 API 矩阵背后的设计更少有人注意到在将Deque当作 Stack 使用时其push/pop与peek方法在异常处理机制上存在着一个微妙的“不统一”。今天我们就以 JDK 8 为例结合Deque接口的两位核心设计者Doug Lea与Joshua Bloch的设计思路深度解剖Deque接口的底层逻辑。1. 为什么抛弃 Stack在讨论Deque之前我们必须先明确旧的java.util.Stack到底有什么问题。Java 集合框架的核心开发者 Joshua Bloch 在其名作《Effective Java》中将Stack作为一个经典的反面教材进行了严厉批判If you attempt to build a stack by extending a vector, you expose all of the vectors methods... A client could corrupt the stack by directly modifying the underlying vector. 如果你试图通过继承Vector来构建栈你暴露了Vector的所有方法…… 客户端可以直接修改底层向量从而破坏栈的约束。Stack继承自Vector这意味着它不仅继承了极其低效的重量级synchronized锁更致命的是它打破了栈“后进先出LIFO”的封装语义。开发者竟然可以通过stack.add(1, element)或stack.elementAt(2)直接操作栈底的元素这在数据结构的设计上是极其荒谬的。正是基于填补这个历史设计缺陷的目的在 JDK 1.6JSR-166中并发大师 Doug Lea 与 Joshua Bloch 联手设计了全新的java.util.Deque接口。在Deque的官方 JavaDoc 中两位作者明确写下Deques can also be used as LIFO (Last-In-First-Out) stacks. This interface should be used in preference to the legacy Stack class.Deque 也可作为 LIFO 栈使用。应该优先使用此接口而非遗留的 Stack 类。2. Deque 接口的核心设计矩阵Deque全称是 Double Ended Queue双端队列。它的核心特性是允许在队列的两端头部和尾部进行插入和删除操作。为了满足不同场景下的需求Doug Lea与Joshua Bloch为Deque设计了一套高度对称的 API。这套 API 的设计维度有两个操作位置头部First vs 尾部Last失败处理机制抛出异常Throws exception vs 返回特殊值Returns special value通常是null或false这两个维度交叉组合构成了Deque的 12 个基础操作 API一些说明插入操作在容量受限的 Deque如LinkedBlockingDeque中当容量已满时抛出异常系列会抛出IllegalStateException而返回特殊值系列会返回false。删除/查看操作当 Deque 为空时抛出异常系列会抛出NoSuchElementException而返回特殊值系列会返回null。无论是基于数组实现的ArrayDeque还是基于链表实现的LinkedList这 12 个基础操作的时间复杂度均被严格保证为 $O(1)$ 或均摊 $O(1)$。3. Deque 与 Queue、Stack 的角色切换Deque的强大之处在于它能力全面它直接继承自java.util.Queue接口并且在语义上完全覆盖了java.util.Stack。3.1 扮演 Queue (FIFO)当把Deque当作普通队列使用时通常遵循 FIFO先进先出原则。元素从尾部进入从头部移出。Deque直接继承了Queue的 API并在内部将其路由到双端队列的具体方法3.2 扮演 Stack (LIFO)JDK 早期提供的java.util.Stack存在严重的设计缺陷它继承自Vector这意味着它的所有方法都自带了synchronized重量级锁导致并发性能极差此外继承结构破坏了封装性暴露了按索引操作元素的方法这在栈的数据结构语义中是不合法的。因此Deque被官方指定为栈的替代品并专门为此提供了栈的经典 APIpush、pop和peek。在 LIFO后进先出模式下所有的入栈和出栈操作都在同一端通常约定为头部 First进行4. Stack 模式下异常处理的“妥协”如果你仔细观察上面的 API 映射并结合我们在第2节总结的“异常 vs 特殊值”矩阵你会发现一个极其反直觉的现象。当我们把Deque当作栈使用时面临空栈或满栈的情况push(e)等价于addFirst(e)-抛出异常(IllegalStateException)pop()等价于removeFirst()-抛出异常(NoSuchElementException)peek()等价于peekFirst()-返回 null(不抛出异常)为什么push和pop走的是“抛出异常”流派而同为栈操作的peek却悄悄走入了“返回特殊值”流派为什么这里的设计不是统一的比如peek应该映射到getFirst()从而抛出NoSuchElementException要理解这个 API 设计的异常割裂我们需要跳出单点思维站在接口继承体系设计和历史兼容性的角度去剖析。4.1 模拟老旧的 StackDoug Lea 在设计Deque的 Stack 模式 API 时首要目标是降低开发者的迁移成本。老旧的java.util.Stack的行为是怎样的Stack.push(e)容量不足时自动扩容Vector 机制但在某些极端底层受限情况下会抛出异常。Stack.pop()当栈为空时抛出EmptyStackException。为了与老用户的习惯保持一致Deque.pop()必须在空栈时抛出异常NoSuchElementException充当了替代品。因此pop()被映射到了removeFirst()同理push()映射到了addFirst()。4.2 接口的里氏替换原则既然老旧的Stack.peek()在空栈时也会抛出EmptyStackException那为什么Deque.peek()不抛出异常呢根本原因在于方法名冲突与接口继承的契约限制。看一眼 JDK 源码的类继承图public interface DequeE extends QueueE { // ... }Deque继承自Queue。而在Queue接口中早就已经定义了peek()方法public interface QueueE extends CollectionE { /** * Retrieves, but does not remove, the head of this queue, * or returns null if this queue is empty. */ E peek(); }Queue接口的契约清楚地写着peek()方法在队列为空时必须返回 null绝不能抛出异常。根据面向对象设计的里氏替换原则Liskov Substitution Principle子接口Deque不能改变父接口Queue已声明的方法的语义契约。如果Deque强行覆盖peek()让其在为空时抛出异常那么所有将Deque向上转型为Queue进行操作的多态代码将会面临不可预期的行为。4.3 设计权衡留给 JDK 设计者的路只有两条换个名字为栈操作专门发明一个新的查看栈顶的方法比如叫peekStack()或top()并让它映射到getFirst()抛异常。妥协复用直接复用继承自Queue的peek()方法名忍受它“返回 null”的语义从而破坏栈操作 APIpush/pop/peek在异常处理上的一致性。最终为了保持核心 API 方法名的高度认知一致性开发者对 push、pop、peek 已经有了多年的肌肉记忆设计者选择了妥协复用。这就是为什么在Deque中push和pop会抛出异常而peek却返回null的原因。这也是 Java API 演进过程中为了平衡“向下兼容”、“接口多继承隔离”和“开发者习惯”而留下的一个经典的微小设计瑕疵。5. 总结与建议通过追踪 Doug Lea 与 Joshua Bloch 的设计轨迹我们不难发现即便是 JDK 核心 API 的设计也是在“向下兼容”、“接口隔离”和“开发者习惯”之间不断博弈与取舍的过程。基于以上的分析在日常开发工作中我有以下两条建议供参考如果追求极致的语义一致性请放弃 push/pop/peek与其记住peek和pop异常处理的不同不如彻底抛弃这种“模拟语义”直接使用带有明确方向标识的First/Last组 API。这样可以在 Code Review 阶段消除由于null返回值或NoSuchElementException带来的隐患。需要抛异常的栈统一使用addFirst/removeFirst/getFirst。不抛异常的栈统一使用offerFirst/pollFirst/peekFirst。不要插入 null 值正如 JDK 官方文档所警告的强烈建议不要向Deque中插入null元素尽管LinkedList允许。因为peek()和poll()使用返回null来表示集合为空如果插入了真实的null元素就会导致混乱。源码之下无秘密。探究 API 的设计不仅能帮我们避开使用上的暗坑更能让我们学习到顶级工程师在面对历史包袱与规范约束时是如何做架构取舍的。这种在“理想的面向对象契约”与“现实的历史兼容性”之间寻找平衡的艺术其实正是我们日常进行系统重构和复杂业务迭代时最真实的写照。希望这次分析能让你在下次敲下这些基础 API 时多一份知其所以然的笃定与从容。文章转载自kefate原文链接https://www.cnblogs.com/kefate/p/19642771/java-deque-design体验地址http://www.jnpfsoft.com/?from001YH