1. 队列的概念

什么是队列？打个比方，就是一群人在排队买东西，先排队的人先拿到东西先离开，后排队的人后拿到东西后离开。

因此，队列是一种 只允许在一端进行插入数据操作，在另一端进行删除数据操作 的特殊线性表，即 “先进先出” ，而栈是“先进后出”。其中，进行插入操作的一端称为队尾（Tail/Rear），该操作叫做入队； 进行删除操作的一端称为队头（Head/Front），该操作叫做出队。在使用队列时，可以画出这样的图形

2.队列的使用

Queue是一个 接口 ，底层是 由LinkedList实现 的！

Queue里的方法是比较少的，如图：

其中，红色框框里的是一组，橙色框框里的是一组；两组的方法都差不多，一般情况下用的是红色框框里的方法

• offer(E):boolean 入列
• poll():E 出列
• peek():E获取队头元素

另外，Queue继承于Collection接口里的两个方法也比较常用：

• size():int 获取队列元素个数
• isEmpty()：boolean 判断队列是否为空

public class Test {public static void main(String[] args) {Queue<Integer> queue = new LinkedList<>();queue.offer(1);queue.offer(2);queue.offer(3);queue.offer(4);queue.offer(5);System.out.println(queue.poll());//1System.out.println(queue.size());//4System.out.println(queue.peek());//2System.out.println(queue.isEmpty());//false}
}

注意： Queue是接口，不能进行实例化接口，而是实例化LinkedList对象，因为LinkedList实现了Queue接口！

3. 队列的模拟实现

常见的结构有顺序结构和链式结构，那么我们模拟实现队列时，选用什么结构来实现呢？答案是都是可以的！

3.1 用链式结构实现队列

链式结构包括单链表和双链表，两种都是可以用来实现的

• 假如用单链表来实现，为了使时间复杂度更小，必须要采用头删和尾插，并且需要一个tail引用来标记尾节点，当然也需要head来标记头节点
• 假如用双链表来实现的话，那就灵活多了，既可以用头删和尾插来模拟实现出队和入队，也可以使用尾删和头插！

下面仅用双链表来模拟实现

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 = null;public ListNode last = null;public int usedSize = 0;public void offer(int val) {ListNode node = new ListNode(val);if(first == null) {first = last = node;}else {node.prev = last;last.next = node;last = node;}usedSize++;}public int poll() {if(first == null) {return -1;} else {int ret = first.val;first = first.next;if(first != null){first.prev = null;}usedSize--;return ret;}}public int peek() {if(first == null) {return -1;} else {return first.val;}}public boolean isEmpty() {return usedSize == 0;}
}

3.2 用顺序结构实现队列

如果使用数组去实现队列，当出队列后，要么把所有的元素都往前挪一位，然而这很浪费时间；要么就要浪费空间，当有大量的出队操作时，就会浪费大量的空间，简直是得不偿失！

那有什么办法可以解决这些问题呢？我们假如可以把数组的首尾连起来，构成循环，出队操作可以直接将队头往后挪一个位置，而原来的位置又能被后面的入队元素占据，这样既能节省时间，又不会浪费空间，接下来就来学习一下循环队列

4. 循环队列

环形队列通常使用数组实现

如图，在一个长度为8的循环队列中，存放12、23、34、45、56元素，用front标记队头，用rear标记队尾，注意rear是数组中最后一个有效元素的下一个

内圈表示数组的下标，外圈表示数组存放的元素。构建好基本的框架后，问题来了

问题1： 如何判空和判满

判空：只要front和rear相遇，就是空
判满：

• 方式1：定义一个变量usedSize，表示当前数组中存放有效数据的个数
• 方式2：添加标记，定义一个boolean类型的标记
• 方式3：浪费一个空间，每次添加元素时判断rear的下一个是不是front，若是则已满

如图，利用方式3，则该循环队列已满，因为rear的下一位是front。该方式浪费了一个空间

