1.栈和队列
栈（stack）：先入后出的容器。FILO(first in last out)。添加、删除操作均为O(1)。查询为O(n)（无序）。
队列(queue)：先进先出的容器。FIFO(first in first out)。添加、删除操作均为O(1)。查询为O(n)（无序）。
2.双端队列 Deque : Double-End Queue
可以理解为queue和stack的结合体，可以往最前端添加数据，也可以在最前端pop出来；既可以在尾端添加数据，也可以在尾端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中的数据层级关系如下：
java.util.AbstractCollection<E>
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。其实现类是多种多样的，具体类如下图可看到：
接口方法如下：
Queue的方法有两组，add(),remove(),element()方法是可以抛出异常的，offer(),poll(),peek()方法是会返回特殊的值。比如一个队列已满，如果调用add(e)方法添加元素，会抛出异常，而调用offer()方法会返回一个null或一个特殊的值，而不是抛出异常。
3.3Deque
Deque的类依赖关系如下：
Modulejava.base
Packagejava.util
Interface Deque<E>
可以看到Deque也是一个interface，它的实现类也有多个，具体如下
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. 优先队列（Priority Queue）
特点：1.插入操作时间复杂度 O(1)
2.取出操作时间复杂度 O(log n) - 按照元素的优先级取出
3. 底层具体实现的数据结构较为多样和复杂：heap
类依赖关系如下：
Modulejava.base
Packagejava.util
Class PriorityQueue<E>
java.util.PriorityQueue<E>
PriorityQueue 是一个class，它的方法如下：
PriorityQueue最终是实现了Queue，因此它里面包含了Queue的实现方法，实现优先级比较的方法是Comparator方法，里面定义优先级的字段、返回值等。
5.Queue源码的分析
public interface Queue extends Collection，Queue是一个继承了Collection的接口，里面只有简单的几个方法待实现它的类去实现：
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
里面的方法add()和offer()都是添加元素到队列中; remove()和poll()方法是移除最头部的元素，区别是如果队列为空，remove方法会抛出NoSuchElementException，poll()方法则返回null；element() 和peek()方法返回队列头部的方法但不删除，区别是如果队列为空，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 实现 Queue ，因此也实现 Queue 的6个方法。确切地说是5个方法，element()方法在 AbstractQueue 中进行了实现，在 PriorityQueue 没有实现。
但我们首先来看PriorityQueue 的构造方法：
1.public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
private static final int DEFAULT_INITIAL_CAPACITY = 11;
无参构造函数，默认调用一个传入初始容量为11的构造函数。
2.public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
传入初始队列容量值，则队列的初始容量大小为传入的值大小。
3.public PriorityQueue(Comparator comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
传参为一个比较器，调用默认容量值为11，带比较器的构造函数。
4.public PriorityQueue(int initialCapacity, Comparator comparator) {
if (initialCapacity <1) throw new IllegalArgumentException();
this.queue =new Object[initialCapacity];
this.comparator = comparator;
}
传参为指定容量，和比较器，创建一个传入容量大小的Object数组队列，将比较器赋值给本地比较器。
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);
}
}
传参为一个集合，则根据集合类型进行处理，获取集合的比较器，并将其根据不同类型转换为数组队列。
6.public PriorityQueue(PriorityQueue c) {
this.comparator = (Comparator) c.comparator();
initFromPriorityQueue(c);
}
传参为PriorityQueue ，获取其比较器，并转换为数组队列。
7.public PriorityQueue(SortedSet c) {
this.comparator = (Comparator) c.comparator();
initElementsFromCollection(c);
}
传参为SortedSet ，获取其比较器，并转换为数组队列。
接下来看它的5个队列的实现方法：
1.add()方法：
public boolean add(E e) {
return offer(e);
}
这里调用了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异常，若队列长度不够则进行扩容，当队列中原来没有数据时把传入的数据放在第一个元素处，当队列中原来有数据时将其和原来的元素根据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，然后将取出的最后一位的元素经过比较放在下标为0的位置。（这里具体怎么比较原谅我没特别明白，后续再补充）
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中没有的，这个方法返回的是作为参数传递进来的Comparator，而Comparator中的comparator()方法是PriorityQueue中决定优先级的方法。
public Comparatorcomparator() {
return comparator;
}
