Queue - 队列-数据结构与算法(上)

当前位置:　首页>> 技术小册>> 数据结构与算法(上)

Queue 是一个 FIFO（先进先出）的数据结构，并发中使用较多，可以安全地将对象从一个任务传给另一个任务。

编程实现
Java
Queue 在 Java 中是 Interface, 一种实现是 LinkedList, LinkedList 向上转型为 Queue, Queue 通常不能存储 null 元素，否则与 poll() 等方法的返回值混淆。

```asp
Queue<Integer> q = new LinkedList<Integer>();
int qLen = q.size(); // get queue length
```
Methods

| 0:0     | Throws exception | Returns special value |
|---------|------------------|-----------------------|
| Insert  | add(e)           | offer(e)              |
| Remove  | remove()         | poll()                |
| Examine | element()        | peek()                |

优先考虑右侧方法，右侧元素不存在时返回 null. 判断非空时使用isEmpty()方法，继承自 Collection.

Priority Queue - 优先队列
应用程序常常需要处理带有优先级的业务，优先级最高的业务首先得到服务。因此优先队列这种数据结构应运而生。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。

优先队列可以使用数组或链表实现，从时间和空间复杂度来说，往往用二叉堆来实现。

Java
Java 中提供PriorityQueue类，该类是 Interface Queue 的另外一种实现，和LinkedList的区别主要在于排序行为而不是性能，基于 priority heap 实现，非synchronized，故多线程下应使用PriorityBlockingQueue. 默认为自然序（小根堆），需要其他排序方式可自行实现Comparator接口，选用合适的构造器初始化。使用迭代器遍历时不保证有序，有序访问时需要使用Arrays.sort(pq.toArray()).

不同方法的时间复杂度：

enqueuing and dequeuing: offer, poll, remove() and add - O(logn)O(\log n)O(logn)
Object: remove(Object) and contains(Object) - O(n)O(n)O(n)
retrieval: peek, element, and size - O(1)O(1)O(1).
Deque - 双端队列
双端队列（deque，全名double-ended queue）可以让你在任何一端添加或者移除元素，因此它是一种具有队列和栈性质的数据结构。

Java
Java 在1.6之后提供了 Deque 接口，既可使用ArrayDeque（数组）来实现，也可以使用LinkedList（链表）来实现。前者是一个数组外加首尾索引，后者是双向链表。

`Deque<Integer> deque = new ArrayDeque<Integer>();`
Methods

|         | First Element (Head) | Last Element (Tail) |
|---------|----------------------|---------------------|
|         | Throws exception     | Special value       | Throws exception | Special value  |
| Insert  | `addFirst(e)`        | `offerFirst(e)`     | `addLast(e)`     | `offerLast(e)` |
| Remove  | `removeFirst()`      | `pollFirst()`       | `removeLast()`   | `pollLast()`   |
| Examine | `getFirst()`         | `peekFirst()`       | `getLast()`      | `peekLast()`   |

该分类下的相关小册推荐：

业务开发实用算法精讲

数据结构与算法(中)

编程之道-算法面试(下)

算法面试通关 50 讲

编程之道-算法面试(上)

数据结构与算法之美

数据结构与算法(下)