问题2： rear或front下标如何由7位置到0位置？可以利用如下公式：(rear + 1) % arr.length

废话不多说，直接上链接来用顺序结构来实现队列，题目链接：622. 设计循环队列

采用方式1的代码如下：

class MyCircularQueue {public int[] elem;public int front;public int rear;public int usedSize;public MyCircularQueue(int k) {elem = new int[k];}public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear] = value;rear = (rear+1) % elem.length;usedSize++;return true;}public boolean deQueue() {if(isEmpty()) {return false;}front = (front+1) % elem.length;usedSize--;return true;}public int Front() {if(isEmpty()) {return -1;}return elem[front];}public int Rear() {if(isEmpty()) {return -1;}int index = rear == 0? elem.length-1 : rear-1;return elem[index];}public boolean isEmpty() {if(usedSize == 0) {return true;}return false;}public boolean isFull() {if(usedSize == elem.length) {return true;}return false;}
}

5. 双端队列（Deque）

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。这也就说明，无论是栈，还是队列，都可以使用该接口

同样地，Deque是一个接口，使用时必须创建LinkedList的对象。

在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口

    Deque<Integer> stack = new ArrayDeque<>();//双端队列的线型实现Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

6. LeetCode刷题

6.1 用队列实现栈

题目链接：225. 用队列实现栈

解题思路：

1. 创建两个队列，当进行模拟栈的pop操作时，元素会从其中的一个队列转移到另外一个队列，两个队列交替来存放所有元素
2. 没有进行操作时，如果要实现的栈不为空，始终只有一个队列存有元素，另外一个队列为空
3. push操作：将元素放入非空队列中，若都是空对列则放入第一个队列中
4. pop操作：将非空队列中的元素依次放入另外一个队列中，只有最后一个元素出队
5. top操作与pop操作大同小异

代码如下：

class MyStack {public Queue<Integer> q1;public Queue<Integer> q2;public MyStack() {q1 = new LinkedList<>();q2 = new LinkedList<>();}public void push(int x) {if(!q1.isEmpty()) {q1.offer(x);}else if(!q2.isEmpty()) {q2.offer(x);}else {q1.offer(x);}}public int pop() {if(empty()) {return -1;}if(!q1.isEmpty()) {int size = q1.size();for(int i = 0; i < size-1; i++) {q2.offer(q1.poll());}return q1.poll();}else {int size = q2.size();for(int i = 0; i < size-1; i++) {q1.offer(q2.poll());}return q2.poll();}}public int top() {if(empty()) {return -1;}if(!q1.isEmpty()) {int size = q1.size();for(int i = 0; i < size-1; i++) {q2.offer(q1.poll());}int val = q1.peek();q2.offer(q1.poll());return val;}else {int size = q2.size();for(int i = 0; i < size-1; i++) {q1.offer(q2.poll());}int val = q2.peek();q1.offer(q2.poll());return val;}}public boolean empty() {return q1.isEmpty() && q2.isEmpty();}
}

6.2 用栈实现队列

题目链接：232. 用栈实现队列

解题思路：

1. 创建两个栈，其中一个栈s1专门用来入队，另外一个栈专门用来出队
2. 入队时，将元素添加进栈s1中
3. 出队时，判断栈s2是否为空，若为空则将s1中的全部元素依次都添入s2中，再将s2中的栈顶元素弹出；若s2不为空则直接将s2中的栈顶元素直接弹出

代码如下：

class MyQueue {public Stack<Integer> s1;public Stack<Integer> s2;public MyQueue() {s1 = new Stack<>();s2 = new Stack<>();}public void push(int x) {s1.push(x);}public int pop() {if(s2.isEmpty()) {while(!s1.isEmpty()) {s2.push(s1.pop());}}return s2.pop();}public int peek() {if(s2.isEmpty()) {while(!s1.isEmpty()) {s2.push(s1.pop());}}return s2.peek();}public boolean empty() {return s1.isEmpty() && s2.isEmpty();}
}