Java 中的 队列（Queue）与双端队列（Deque）
这篇笔记期初是因为在刷算法题的过程中，发现其他解题方法很多地方有采用栈或者队列来解题，我在这方面比较薄弱，特此学习记录一下。
关于队列，我的初始印象就是先进先出，但是通过学习，了解到队列还有双端队列（Deque）、优先队列（PriorityQueue）等类型，不同的队列有不同的进出规则。
队列（Queue）
队列通常是以 FIFO （先进先出） 方式对元素进行排序，即在队头删除元素，队尾添加元素，在java代码中是继承了Collection<E>，所以也有Collection的方法，例如size(),isEmpty()等。这里只列出队列 Queue 的方法：
// 队列示例 初始化 结果为[1,2,3,4]
Queue<Integer> queue = new LinkedList<Integer>(){{add(1);add(2);add(3);add(4);}};| 方法名 | 描述 | 示例 |
| boolean add(E e); | 成功向队尾加入元素返回true,否则抛出以下异常： IllegalStateException – 如果队列有容量限制且队列已满无法添加 ClassCastException – 如果指定元素的类阻止将其添加到此队列 NullPointerException – 如果指定的元素为 null，并且此队列不允许空元素 IllegalArgumentException – 如果此元素的某些属性阻止将其添加到此队列 | queue.add(5); // 此时的队列结果 [1,2,3,4,5] |
| boolean offer(E e); | 成功向队尾加入元素返回true,否则抛出以下异常： ClassCastException – 如果指定元素的类阻止将其添加到此队列中 NullPointerException – 如果指定的元素为 null，并且此队列不允许 null 元素 IllegalArgumentException – 如果此元素的某些属性阻止将其添加到此队列中 与add(E e) 的区别：如果队列已满，offer(E e)方法会返回false, add(E e)会抛出异常 | queue.add(5); // 此时的队列结果 [1,2,3,4,5] |
| E remove(); | 删除并返回队列头的部元素 NoSuchElementException – 如果此队列为空 | Integer remove = queue.remove(); // 输出结果为 1 |
| E poll(); | 删除并返回队列头的部元素 ，如果队列为空，则返回null 与remove() 的区别： 如果队列为空，poll()会返回null,remove() 会抛出异常 | Integer remove = queue.remove(); // 输出结果为 1 |
| E element(); | 返回第一个元素 NoSuchElementException – 如果此队列为空 | queue.element(); // 1 |
| E peek(); | 返回第一个元素，如果队列为空，则返回null 与element() 的区别： 如果队列为空，peek()会返回null,element() 会抛出异常 | queue.peek(); // 1 |
双端队列（Deque）
双端队列（Deque）支持在队头和队尾两端都能添加、删除元素或者获取元素，Deque包含的元素既可以是没有固定容量的，也可以是有容量限制的。由于 Deque 继承了Queue，除了Queue 的方法外，还有自身所需的添加、删除和获取的方法，且和Queue的方法高度相似。例如添加方法，在Queue 中是 boolean add(E e)，在Deque 则是void addFirst(E e) 和 void addLast(E e) ,表示在队头、队尾的添加方法。
| 队头方法 | 队尾方法 | |||
| 失败抛异常 | 返回false或null | 失败抛异常 | 返回false或null | |
| 添加 | void addFirst(E e); | boolean offerFirst(E e); | void addLast(E e); | boolean offerLast(E e); |
| 删除 | E removeFirst(); | E pollFirst(); | E removeLast(); | E pollLast(); |
| 检查 | E getFirst(); | E getLast(); | E peekFirst(); | E peekLast(); |
addFirst 与 offerFirst 区别、addLast 与 offerLast 区别 ：如果队列已满，addFirst、addLast 会抛出异常- IllegalStateException，offerFirst、offerLast 都会返回false。类比 Queue 的add(E e) 和offer（E e）的区别，且抛出的异常情况一致。
removeFirst与pollFirst 区别、removeLast 与 pollLast 区别： 如果队列为空，removeFirst、removeLast会抛出异常-NoSuchElementException ，pollFirst、pollLast 会返回null.
getFirst 与 peekFirst 区别、getLast与 peekLast区别：如果队列为空，getFirst、getLast会抛出异常-NoSuchElementException ，peekFirst、peekLast 会返回null.
其他方法：
boolean removeFirstOccurrence(Object o);
删除指定的第一个元素，有则返回true,没有则返回false
ClassCastException – 如果指定元素的类与此双队列不兼容
NullPointerException – 如果指定的元素为空并且此双队列不允许空元素
// 举例 [5, 1, 2, 1, 3, 4]
Deque<Integer> deque = new LinkedList<>(){{add(5);add(1);add(2);add(1);add(3);add(4);}};deque.removeFirstOccurrence(1) // true 此时队列为 [5, 2, 1, 3, 4]deque.removeFirstOccurrence(7) //false 此时队列为 [5, 2, 1, 3, 4]boolean removeLastOccurrence(Object o);
删除指定的最后一个元素，有则返回true,没有则返回false
ClassCastException – 如果指定元素的类与此 deque 不兼容
NullPointerException – 如果指定的元素为 null 并且此 deque 不允许 null 元素
// 举例 [5, 1, 2, 1, 3, 4]
Deque<Integer> deque = new LinkedList<>(){{add(5);add(1);add(2);add(1);add(3);add(4);}};deque.removeFirstOccurrence(1) // true 此时队列为 [5, 1, 2, 3, 4]deque.removeFirstOccurrence(7) //false 此时队列为 [5, 1, 2, 3, 4]void push(E e)： 向队首添加元素，此方法等同于 addFirst。如果队列已满会抛出异常-IllegalStateException。
E pop()：删除并返回队列的第一个元素，此方法等效于 removeFirst（）。
Iterator<E> descendingIterator()： 以相反的顺序返回此 deque 中元素的迭代器。元素将按照从 last （tail） 到 first （head） 的顺序返回。返回： 此 deque 中元素的反向迭代器
其他
队列中除了两端队列（Deque），还有优先队列（PriorityQueue），优先队列中元素可以插入任意顺序的元素，但是会在获取元素的时候，按一定的顺序获取。
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>() {{add(5);add(1);add(2);add(1);add(3);add(4);}};System.out.println(priorityQueue); // [1, 1, 2, 5, 3, 4]System.out.println(priorityQueue.element()); // 1