1. 队列
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作并具有先进先出特点的特殊线性表。
对尾：进行插入操作的一端。
对头：进行删除操作的一端。
2. 队列的模拟实现
队列可以通过链表或顺序表来实现。
2.1 通过链表来实现队列
这里我们使用双向链表连实现。
2.1.1 接口
public class MyQueue {static class ListNode {public ListNode next;public ListNode prev;public int val;public ListNode(int val) {this.val = val;}}public ListNode first;public ListNode last;//入队列public void offer(int val) {}//出队列public int poll() {}//获取队头元素 但是不删除public int peek() {}//判空public boolean isEmpty() {}
}
2.1.2 内部类
和双向链表一样。
static class ListNode {public ListNode next;public ListNode prev;public int val;public ListNode(int val) {this.val = val;}}2.1.3 入队列
思路：
1. 先判断队列是否为空，为空头结点和尾结点同时指向入队node结点。
2. 尾结点的后驱next指向入队node结点，入队结点的前驱prev指向尾结点，尾结点指向入队 node结点。
public void offer(int val) {ListNode node = new ListNode(val);if(isEmpty()) {first = last = node;return;}last.next = node;node.prev = last;last = node;}2.1.4 出队列
思路：
1. 先判断队列是否为空，为空直接抛异常。
2. 把头结点的val值先存一份。
3. 再判断头结点的后驱是否为空，为空把头结点的后驱next的前驱prev置为空。
4. 返回之前头结点的值。
public int poll() {if(isEmpty()) {throw new QueueEmptyException();}int val = first.val;if(first.next != null) {first.next.prev = null;}first = first.next;return val;}2.1.5 获取队头元素 但是不删除
思路：
1. 先判断队列是否为空，为空直接抛异常。
2. 返回头结点的val值。
public int peek() {if(isEmpty()) {throw new QueueEmptyException();}int val = first.val;return val;}2.1.6 判空
判读头结点是否等于空。
public boolean isEmpty() {return first == null;}2.2 通过顺序表来实现队列
如果我们直接使用顺序表来实现队列，在删除元素之后再插入元素会造成空间的浪费，所以我们使用循环队列来实现。（这里的循环队列我们浪费了一个空间）
2.2.1 接口
public class MyCircularQueue {public int[] elem;public int rear;public int front;//构造器，设置队列长度为 kpublic MyCircularQueue(int k) {}// 入队列public boolean enQueue(int value) {}//出队列public boolean deQueue() {}//获取对头元素public int Front() {}//获取队尾元素public int Rear() {}//检查循环队列是否为空。public boolean isEmpty() {}//检查循环队列是否已满。public boolean isFull() {}
}2.2.2 构造器，设置队列长度为 k
给队列设置k个容量。
public MyCircularQueue(int k) {elem = new int[k];}2.2.3 入队列
思路：
1. 先判断循环队列是否为空，为空返回false。
2. 不为空插入value，并使rear向后移动一位，返回true。
public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear] = value;rear = (rear+1)%elem.length;return true;}2.2.4 出队列
思路：
1. 先判断队列是否为空，为空返回false。
2. 不为空，删除队列front下标元素，然后让front移动到下一位，并返true。
public boolean deQueue() {if(isEmpty()) {return false;}front = (front+1)%elem.length;return true;}2.2.5 获取队头元素
思路：
1. 先判断循环队列是否为空，为空返回-1.
2. 不为空，返回队列front下标的元素。
public int Front() {if(isEmpty()) {return -1;}return elem[front];}2.2.6 获取队尾元素
思路：
1. 判断队列是否为空，为空返回-1。
2. 判断rear是否为零，为零返回数组长度-1下标的元素。
3. 最后返回rear-1下标的元素。
public int Rear() {if(isEmpty()) {return -1;}if(rear == 0) {return elem[elem.length-1];}return elem[rear-1];}2.2.7 检查循环队列是否为空
判断front是否等于rear。
public boolean isEmpty() {return front == rear;}2.2.8 检查循环队列是否已满
判断front是否等于rear+1和数组长度取余的结果。
public boolean isFull() {return (rear+1)%elem.length == front;}3. JAVA中的队列（Queue）
3.1 Queue接口
3.2 Queue的常用方法
)
