1. 队列的概念
队列只允许在一端进行插入操作，在另一端进行删除操作的特殊线性表，队列具有先进先出（FIFO）的特性，进行插入操作的一端为队尾，进行删除操作的一端为队头。
2. 队列的使用
在Java中，Queue是一个接口，底层是通过链表来实现的
| 方法 | 功能说明 |
| boolean offer(E e) | 入队列 |
| E poll() | 出队列 |
| E peek() | 获取对头元素 |
| int size() | 获取队列中有效元素的个数 |
| boolean isEmpty() | 检测队列是否为空 |
注意：队列Queue是一个接口，在实例化对象时必须实例化LinkedList对象，因为LinkedList实现了Queue接口
import java.util.LinkedList; import java.util.Queue; public class TestQueue { public static void main(String[] args) { Queue<Integer> q = new LinkedList<>(); q.offer(1); q.offer(2); q.offer(3); q.offer(4); q.offer(5); System.out.println(q); System.out.println(q.size()); q.poll(); q.poll(); System.out.println(q); System.out.println(q.isEmpty()); } } //执行结果：[1, 2, 3, 4, 5] // 5 // [3, 4, 5] // false
3. 队列的模拟实现
public class Queue<E> { public static class ListNode<E>{ E val; ListNode<E> next; ListNode<E> pre; ListNode(E val){ this.val = val; } } ListNode<E> first; //队头 ListNode<E> last; //队尾 int size = 0; //入队列---插新节点 public void offer(E e){ ListNode<E> newNode = new ListNode<>(e); if(first==null){ first = newNode; last = newNode; }else{ last.next = newNode; newNode.pre = last; last = newNode; } size++; } //出队列---删除头 public E poll(){ E val = null; if(first==null){ return null; }else if(first == last){ first = null; last = null; }else{ val = first.val; first = first.next; first.pre.next = null; first.pre = null; } size--; return val; } //获取队头元素 public E peek(){ if(first == null){ return null; } return first.val; } //获取长度 public int size(){ return size; } //判空 public boolean isEmpty(){ return first==null; } //栈和队列一般不进行遍历操作 public static void main(String[] args) { Queue<Integer> q = new Queue<>(); q.offer(1); q.offer(2); q.offer(3); q.offer(4); System.out.println(q.size()); System.out.println(q.peek()); q.poll(); System.out.println(q.size()); } }
4. 循环队列
循环队列使用的是循环数组，为什么不使用普通的数组呢？
如果使用一段连续的空间则会造成空间假溢出，造成空间的浪费，因为队列是在尾端进行插入，在头部进行删除，这样会造成数组中的元素偏后，如下面的情形：
所以使用的循环数组，循环队列就是解决空间的假溢出。
当对头与队尾重合时如何区分循环队列的空与满呢？我们可以通过添加size来记录队列元素的个数，当size为0时队列为空，当size不为0时，队列为满。
下面是循环队列的实现：
//循环队列 public class CircularQueue { int array[]; int rear = 0; //队尾下标 int front = 0; //队头下标 int count = 0; //队列的有效元素的个数 int N; public CircularQueue(int k) { array = new int[k]; //创建一个数组 N = array.length; //用N标记数组的长度 } public boolean enQueue(int value) { //入队列 if(isFull()){ return false; //如果队列已经满了，则返回false } array[rear] = value; rear++; if(rear==N){ //rear返回起始位置 rear = 0; } count++; return true; } public boolean deQueue() { //出队列 if(isEmpty()){ //如果队列为空，则返回false return false; } front++; front%=N; //front返回起始位置 count--; return true; } public int Front() { //获取队头元素 if(isEmpty()){ return -1; } return array[front]; } public int Rear() { //获取队尾元素 if(isEmpty()){ return -1; } return array[(rear-1+N)%N]; //队尾元素的下标为rear-1，如果rear为0，则下标就为-1了，所以需要（rear-1+n）% n } public boolean isEmpty() { //检测队列是否为空 return count==0; } public boolean isFull() { //检测队列是否已满 return count==N; } }
5. 双端队列
双端队列是指允许两端都可以进行入队列和出队列操作的队列，deque（double ended queue的简称）。
6. OJ题
1. 用队列实现栈 （LeetCode225）用队列实现栈
可以点开上面链接来查看题目
方法：
1. 先创建两个队列
2. 判空：如果两个队列都为空，则返回true，否则返回false
3. 插入元素：当两个队列都为空的时候，随便选一个队列往里插入元素，当有一个队列不为空的时候，往这个不为空的队列里插入元素
4. 删除栈顶元素：哪一个队列不为空，就将这个队列的元素往另一个为空的队列里放，直到不为空的队列剩余一个元素，最后再将这个元素出队列，用一个变量接收并返回
5. 获取栈顶元素：这个操作和前面删除栈顶元素大概相同，只是在返回元素之前，将这个元素插入另一个不为空的队列中
参考代码：
class MyStack { Queue<Integer> q1 = new LinkedList<>(); Queue<Integer> q2 = new LinkedList<>(); public MyStack() { } public void push(int x) { if(q2.isEmpty()){ q1.offer(x); }else{ q2.offer(x); } } public int pop() { int ret = 0; if(!q1.isEmpty()){ while(q1.size()>1){ q2.offer(q1.poll()); } ret = q1.poll(); }else{ while(q2.size()>1){ q1.offer(q2.poll()); } ret = q2.poll(); } return ret; } public int top() { int ret = 0; if(!q1.isEmpty()){ while(q1.size()>1){ q2.offer(q1.poll()); } ret = q1.poll(); q2.offer(ret); }else{ while(q2.size()>1){ q1.offer(q2.poll()); } ret = q2.poll(); q1.offer(ret); } return ret; } public boolean empty() { if(q1.isEmpty()&&q2.isEmpty()){ return true; } return false; } }
2. 实现一个最小栈（LeetCode155）最小栈
点上述链接查看题目
方法：
1. 先构造两个栈，栈s1储存所有元素，栈s2储存最小元素
2. 入栈：第一个元素给两个栈都添加，下来的元素如果小于等于s2的栈顶元素，则将元素入栈s2，所有元素都入栈s1
3. 获取栈顶元素：直接获取栈s1的栈顶元素
4. 删除栈顶元素：对于s2：如果s1栈顶元素与s2栈顶元素相等，则出栈；对于s1：依次出栈
5. 获取栈里的最小元素：直接返回栈s2的栈顶元素
参考代码：
class MinStack { Stack<Integer> s1 = new Stack<>(); Stack<Integer> s2 = new Stack<>(); public MinStack() { } public void push(int val) { if(s1.empty()||val<=s2.peek()){ s2.push(val); } s1.push(val); } public void pop() { if(s1.peek().equals(s2.peek())){ s2.pop(); } s1.pop(); } public int top() { return s1.peek(); } public int getMin() { return s2.peek(); } }
3. 用栈实现队列（LeetCode232）用栈实现队列
查看上面链接查看题目
方法：
1. 构造两个栈，一个输入栈s1，一个输出栈s2
2. 判空：当两个栈都为空时，返回true，否则返回false
3. 入队列：直接往栈s1插入元素
4. 出队列：当s2为空时，将s1的所有元素入s2，然后将s2的元素出栈
5. 获取队头元素：当s2为空时，将s1的所有元素入s2，直接获取s2栈顶元素并返回
参考代码：
class MyQueue { Stack<Integer> s1 = new Stack<>(); //输入 Stack<Integer> s2 = new Stack<>(); //输出 public MyQueue() { } public void push(int x) { s1.push(x); } public int pop() { if(s2.empty()){ while(!s1.empty()){ s2.push(s1.pop()); } } return s2.pop(); } public int peek() { if(s2.empty()){ while(!s1.empty()){ s2.push(s1.pop()); } } return s2.peek(); } public boolean empty() { if(s1.empty()&&s2.empty()){ return true; } return false; } }
