1.队列（Queue）
1.1概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)的性质
入队列：进行插入操作的一端称为队尾(Tail/Rear)
出队列：进行删除操作的一端称为队头(Head/Front)
1.2 队列的使用
在Java中，Queue是个接口，底层是通过链表实现的，在实例化Queue时，必须实例化LinkedList对象，因为LinkedList实现了Queue接口
| 方法 | 功能 |
| boolean offer(E e) | 入队列 |
| E poll() | 出队列 |
| peek() | 获取队头元素 |
| int size() | 获取队列中有效元素个数 |
| boolean isEmpty() | 检测队列是否为空 |
1.3 队列模拟实现（双列表实现）
public class MyQueue {
static class ListNode {
public int val;
public ListNode prev;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode first;
public ListNode last;
//尾插
public void offer(int val) {
ListNode node = new ListNode(val);
if(first == null) {
first = last = node;
}else {
node.prev = last;
last.next = node;
last = last.next;
}
}
//头删
public int poll() {
//队列为空
if(first == null) {
return -1;
}
int ret = first.val;
//队列只有一个节点
if(first.next == null) {
first = last = null;
}else {
//队列有多个节点
first = first.next;
first.prev = null;
}
return ret;
}
//查看队头元素
public int peek() {
if(first == null) {
return -1;
}
return first.val;
}
//判断队列是否为空
public boolean isEmpty() {
return first == null;
}
}
1.4 循环队列（数组实现）
一开始，first 和 last 从0下标开始，放一个元素 last++ ，如此，last 即为元素当前要存放的下标
判断循环队列是否已满：
解决下标从7 到 0 的过程，不能一直让 last++、first++，这样肯定会越界
公式：last = ( last + 1 ) % len(数组长度)
代码：
class MyCircularQueue {
public int[] elem;//数组实现
public int first;
public int last;
public MyCircularQueue(int k) {
//因为计数方法为保留一个空间，所以想要存放K个元素，需要申请K+1个空间
elem = new int[k+1];
}
//队尾添加元素
public boolean enQueue(int value) {
if(isFull()) {
return false;
}
elem[last] = value;
last = (last+1)%elem.length;
return true;
}
//队头删除元素
public boolean deQueue() {
if(isEmpty()) {
return false;
}
first = (first+1)%elem.length;
return true;
}
//从队头获取元素
public int Front() {
if(isEmpty()){
return -1;
}
return elem[first];
}
//从队尾获取元素
public int Rear() {
if(isEmpty()){
return -1;
}
int index = (last == 0) ? elem.length-1 : last-1;
return elem[index];
}
//判空
public boolean isEmpty() {
return first == last;
}
//判满
public boolean isFull() {
return (last+1)%elem.length == first;
}
}2. 双端队列（Deuqe）常用！
双端队列是指允许两端都可以进行入队和出队操作的队列，deque是 "double ended queue" 的简称
Deque是一个接口，使用时必须创建LinkedList对象
在实际工程中，使用Deque接口是比较多的，栈和队列均可使用该接口，如：
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现3. OJ
3.1 用队列实现栈
import java.util.LinkedList;
import java.util.Queue;
//用队列实现栈
//该方法用到两个队列
class MyStackUseQueue {
Queue<Integer> qu1;
Queue<Integer> qu2;
public MyStackUseQueue() {
qu1 = new LinkedList<>();
qu2 = new LinkedList<>();
}
public void push(int x) {
if(empty()) {//若两队列均为空，将x添加到qu1中
qu1.offer(x);
return;
}
if(!qu1.isEmpty()) {//两队列哪个不为空，添加到哪个里面
qu1.offer(x);
}else {
qu2.offer(x);
}
}
//删除栈顶元素
public int pop() {
if(empty()) {//若两队列均为空，返回-1
return -1;
}
if(!qu1.isEmpty()) {//若qu1不为空，将qu1中size-1个元素放到qu2中，剩下一个元素即为栈顶元素
int size = qu1.size();//存放qu1元素个数
for (int i = 0; i < size-1; i++) {//循环size-1次将元素放到qu2中
qu2.offer(qu1.poll());
}
return qu1.poll();//将qu1中剩下一个元素出队
}else {
int size = qu2.size();//与上同理
for (int i = 0; i < size-1; i++) {
qu1.offer(qu2.poll());
}
}
return qu2.poll();
}
//获取栈顶元素
public int top() {
if (empty()) {
return -1;
}
//若qu1不为空，循环将qu1中所有元素，通过中间变量ret放到qu2中，当放完后，ret中存放的值即为栈顶元素
if (!qu1.isEmpty()) {
int size = qu1.size();
int ret = -1;
for (int i = 0; i < size; i++) {
ret = qu1.poll();//qu1中元素出队，赋值给ret
qu2.offer(ret);//ret中值入队给qu2
}
return ret;
} else {
int size = qu2.size();
int ret = -1;
for (int i = 0; i < size; i++) {
ret = qu2.poll();
qu1.offer(ret);
}
return ret;
}
}
public boolean empty() {
return qu1.isEmpty() && qu2.isEmpty();
}
}3.2 用栈实现队列
import java.util.Stack;
//用栈实现队列，先进先出，用到两个栈
class MyQueueUseStack {
Stack<Integer> st1;
Stack<Integer> st2;
public MyQueueUseStack() {
st1 = new Stack<>();
st2 = new Stack<>();
}
//添加元素全部添加到st1中
public void push(int x) {
st1.push(x);
}
//删除队首元素
public int pop() {
if(empty()) {
return -1;
}
//若st2不为空，将st1中元素pop，push到st2中
if(st2.empty()) {
while(!st1.empty()) {
st2.push(st1.pop());
}
}
//因为栈是先进后出，所以模拟队列的队首元素在st1的最下面
//当把元素全部挪到st2中后，st2的栈顶元素即是队首元素
return st2.pop();
}
public int peek() {
if(empty()) {
return -1;
}
if(st2.empty()) {
while(!st1.empty()){
st2.push(st1.pop());
}
}
return st2.peek();
}
public boolean empty() {
return st1.empty() && st2.empty();
}
}以上两个OJ，若用双端队列来实现会更简单
