Queue
Queue隊(duì)列介紹
??Queue是用于模擬隊(duì)列的蝶桶，啥叫隊(duì)列？隊(duì)列就是排隊(duì)的意思掉冶，比如排隊(duì)結(jié)賬真竖，先進(jìn)入隊(duì)伍中脐雪，先排到先付賬走人；后排到的恢共，進(jìn)入隊(duì)伍战秋，等前面的人出隊(duì)伍后，再跟在后面付錢出隊(duì)讨韭。符合“先進(jìn)先出FIFO”的規(guī)則脂信，是一種線性表。插入在一端透硝，刪除則在另一端狰闪。入隊(duì)（offer）在隊(duì)尾，出隊(duì)（poll）在隊(duì)頭濒生。
??Queue接口有實(shí)現(xiàn)類PriorityQueue埋泵，有另一個雙端隊(duì)列接口Deque。
Queue隊(duì)列進(jìn)出示意圖
Queue常用方法
??PriorityQueue擁有Queue和Collection的方法罪治。下面主要介紹一些常用方法：
-
boolean add(E e);：將指定元素加入到隊(duì)列的尾部秋泄。 -
E element();：獲取隊(duì)列頭部的元素，但是不刪除該元素规阀。 -
boolean offer(E e);：將指定元素加入到隊(duì)列的尾部。 -
E peek();：獲取隊(duì)列頭部的元素瘦麸，但是不刪除元素谁撼；若隊(duì)列為空，返回null滋饲。 -
E poll();：獲取隊(duì)列頭部的元素厉碟，并刪除該元素。若隊(duì)列為空屠缭，返回null箍鼓。 -
E remove();：獲取隊(duì)列頭部的元素，并刪除該元素呵曹。若隊(duì)列為空款咖，拋異常。
PriorityQueue
PriorityQueue概述
??PriorityQueue是Queue隊(duì)列實(shí)現(xiàn)類奄喂，PriorityQueue保存隊(duì)列元素的順序不是按照加入隊(duì)列的順序铐殃，而是按照隊(duì)列元素的大小進(jìn)行重新排序。當(dāng)調(diào)用peek()或者poll()方法獲取隊(duì)列元素時(shí)跨新，獲取的是隊(duì)列最小元素富腊，而不是先入隊(duì)列的元素。有點(diǎn)反先入先出規(guī)則域帐。
PriorityQueue示例
1）運(yùn)行主類：
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);
//查看入隊(duì)順序
System.out.println("隊(duì)列輸出：" + priorityQueue);
//peek方法獲取隊(duì)頭元素但是不刪除元素
System.out.println("peek()方法獲取隊(duì)頭：" + priorityQueue.peek());
//查看第一個元素即為最小元素
System.out.println("第一個隊(duì)列元素出隊(duì)：" + priorityQueue.poll());
System.out.println("第二個隊(duì)列元素出隊(duì)：" + priorityQueue.poll());
System.out.println("第三個隊(duì)列元素出隊(duì)：" + priorityQueue.poll());
System.out.println("第四個隊(duì)列元素出隊(duì)：" + priorityQueue.poll());
System.out.println("null隊(duì)列：" + priorityQueue.poll());
}
}
2）運(yùn)行結(jié)果：
隊(duì)列輸出：[-1, 5, 3, 7]
peek()方法獲取隊(duì)頭：-1
第一個隊(duì)列元素出隊(duì)：-1
第二個隊(duì)列元素出隊(duì)：3
第三個隊(duì)列元素出隊(duì)：5
第四個隊(duì)列元素出隊(duì)：7
null隊(duì)列：null
Deque
Deque雙端隊(duì)列介紹
??Deque是Queue子接口赘被，是雙端隊(duì)列是整。可以同時(shí)從兩端（隊(duì)列頭部和尾部）添加民假、刪除元素浮入。所以可以用來實(shí)現(xiàn)棧的數(shù)據(jù)結(jié)構(gòu)。有兩個實(shí)現(xiàn)類（ArrayDeque和LinkedList）
Deque常用方法
-
void addFirst(E e)：將指定元素插入該雙端隊(duì)列的頭部阳欲，比較重要舵盈，下面很多方法頭部插入內(nèi)部實(shí)現(xiàn)都是通過這個來實(shí)現(xiàn)的，如offerFirst()球化。 -
void addLast(E e)：將指定元素插入該雙端隊(duì)列的尾部秽晚。比較重要，下面添加到尾部插入內(nèi)部實(shí)現(xiàn)都是通過這個來實(shí)現(xiàn)的筒愚，如offerLast()赴蝇。 -
E getFirst()：獲取但不刪除雙端隊(duì)列的第一個元素。 -
E getLast()：獲取但不刪除雙端隊(duì)列的最后一個元素巢掺。 -
E removeFirst()：獲取并刪除該雙端隊(duì)列的第一個元素句伶。棧的出隊(duì)列方法pop()也是通過該方法實(shí)現(xiàn)的。 -
E removeLast()：獲取并刪除該雙端隊(duì)列的最后一個元素陆淀。 -
Iterator<E> descendingIterator()：返回雙端隊(duì)列的迭代器考余，逆向順序迭代元素轧苫。 -
boolean offerFirst(E e)：將指定元素插入該雙端隊(duì)列的頭部。
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
-
boolean offerLast(E e)：將指定元素插入該雙端隊(duì)列的尾部含懊。
public boolean offerLast(E e) {
addLast(e);
return true;
}
-
E peekFirst()：獲取但不刪除該雙端隊(duì)列的第一個元素；若隊(duì)列為空岔乔，則返回null酥筝。
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
-
E peekLast()：獲取但不刪除該雙端隊(duì)列的最后一個元素；若隊(duì)列為空嘿歌，則返回null剿配。
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
-
E pollFirst()：獲取并刪除該雙端隊(duì)列的第一個元素搅幅；若隊(duì)列為空，則返回null呼胚。
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
-
E pollLast()：獲取并刪除該雙端隊(duì)列的最后一個元素茄唐；若隊(duì)列為空，則返回null沪编。
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
-
E pop()：棧方法，pop出該雙端隊(duì)列表示棧的棧頂元素访圃，等價(jià)于removeFirst()方法相嵌。
public E pop() {
return removeFirst();
}
-
void push(E e)：棧方法，push元素進(jìn)入該雙端隊(duì)列表示棧的棧頂饭宾，等價(jià)于addFist()方法。
public void push(E e) {
addFirst(e);
}
-
boolean removeFirstOccurrence(Object o)：刪除該雙端隊(duì)列的第一次出現(xiàn)的元素o看铆，底層通過remove()方法實(shí)現(xiàn)。
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
-
boolean removeLastOccurrence(Object o)：刪除該涮短隊(duì)列的最后一次出現(xiàn)的元素o否淤。
ArrayDeque
ArrayDeque概述
??ArrayDeque底層實(shí)現(xiàn)類似于ArrayList棠隐，都是通過動態(tài)、可分配的Object[]數(shù)組來實(shí)現(xiàn)元素存儲助泽，當(dāng)集合元素超過數(shù)組容量，會重新分配一個新的數(shù)組來存儲集合元素。
ArrayDeque示例
1）運(yùn)行主類
public class DemoApplication {
public static void main(String[] args) {
//可以作為棧來使用挖藏，先進(jìn)后出
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("在雙端隊(duì)列頭部插入元素：" + arrayDeque.offerFirst("booknew01"));
System.out.println("在雙端隊(duì)列尾部插入元素：" + arrayDeque.offerLast("booknew02"));
System.out.println("新棧：" + arrayDeque);
}
}
2）運(yùn)行結(jié)果
原棧：[book04, book02, book03, book01]
獲取頭部元素会涎，但不刪除該元素: book04
獲取頭部元素，且刪除該元素: book04
獲取第一個元素末秃，但不刪除：book02
獲取最后一個元素，但不刪除：book01
true
true
新棧：[booknew01, book02, book03, book01, booknew02]
LinkedList
LinkedList概述
??LinkedList實(shí)現(xiàn)List练慕，同時(shí)也實(shí)現(xiàn)了Deque，可以當(dāng)做雙端隊(duì)列來使用项鬼，可以當(dāng)做“楐锶”或“隊(duì)列”使用。
??LinkedList與ArrayList哪工、ArrayDeque不同之處在于底層實(shí)現(xiàn)，LinkedList底層是通過鏈表的形式存儲元素雁比，隨機(jī)訪問性能比較差稚虎，但是在插入偎捎、刪除的時(shí)候性能比較好（只需要改變指針?biāo)傅牡刂肪托校?/p>
Q&A
peek()和element()的異同
- 同：peek()和element()都是在不移除的情況下返回隊(duì)頭茴她；
- 異：peek()方法在隊(duì)列為空時(shí)返回null，而element()會拋出NoSuchElementException異常丈牢。
poll()和remove()的異同
- 同：poll()和remove()都是將移除并返回隊(duì)頭；
- 異：poll()在隊(duì)列為空時(shí)返回null慌核，而remove()會拋出NoSuchElementException異常申尼。
隊(duì)列和棧區(qū)別？
隊(duì)列
- 隊(duì)列是按照
先進(jìn)先出FIFO原則進(jìn)行操作元素的师幕。 - 隊(duì)列是限定所有的插入只能在表的一端進(jìn)行，而刪除在表的另一端進(jìn)行的線性表钾怔。
- 表中允許插入的一端為隊(duì)尾，允許刪除的一端為隊(duì)頭宗侦。
棧
- 棧是一種特殊的線性表，是一種
后進(jìn)先出LIFO的結(jié)構(gòu)姑裂； - 棧是先定僅在表尾插入和刪除運(yùn)算的線性表男旗，表尾即為
棧頂，表頭稱為棧底察皇。 - 棧的物理存儲可以用熟悉順序存儲結(jié)構(gòu)，也可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)矾缓。
