Queue
Queue队列介绍
Queue是用于模拟队列的，啥叫队列？队列就是排队的意思，比如排队结账，先进入队伍中，先排到先付账走人；后排到的，进入队伍，等前面的人出队伍后，再跟在后面付钱出队。符合“先进先出FIFO”的规则，是一种线性表。插入在一端，删除则在另一端。入队（offer）在队尾，出队（poll）在队头。
Queue接口有实现类PriorityQueue，有另一个双端队列接口Deque。
Queue队列进出示意图
队列进出示意图
Queue常用方法
PriorityQueue拥有Queue和Collection的方法。下面主要介绍一些常用方法：
-
boolean add(E e);：将指定元素加入到队列的尾部。 -
E element();：获取队列头部的元素，但是不删除该元素。 -
boolean offer(E e);：将指定元素加入到队列的尾部。 -
E peek();：获取队列头部的元素，但是不删除元素；若队列为空，返回null。 -
E poll();：获取队列头部的元素，并删除该元素。若队列为空，返回null。 -
E remove();：获取队列头部的元素，并删除该元素。若队列为空，抛异常。
PriorityQueue
PriorityQueue概述
PriorityQueue是Queue队列实现类，PriorityQueue保存队列元素的顺序不是按照加入队列的顺序，而是按照队列元素的大小进行重新排序。当调用peek()或者poll()方法获取队列元素时，获取的是队列最小元素，而不是先入队列的元素。有点反先入先出规则。
PriorityQueue示例
1）运行主类：
public class DemoApplication {
public static void main(String[] args) {
PriorityQueue priorityQueue = new PriorityQueue();
priorityQueue.offer(5);
priorityQueue.offer(-1);
priorityQueue.offer(3);
priorityQueue.offer(7);
//查看入队顺序
System.out.println("队列输出：" + priorityQueue);
//peek方法获取队头元素但是不删除元素
System.out.println("peek()方法获取队头：" + priorityQueue.peek());
//查看第一个元素即为最小元素
System.out.println("第一个队列元素出队：" + priorityQueue.poll());
System.out.println("第二个队列元素出队：" + priorityQueue.poll());
System.out.println("第三个队列元素出队：" + priorityQueue.poll());
System.out.println("第四个队列元素出队：" + priorityQueue.poll());
System.out.println("null队列：" + priorityQueue.poll());
}
}
2）运行结果：
队列输出：[-1, 5, 3, 7]
peek()方法获取队头：-1
第一个队列元素出队：-1
第二个队列元素出队：3
第三个队列元素出队：5
第四个队列元素出队：7
null队列：null
Deque
Deque双端队列介绍
Deque是Queue子接口，是双端队列。可以同时从两端（队列头部和尾部）添加、删除元素。所以可以用来实现栈的数据结构。有两个实现类（ArrayDeque和LinkedList）
Deque常用方法
-
void addFirst(E e)：将指定元素插入该双端队列的头部，比较重要，下面很多方法头部插入内部实现都是通过这个来实现的，如offerFirst()。 -
void addLast(E e)：将指定元素插入该双端队列的尾部。比较重要，下面添加到尾部插入内部实现都是通过这个来实现的，如offerLast()。 -
E getFirst()：获取但不删除双端队列的第一个元素。 -
E getLast()：获取但不删除双端队列的最后一个元素。 -
E removeFirst()：获取并删除该双端队列的第一个元素。栈的出队列方法pop()也是通过该方法实现的。 -
E removeLast()：获取并删除该双端队列的最后一个元素。 -
Iterator<E> descendingIterator()：返回双端队列的迭代器，逆向顺序迭代元素。 -
boolean offerFirst(E e)：将指定元素插入该双端队列的头部。
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
-
boolean offerLast(E e)：将指定元素插入该双端队列的尾部。
public boolean offerLast(E e) {
addLast(e);
return true;
}
-
E peekFirst()：获取但不删除该双端队列的第一个元素；若队列为空，则返回null。
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
-
E peekLast()：获取但不删除该双端队列的最后一个元素；若队列为空，则返回null。
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
-
E pollFirst()：获取并删除该双端队列的第一个元素；若队列为空，则返回null。
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
-
E pollLast()：获取并删除该双端队列的最后一个元素；若队列为空，则返回null。
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
-
E pop()：栈方法，pop出该双端队列表示栈的栈顶元素，等价于removeFirst()方法。
public E pop() {
return removeFirst();
}
-
void push(E e)：栈方法，push元素进入该双端队列表示栈的栈顶，等价于addFist()方法。
public void push(E e) {
addFirst(e);
}
-
boolean removeFirstOccurrence(Object o)：删除该双端队列的第一次出现的元素o，底层通过remove()方法实现。
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
-
boolean removeLastOccurrence(Object o)：删除该涮短队列的最后一次出现的元素o。
ArrayDeque
ArrayDeque概述
ArrayDeque底层实现类似于ArrayList，都是通过动态、可分配的Object[]数组来实现元素存储，当集合元素超过数组容量，会重新分配一个新的数组来存储集合元素。
ArrayDeque示例
1）运行主类
public class DemoApplication {
public static void main(String[] args) {
//可以作为栈来使用，先进后出
ArrayDeque<String> arrayDeque = new ArrayDeque<>();
arrayDeque.push("book01");
arrayDeque.push("book03");
arrayDeque.push("book02");
arrayDeque.push("book04");
System.out.println("原栈：" + arrayDeque);
System.out.println("获取头部元素，但不删除该元素，peek(): " + arrayDeque.peek());
System.out.println("获取头部元素，且删除该元素，pop(): " +arrayDeque.pop());
System.out.println("获取第一个元素，但不删除：" + arrayDeque.getFirst());
System.out.println("获取最后一个元素，但不删除：" + arrayDeque.getLast());
System.out.println("在双端队列头部插入元素：" + arrayDeque.offerFirst("booknew01"));
System.out.println("在双端队列尾部插入元素：" + arrayDeque.offerLast("booknew02"));
System.out.println("新栈：" + arrayDeque);
}
}
2）运行结果
原栈：[book04, book02, book03, book01]
获取头部元素，但不删除该元素: book04
获取头部元素，且删除该元素: book04
获取第一个元素，但不删除：book02
获取最后一个元素，但不删除：book01
true
true
新栈：[booknew01, book02, book03, book01, booknew02]
LinkedList
LinkedList概述
LinkedList实现List，同时也实现了Deque，可以当做双端队列来使用，可以当做“栈”或“队列”使用。
LinkedList与ArrayList、ArrayDeque不同之处在于底层实现，LinkedList底层是通过链表的形式存储元素，随机访问性能比较差，但是在插入、删除的时候性能比较好（只需要改变指针所指的地址就行）
Q&A
peek()和element()的异同
- 同：peek()和element()都是在不移除的情况下返回队头；
- 异：peek()方法在队列为空时返回null，而element()会抛出NoSuchElementException异常。
poll()和remove()的异同
- 同：poll()和remove()都是将移除并返回队头；
- 异：poll()在队列为空时返回null，而remove()会抛出NoSuchElementException异常。
队列和栈区别？
队列
- 队列是按照
先进先出FIFO原则进行操作元素的。 - 队列是限定所有的插入只能在表的一端进行，而删除在表的另一端进行的线性表。
- 表中允许插入的一端为队尾，允许删除的一端为队头。
栈
- 栈是一种特殊的线性表，是一种
后进先出LIFO的结构； - 栈是先定仅在表尾插入和删除运算的线性表，表尾即为
栈顶，表头称为栈底。 - 栈的物理存储可以用熟悉顺序存储结构，也可以用链式存储结构。
