1.概念
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特性。
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
2.队列的使用
注意：在Java中，Queue是个接口，所以在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口
| 方法 | 功能 |
| boolean offer(E e) | 入队列 |
| E poll() | 出队列 |
| peek() | 获取队头元素 |
| int size() | 获取队列中有效元素个数 |
| boolean isEmpty() | 检测队列是否为空 |
代码实例：
public static void main(String[] args) { Queue<Integer> queue=new LinkedList<>(); queue.offer(1); queue.offer(2); queue.offer(3); System.out.println(queue.peek());//1 System.out.println(queue.poll());//1 System.out.println(queue.peek());//2 }
3.队列模拟实现
队列中既然可以存储元素，那底层必须要有能够保存元素的空间，通过前边线性表的的学习我们了解到常见的空间类型有两种：顺序结构和链式结构，而我们队列的实现，如果使用顺序结构，插入数据的时间复杂度为O(1)，删除数据的时间复杂度为O（N）（删除头数据需要数组后边的数据整体前移）,说明并不能很高效的完成删除操作，所以我们用链式结构来存储。但当我们如果考虑用链式结构来存储时，有两种情况：
- 头插尾删：头插入队列的时间复杂度为O(1)，尾删出队列的时间复杂度为O(N).
- 尾插头删：尾插入队列的时间复杂度为O(N),头删出队列的时间复杂度为O(1).
由上边的两种情况我们也可以看出，即使是链式存储也并不能高效的完成任务，但如果我们加一个last引用指向尾节点，再以尾插入队列，头删出队列的方式其时间复杂度将都会成为O(1).
public class MyQueue { static class Node { public int val; public Node next; public Node(int val) { this.val = val; } } public Node head;//队列的头 public Node tail;//队列的尾 /** * 入队操作 * @param val */ public void offer(int val) { Node node=new Node(val); if(head==null) { head=node; tail=node; }else { tail.next=node; tail=tail.next; } } /** * 出队操作 */ public int poll() { if(head==null) throw new RuntimeException("队列为空！"); int val= head.val;; if(head.next==null) head=tail=null; else head=head.next; return val; } /** * 查看队头元素 */ public int peek() { if(head==null) { throw new RuntimeException("队列为空！"); } return head.val; } }
4.循环队列
循环队列通常使用数组实现。
如上图所示，front代表队列头，rear代表队列尾的前一个位置（用于判断当前位置是否可以成为新队尾），当front==rear时队列为空。
为了实现数组下标的循环，在后移的时候使用取余的方式，例如rear需要后移一步，则rear=(rear+1)%len,len为数组的长度。
如果队列满了，就成为下图的情况：
此时front又和rear相等了，我们判断队列满有两种方式，一种是使用usedSize属性记录添入元素个数，当usedSize == length时队列满。另一种方式是浪费最后一个格子，如下图，当（rear+1）%len == front时，就判断为满不再添加元素了。
我们来做一道力扣练习题来更好的了解循环队列。
【622. 设计循环队列】
题意：
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
示例：
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3 circularQueue.enQueue(1); // 返回 true circularQueue.enQueue(2); // 返回 true circularQueue.enQueue(3); // 返回 true circularQueue.enQueue(4); // 返回 false，队列已满 circularQueue.Rear(); // 返回 3 circularQueue.isFull(); // 返回 true circularQueue.deQueue(); // 返回 true circularQueue.enQueue(4); // 返回 true circularQueue.Rear(); // 返回 4
代码：
方法一：利用usedSize记录有效数据个数
class MyCircularQueue { int []array;//存储数组 int front;//队列头 int rear;//队列尾的前一个位置 int usedSize;//记录有效数据个数 public MyCircularQueue(int k) { array=new int[k]; front=0; rear=0; usedSize=0; } public boolean enQueue(int value) { if(isFull()) return false; else { array[rear]=value; usedSize++; rear=(rear+1)%array.length; return true; } } public boolean deQueue() { if(isEmpty()) return false; else { //删除队列头直接让头后移一个位置并让usedSize--即可，当在有新的数据插入到此位置时会把原来的数据覆盖 front=(front+1)%array.length; usedSize--; return true; } } public int Front() { if(isEmpty()) return -1; else { return array[front]; } } public int Rear() { if(isEmpty()) return -1; else { //特殊情况：0下边的前一个位置时数组的最后一个位置 int index=rear-1; if(rear==0) index=array.length-1; return array[index]; } } public boolean isEmpty() { return usedSize==0; } public boolean isFull() { return usedSize==array.length; } } /** * Your MyCircularQueue object will be instantiated and called as such: * MyCircularQueue obj = new MyCircularQueue(k); * boolean param_1 = obj.enQueue(value); * boolean param_2 = obj.deQueue(); * int param_3 = obj.Front(); * int param_4 = obj.Rear(); * boolean param_5 = obj.isEmpty(); * boolean param_6 = obj.isFull(); */
方法二：浪费一个位置来判满
class MyCircularQueue { int []array; int front; int rear; public MyCircularQueue(int k) { array=new int[k+1]; front=0; rear=0; } public boolean enQueue(int value) { if(isFull()) return false; else { array[rear]=value; rear=(rear+1)%array.length; return true; } } public boolean deQueue() { if(isEmpty()) return false; else { front=(front+1)%array.length; return true; } } public int Front() { if(isEmpty()) return -1; else { return array[front]; } } public int Rear() { if(isEmpty()) return -1; else { int index=rear-1; if(rear==0) index=array.length-1; return array[index]; } } public boolean isEmpty() { return rear==front; } public boolean isFull() { return (rear+1)%array.length==front; } } /** * Your MyCircularQueue object will be instantiated and called as such: * MyCircularQueue obj = new MyCircularQueue(k); * boolean param_1 = obj.enQueue(value); * boolean param_2 = obj.deQueue(); * int param_3 = obj.Front(); * int param_4 = obj.Rear(); * boolean param_5 = obj.isEmpty(); * boolean param_6 = obj.isFull(); */
5.双端队列（Deque）
双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。
那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
Deque是一个接口，使用时必须创建LinkedList的对象。
使用：
双端队列既能作为栈来使用，也能作为队列来使用。
当作栈时调用push方法，将会从底层链表头插数据，pop方法从底层链表头删数据。
当作队列时调用offer方法，将会从底层链表尾插数据，poll方法从链表头删数据。
两者都适用于peek方法，因为在源码中，peek方法返回链表头，就是栈的栈顶，也就是队列的队头。
6.经典面试题
1.【232. 用栈实现队列】
题意：
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
思路：
入队列时入进栈，出队列时把数据从入栈出，进出栈内，再从出栈出数据，就模拟实现了队列的先进先出。
代码：
class MyQueue { Stack<Integer> stackIn; Stack<Integer> stackOut; public MyQueue() { stackIn=new Stack<>(); stackOut=new Stack<>(); } public void push(int x) { stackIn.push(x); } public int pop() { fun(); return stackOut.pop(); } public int peek() { fun(); return stackOut.peek(); } public boolean empty() { return stackIn.isEmpty()&&stackOut.isEmpty(); } private void fun() { //当出栈不为空时，直接返回，此时可以直接从出栈出数据 //当出栈为空时，需要把入栈内的数据全部出到出栈中。 if(!stackOut.isEmpty()) return; while (!stackIn.isEmpty()) { stackOut.push(stackIn.pop()); } } } /** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */
2.【225. 用队列实现栈】
题意：
使用队列实现栈的下列操作：
push(x) – 元素 x 入栈
pop() – 移除栈顶元素
top() – 获取栈顶元素
empty() – 返回栈是否为空
注意:
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
思路：
用队列来模拟栈的先进后出，此时就需要通过两个栈来更改数据的顺序，来模拟实现先进后出。
在每次新入元素时，让该元素先进入queue2中，如果queue1中元素不为空，就让queue1中元素依次出队列进入queue2中，再交换queue1和queue2，这样就可以通过queue2调整元素的顺序，使得queue1中的元素顺序模拟了栈的先入后出。
代码：
class MyStack { Queue<Integer> queue1; Queue<Integer> queue2; public MyStack() { queue1=new LinkedList<>(); queue2=new LinkedList<>(); } public void push(int x) { queue2.offer(x); while (!queue1.isEmpty()) { queue2.offer(queue1.poll()); } //交换queue1和queue2，交换完成后queue1成为模拟栈，queue2又变为空 Queue<Integer> temp=queue1; queue1=queue2; queue2=temp; } public int pop() { return queue1.poll(); } public int top() { return queue1.peek(); } public boolean empty() { return queue1.isEmpty(); } } /** * Your MyStack object will be instantiated and called as such: * MyStack obj = new MyStack(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.top(); * boolean param_4 = obj.empty(); */
3.【155. 最小栈】
题意：
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
思路：
利用辅助栈来存储栈中最小的元素，入栈时数据栈正常入栈，辅助栈在为空时或者数据小于等于栈顶元素时，辅助栈也入栈数据。此时如果获取堆栈中最小元素，直接返回辅助栈的栈顶元素即可。在删除栈顶元素时，需要判断数据栈要删除的元素是否和辅助栈的栈顶元素相同，相同的情况下辅助栈也需要删除元素。
代码：
class MinStack { Stack<Integer> stack; Stack<Integer> minStack; public MinStack() { stack=new Stack<>(); minStack=new Stack<>(); } public void push(int val) { stack.push(val); if(minStack.empty()||val<=minStack.peek()) minStack.push(val); } public void pop() { int val=stack.pop(); if(minStack.peek()==val) minStack.pop(); } public int top() { return stack.peek(); } public int getMin() { return minStack.peek(); } }
