Java教程

Java集合中的Queue & Deque

本文主要是介绍Java集合中的Queue & Deque,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Queue 是一端进另一端出的线性数据结构;而 Deque 是两端都可以进出的。

Queue

Java 中的 这个 Queue 接口稍微有点坑,一般来说队列的语义都是先进先出(FIFO)的。

但是这里有个例外,就是 PriorityQueue,也叫 heap,并不按照进去的时间顺序出来,而是按照规定的优先级出去,并且它的操作并不是 O(1) 的,时间复杂度的计算稍微有点复杂,我们之后单独开一篇来讲。

那 Queue 的方法官网[1]都总结好了,它有两组 API,基本功能是一样的,但是呢:

  • 一组是会抛异常的;
  • 另一组会返回一个特殊值。
功能抛异常返回值
add(e) offer(e)
remove() poll()
element() peek()

为什么会抛异常呢?

  • 比如队列空了,那 remove() 就会抛异常,但是 poll() 就返回 null;element() 就会抛异常,而 peek() 就返回 null 就好了。

那 add(e) 怎么会抛异常呢?

有些 Queue 它会有容量的限制,比如 BlockingQueue,那如果已经达到了它最大的容量且不会扩容的,就会抛异常;但如果 offer(e),就会 return false.

那怎么选择呢?:

  • 首先,要用就用同一组 API,前后要统一;

  • 其次,根据需求。如果你需要它抛异常,那就是用抛异常的;不过做算法题时基本不用,所以选那组返回特殊值的就好了。

Deque

Deque 是两端都可以进出的,那自然是有针对 First 端的操作和对 Last 端的操作,那每端都有两组,一组抛异常,一组返回特殊值:

功能抛异常返回值
addFirst(e)/ addLast(e) offerFirst(e)/ offerLast(e)
removeFirst()/ removeLast() pollFirst()/ pollLast()
getFirst()/ getLast() peekFirst()/ peekLast()

使用时同理,要用就用同一组。

Queue 和 Deque 的这些 API 都是 O(1) 的时间复杂度,准确来说是均摊时间复杂度。

实现类

它们的实现类有这三个:

 

 

所以说,

  • 如果想实现「普通队列 - 先进先出」的语义,就使用 LinkedList 或者 ArrayDeque 来实现;
  • 如果想实现「优先队列」的语义,就使用 PriorityQueue;
  • 如果想实现「栈」的语义,就使用 ArrayDeque。

我们一个个来看。

在实现普通队列时,如何选择用 LinkedList 还是 ArrayDeque 呢?

总结来说就是推荐使用 ArrayDeque,因为效率高,而 LinkedList 还会有其他的额外开销(overhead)。

那 ArrayDeque 和 LinkedList 的区别有哪些呢?

  1. ArrayDeque 是一个可扩容的数组,LinkedList 是链表结构;
  2. ArrayDeque 里不可以存 null 值,但是 LinkedList 可以;
  3. ArrayDeque 在操作头尾端的增删操作时更高效,但是 LinkedList 只有在当要移除中间某个元素且已经找到了这个元素后的移除才是 O(1) 的;
  4. ArrayDeque 在内存使用方面更高效。

所以,只要不是必须要存 null 值,就选择 ArrayDeque 吧!

那如果是一个很资深的面试官问你,什么情况下你要选择用 LinkedList 呢?

  • 答:Java 6 以前。。。因为 ArrayDeque 在 Java 6 之后才有的。。

那最后一个问题,就是关于 Stack 了。

Stack

Stack 在语义上是 后进先出(LIFO) 的线性数据结构。

有很多高频面试题都是要用到栈的,比如接水问题,虽然最优解是用双指针,但是用栈是最直观的解法也是需要了解的,之后有机会再专门写吧。

那在 Java 中是怎么实现栈的呢?

虽然 Java 中有 Stack 这个类,但是呢,官方文档都说不让用了!

 

 原因也很简单,因为 Vector 已经过被弃用了,而 Stack 是继承 Vector 的。

那么想实现 Stack 的语义,就用 ArrayDeque 吧:

Deque<Integer> stack = new ArrayDeque<>();

 

参考:https://mp.weixin.qq.com/s/bVOSat47L0Hskfx9akAN6Q

 

这篇关于Java集合中的Queue & Deque的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!