1.棧和隊列
棧（stack）：先入后出的容器。FILO(first?in last out)。添加、刪除操作均為O(1)。查詢?yōu)镺(n)（無序）。
隊列(queue)：先進先出的容器。FIFO(first in first out)。添加、刪除操作均為O(1)。查詢?yōu)镺(n)（無序）。
2.雙端隊列 Deque : Double-End Queue
可以理解為queue和stack的結(jié)合體，可以往最前端添加數(shù)據(jù)，也可以在最前端pop出來；既可以在尾端添加數(shù)據(jù)，也可以在尾端pop出來。插入和刪除操作時間復雜度是O(1)，查詢操作時間復雜度是O(n)。
3.java中Stack、Queue、Deque 的接口查詢和使用
3.1 Stack
java Stack的文檔地址：https://docs.oracle.com/javase/10/docs/api/java/util/Stack.html。下面進行分析，
棧在java中的數(shù)據(jù)層級關系如下：
????????java.util.AbstractCollection<E>
????????????????java.util.AbstractList<E>
????????????????????????java.util.Vector<T>
????????????????????????????????java.util.Stack<T>
5個方法如下：
empty() 返回該棧是否為空；
peek() 查看棧頂元素，不對棧進行修改；
pop() 彈出棧頂元素，并返回該元素；
push() 將一個元素加入棧頂；
search() 查找一個元素在棧中的下標。
3.2 Queue
Queue 在java中的類依賴關系如下，
Modulejava.base
????????Packagejava.util
????????????Interface Queue<E>
可以看到，queue并不是一個class，而是一個interface。其實現(xiàn)類是多種多樣的，具體類如下圖可看到：
接口方法如下：
Queue的方法有兩組，add(),remove(),element()方法是可以拋出異常的，offer(),poll(),peek()方法是會返回特殊的值。比如一個隊列已滿，如果調(diào)用add(e)方法添加元素，會拋出異常，而調(diào)用offer()方法會返回一個null或一個特殊的值，而不是拋出異常。
3.3Deque
Deque的類依賴關系如下：
Modulejava.base
????????Packagejava.util
????????????????Interface Deque<E>
可以看到Deque也是一個interface，它的實現(xiàn)類也有多個，具體如下
Deque的提供的接口方法如下
同queue一樣，對每個元素的操作有兩組，對于First Element的操作，addFirst(),removeFirst(),getFirst()方法會拋出異常，offerFirst(),pollFirst(),peekFirst()方法不會拋出異常，而是返回一個特殊的值。對于LastElement 的操作，addLast(),removeLast(0,getLast()方法會拋出異常，offerLast(),pollLast(),peekLast()方法不是拋出異常，而是返回一個特殊的值。
Deque和Queue的方法進行對比：
Deque是雙向的，Queue是單向的先進先出的，因此Queue的添加操作相對于Deque來說是對于last元素進行添加，Queue的刪除操作相對于Deque是first元素進行刪除。
Deque和Stack的方法進行對比：
Deque是雙向的，Stack是單向的先進后出的，因此Stack的push(),pop(),peek()操作相對于Deque來說都是對于first元素進行的。
4. 優(yōu)先隊列（Priority Queue）
特點：1.插入操作時間復雜度 O(1)
? ? ? ? ? ?2.取出操作時間復雜度 O(log n) - 按照元素的優(yōu)先級取出
? ? ? ? ? ?3. 底層具體實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)較為多樣和復雜：heap
類依賴關系如下：
Modulejava.base
Packagejava.util
Class PriorityQueue<E>
????????java.util.AbstractCollection
????????????????java.util.AbstractQueue
????????????????????????java.util.PriorityQueue<E>
PriorityQueue 是一個class，它的方法如下：
PriorityQueue最終是實現(xiàn)了Queue，因此它里面包含了Queue的實現(xiàn)方法，實現(xiàn)優(yōu)先級比較的方法是Comparator方法，里面定義優(yōu)先級的字段、返回值等。
5.Queue源碼的分析
public interface Queue?extends Collection，Queue是一個繼承了Collection的接口，里面只有簡單的幾個方法待實現(xiàn)它的類去實現(xiàn)：
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
里面的方法add()和offer()都是添加元素到隊列中; remove()和poll()方法是移除最頭部的元素，區(qū)別是如果隊列為空，remove方法會拋出NoSuchElementException，poll()方法則返回null；element() 和peek()方法返回隊列頭部的方法但不刪除，區(qū)別是如果隊列為空，element方法會拋出NoSuchElementException，peek()方法則返回null。
6.和Priority Queue源碼的分析
public class PriorityQueue?extends AbstractQueue?implements java.io.Serializable
public abstract class AbstractQueue extends AbstractCollection implements Queue
PriorityQueue? 繼承 AbstractQueue? ?實現(xiàn)? Queue ，因此也實現(xiàn)?Queue 的6個方法。確切地說是5個方法，element()方法在 AbstractQueue? 中進行了實現(xiàn)，在 PriorityQueue? 沒有實現(xiàn)。
但我們首先來看PriorityQueue 的構(gòu)造方法：
1.public PriorityQueue() {
????????this(DEFAULT_INITIAL_CAPACITY, null);
}
private static final int DEFAULT_INITIAL_CAPACITY = 11;
無參構(gòu)造函數(shù)，默認調(diào)用一個傳入初始容量為11的構(gòu)造函數(shù)。
2.public PriorityQueue(int initialCapacity) {
????????this(initialCapacity, null);
}
傳入初始隊列容量值，則隊列的初始容量大小為傳入的值大小。
3.public PriorityQueue(Comparator comparator) {
????????this(DEFAULT_INITIAL_CAPACITY, comparator);
}
傳參為一個比較器，調(diào)用默認容量值為11，帶比較器的構(gòu)造函數(shù)。
4.public PriorityQueue(int initialCapacity,? Comparator comparator) {
? ? if (initialCapacity <1)? ?throw new IllegalArgumentException();
? ? this.queue =new Object[initialCapacity];
? ? this.comparator = comparator;
}
傳參為指定容量，和比較器，創(chuàng)建一個傳入容量大小的Object數(shù)組隊列，將比較器賦值給本地比較器。
5.public PriorityQueue(Collection c) {
if (cinstanceof SortedSet) {
SortedSet ss = (SortedSet) c;
? ? ? ? this.comparator = (Comparator) ss.comparator();
? ? ? ? initElementsFromCollection(ss);
? ? }
else if (cinstanceof PriorityQueue) {
PriorityQueue pq = (PriorityQueue) c;
? ? ? ? this.comparator = (Comparator) pq.comparator();
? ? ? ? initFromPriorityQueue(pq);
? ? }
else {
this.comparator =null;
? ? ? ? initFromCollection(c);
? ? }
}
傳參為一個集合，則根據(jù)集合類型進行處理，獲取集合的比較器，并將其根據(jù)不同類型轉(zhuǎn)換為數(shù)組隊列。
6.public PriorityQueue(PriorityQueue c) {
this.comparator = (Comparator) c.comparator();
? ? initFromPriorityQueue(c);
}
傳參為PriorityQueue ，獲取其比較器，并轉(zhuǎn)換為數(shù)組隊列。
7.public PriorityQueue(SortedSet c) {
this.comparator = (Comparator) c.comparator();
? ? initElementsFromCollection(c);
}
傳參為SortedSet ，獲取其比較器，并轉(zhuǎn)換為數(shù)組隊列。
接下來看它的5個隊列的實現(xiàn)方法：
1.add()方法：
public boolean add(E e) {
????????return offer(e);
}
這里調(diào)用了offer()方法。
2.offer()方法：
public boolean offer(E e) {
if (e ==null)
throw new NullPointerException();
? ? modCount++;
? ? int i =size;
? ? if (i >=queue.length)
grow(i +1);
? ? size = i +1;
? ? if (i ==0)
queue[0] = e;
else
? ? ? ? siftUp(i, e);
return true;
}
首先判斷要添加的方法是否為空，若為空則拋出NullPointerException異常，若隊列長度不夠則進行擴容，當隊列中原來沒有數(shù)據(jù)時把傳入的數(shù)據(jù)放在第一個元素處，當隊列中原來有數(shù)據(jù)時將其和原來的元素根據(jù)Compator進行比較放在比較后所在的位置。
3.peek()
@SuppressWarnings("unchecked")
public E peek() {
return (size ==0) ?null : (E)queue[0];
}
判斷隊列的長度，若為空則返回null，不為空則獲取下標為0的隊列中的元素。但是并沒有對隊列進行操作。
4.poll()
public E poll() {
if (size ==0)
return null;
? ? int s = --size;
? ? modCount++;
? ? E result = (E)queue[0];
? ? E x = (E)queue[s];
? ? queue[s] =null;
? ? if (s !=0)
siftDown(0, x);
? ? return result;
}
獲取隊列中下標為0的元素，將最后位的元素取出，并將最后一位元素位置上的值置為null，然后將取出的最后一位的元素經(jīng)過比較放在下標為0的位置。（這里具體怎么比較原諒我沒特別明白，后續(xù)再補充）
5.remove()
public boolean remove(Object o) {
int i = indexOf(o);
? ? if (i == -1)
return false;
? ? else {
removeAt(i);
return true;
? ? }
}
找到想要刪除元素的下標，如果下標不存在則返回false，如果存在則將其刪除，返回true。
6.在PriorityQueue中還有一個方法comparator()是Queue中沒有的，這個方法返回的是作為參數(shù)傳遞進來的Comparator，而Comparator中的comparator()方法是PriorityQueue中決定優(yōu)先級的方法。
public Comparatorcomparator() {
return comparator;
}
