Dx's Tech Notes

Deque 与 Queue

6 min read

queue：poll，offer （peek） deque：pop，push （peek） priorityQueue：poll，offer （peek）

  • 想当栈用（只能操作头）：push / pop

  • 想当队列用（一头进一头出）：offer / poll

  • 想当双端队列用（LinkedList）3.字符串解码（两头随便搞，且需要用的 Collections 的 API，只接受 List 类型）：addFirst / removeLast (显式指定 First/Last)、、、

  • Queue 是老板，制定了“排队”的最基本规则。

  • Deque 是少东家，继承了 Queue，并把规则升级为“双端操作”（可队列、可栈）。

  • LinkedList 是老员工，他既签了 Deque 的合同（能排队），也签了 List 的合同（能存列表）。

    • 因为签了 Deque 合同，所以它自然也有 Queue 的能力（peek, poll 等）。
Iterable (顶层接口)
          ↓
      Collection (总接口)
          ↓
    +-----+----------------+
    ↓                      ↓
  List (接口)            Queue (接口)
    ↓                      ↓
    |                +-----+-----+
    |                ↓           ↓
ArrayList       PriorityQueue  Deque (接口)
(类)                 (类)        ↓
    |                            |
    +-----------+----------------+
                ↓
            LinkedList
              (类)

这是一个非常经典且体现Java 设计哲学的问题！

这句话背后的核心思想叫做 “面向接口编程” (Coding to an Interface)，而不是面向实现编程。

简单来说，就是：“我只关心你是个列表（List），我不关心你底层是用数组（ArrayList）还是链表（LinkedList）实现的。”

下面我用大白话加具体的例子给你讲清楚这三个主要原因：

1. 以后换“零件”特别方便（解耦）

这是最主要的原因。

假设你写了一个巨大的系统，里面到处都用到了这个 list。

场景：

一开始你觉得 ArrayList挺好。结果过了两个月，你发现业务变了，需要频繁地在列表头部插入数据。我们要知道，ArrayList 在头部插入数据非常慢（要搬移后面所有元素），而 LinkedList 在头部插入非常快。

  • 如果你写的是 ArrayList<String> list = ...：

    当你把 new ArrayList<>() 改成 new LinkedList<>() 时，编译器可能会报错，或者你需要把代码里所有定义 ArrayList 的地方全部改成 LinkedList。如果你的代码有几千行，你就疯了。

  • 如果你写的是 List<String> list = ...：

    你只需要改一行代码：

    Java

    // 旧代码
List<String> list = new ArrayList<>();

// 新代码，只改这一处，后面几千行代码完全不用动！
List<String> list = new LinkedList<>();

    为什么？ 因为后面代码调用的 add, get, remove 都是 List 接口里定义好的方法，大家都有，所以无缝切换。

2. 通用性：为了让别人能给你传参

这在写方法（函数）时尤为重要。

假设你要写一个方法，用来打印列表里的所有名字。

写法 A（不好）：限制太死

Java

// 你要求必须传 ArrayList 进来
public void printNames(ArrayList<String> names) {
    for (String name : names) {
        System.out.println(name);
    }
}

后果： 如果有一天，你的同事用了一个 LinkedList，或者 Vector，或者 Java 以后出的新列表类型，他都没法调用你的这个方法！他必须先把他的链表转成 ArrayList 才能传给你，非常麻烦。

写法 B（推荐）：海纳百川

Java

// 你只要求传一个 List 进来，管你是什么 List
public void printNames(List<String> names) {
    // ...
}

好处： ArrayList、LinkedList、Stack、Vector… 只要是实现了 List 接口的，统统都能传给你处理。

3. 隐藏细节（抽象）

生活中的例子：

  • List (接口) 就像是 “USB 插口”。

  • ArrayList (实现) 就像是 “金士顿 64G U盘”。

当你买电脑的时候，你只会问：“这电脑有 USB 口吗？”（即 List）。

你不会问：“这电脑有金士顿 64G U盘专用口吗？”（即 ArrayList）。

因为你只关心能不能存数据，至于这个口插进去的是金士顿、闪迪还是三星，那是细节，不应该把电脑（你的代码逻辑）和某个具体品牌的U盘（ArrayList）焊死在一起。

什么时候必须写 ArrayList list = ...？

虽然很少见，但只有一种情况你需要这么写：

你需要调用 ArrayList 独有的、List 接口里没有的方法时。

比如 ArrayList 有两个特有方法：

  1. ensureCapacity(int minCapacity): 提前扩容。

  2. trimToSize(): 把底层数组的大小修剪到和当前元素数量一样（省内存）。

如果你确实需要手动控制这些内存细节（极度追求性能优化），那你必须声明为 ArrayList，否则无法调用这两个方法。但在 99% 的业务开发中，我们不需要关心这个。

总结

写 List<T> list = new ArrayList<>(); 是为了：

  1. 灵活：随时能换成 LinkedList 而不改动其他代码。

  2. 通用：让你的代码能兼容所有列表类型。

  3. 规范：这是 Java 程序员通用的“行规”（设计模式中的依赖倒置原则）。

Graph View