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