1. 队列的基本知识

1.1 概念及特性

队列概念：

队列：是一种只允许在一端进行数据的插入，在另一端进行数据的删除操作的特殊线性表，在Java中，队列（Queue）是个接口，继承自 Collection ，底层是通过链表来实现的；
将插入数据的一端称为队尾，删除数据的一端称为对头。
如下图所示：

队列特性：

队列遵循先进先出的原则，(First In First Out) ；
大神比喻：吃进去，拉出来

1.2 队列的使用

常用方法：

• boolean offer(E e)：将元素 e入队列
• E poll()：出队列
• E peek()：获取队头元素
• int size() ： 获取队列中有效元素个数
• boolean isEmpty()： 检测队列是否为空

package day20211018;import java.util.LinkedList;
import java.util.Queue;public class TestQueue {//测试队列public static void main(String[] args) {Queue q=new LinkedList();//入队列：1 2 3 4q.offer(1);q.offer(2);q.offer(3);q.offer(4);System.out.println(q);  //[1, 2, 3, 4]//获取队头元素System.out.println(q.peek()); //1//获取队列中元素的个数System.out.println(q.size()); //4//出队头2个元素q.poll();q.poll();System.out.println(q); //[3, 4]//判断队列是否为空if(q.isEmpty()) {System.out.println("队为空");}else{System.out.println("队不为空");}}
}

2. 模拟实现队列

package day20211023;//模拟实现队列--Queue
public class Queue <E>{public static class ListNode<E>{E value;ListNode<E> next;ListNode<E> prev;public ListNode(E val){this.value = val;}}ListNode<E> first; //标记表示队头元素ListNode<E> last; // 标记队尾元素int size=0; //队列中有效元素的个数//入队列--offerpublic boolean offer(E e){ListNode<E> newNode=new ListNode<>(e);if(first==null){//队列为空first=newNode;//last=newNode;}else{//队列不为空last.next=newNode;//last=newNode;}last=newNode;size++;return true;}//出队列-poll//实质：删除队头元素public E poll() {if(0 == size){return null;}ListNode<E> delNode = first;first = first.next;if(null == first){last = null;}size--;return delNode.value;}//获取队头元素public E peek() {if (first == null) {//说明队列中没有元素return null;}return first.value;}//获取有效元素的个数public int size(){return size;}// 判空public boolean isEmpty(){return first==null;}public static void main(String[] args) {Queue<Integer> q=new Queue<>();//测试入队列 1 2 3 4 5q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5);System.out.println(q.size()); //5System.out.println(q.peek()); //1//测试出队列q.poll();q.poll();q.poll();System.out.println(q.size()); //2System.out.println(q.peek()); //4//测试判空if(q.isEmpty()){System.out.println("队列为空");}else{System.out.println("队列不为空");}}
}

思考：

在 Java 中，队列是采用链表来实现的，如果采用连续空间是否能满足队列的所有操作的时间复杂度都为O(1)?

分析如下：

假设借助数组的一段连续空间来实现入队列、出队列和获取队头元素的的操作；
如下图所示：入队列：1 2 3 4 5 6 这 6 个元素，直接插入尾部即可，时间复杂度为O(1);

出队列时：由于队列具有先进先出的特性，因此只有该元素成为队头元素才可以实现出队列；

出队列方式一：

保持front不动，将后面5个元素整体往前搬移一个位置；再将rear往前移动一个位置；
注意：虽然这样可以实现出队列，但当有N个元素时，就需要搬移N-1次，所以时间复杂度为O(N)，不满足要求；

如下图所示：

那么，要保证队列的所有操作中，时间复杂度均为O(1)，要怎么实现呢？

方式二：

出队列时，让front往后移动一步即可实现；
原因：front每次标记的都是队头元素，因此当front往后移动时，就相当于将前面的元素移出队列了；
而且确保了出队列的时间复杂度为O(1)，但采用该种方式时，又会导致假溢出的现象。

假溢出：当想要再该空间进行数据插入时，由于rear已经指向了空间的末尾，因此不能插入。但实际上前面有三个元素已经出队列了，这部分是有剩余空间的，只是不能被使用而已。把这种现象称为队列的假溢出；

针对上面使用连续空间所出现的假溢出问题，提出了循环队列

3.循环队列

循环队列：就是将队列存储空间的最后一个位置绕回到第一个位置，形成逻辑上的环状空间，以便实现队列的循环使用，循环队列也是一种线性的数据结构，其操作表现是基于 FIFO（先进先出）的原则；如下图所示：

如上环形队列图所示：

入队列时：
将元素放在rear队尾的位置，然后将rear往后移动一步；
出队列时：front往后移动一步即可；

在上图中的5号位置再插入一个元素时，rear就指向了front的位置，那此时，如何判断队列是空还是满呢？

判断循环队列是空还是满的**三种方式**：

• 使用 count 来计数

当count为0 时，循环队列就是空的；
当count为arr.length时，循环队列为满；

• 少存储一个元素

当front等于rear时，队列为空；
当rear加1等于rear时，队列就为满
注意：当队列中的元素存储到最后一个位置时，再插入元素就回到了起始位置，所以队列满时判断条件为：

     (rear+1）% arr.length==front

• 设置标志位

起始状态，将flag设为false
入队列时，rear往下一个位置移动，同时flag=true；
出队列时：front往下一个位置移动，同时flag=false；
当front等于rear &&flag等于false时，队列为空；
当front等于rear &&flag等于true时，队列为满；

如何实现一个循环队列？

循环队列实现代码:

class MyCircularQueue {int[] array;int front=0;  //标记队头元素int rear=0;   //标记队尾元素int count=0;  //判断队列是满还是空int N; //队列的长度public MyCircularQueue(int k) {array=new int[k];N=k;}//入队列public boolean enQueue(int value) {if(isFull()){return false;}array[rear]=value;rear++;if(rear==N){rear=0;}count++;return true;}//出队列public boolean deQueue() {if(isEmpty()){return false;}front++;front %= N;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];}public boolean isEmpty() {return 0==count;}public boolean isFull() {return count==array.length;}
}

4. 双端队列

双端队列（Deque）是指允许两端都可以进行入队和出队操作的队列，底层也是通过 LinkedList 实现的； 集合框架中的结构图如下图所示：

常见队列笔试题

（很重要哦）

注：下面三道题点开蓝色链接查看原题 ！！！

第一题：队列实现栈

问题描述：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false

解题思路：

使用两个队列q1 和 q2 ，q1 用来存储元素，q2 用来作为入栈的辅助队列；
入栈时：先将元素入队到q2中，然后再将q1的全部元素出队到q2中，再将两个队列中的元素互换，则q1的前端元素和后端为栈顶和栈底元素；
由于每次入栈操作都确保 q1 的前端元素为栈顶元素，因此，出栈操作只需要移除 q1 的前端元素并返回即可。
获取栈顶元素：只需要获得q1的前端元素并返回；
判断栈空：只需要q1是否为空；

class MyStack {//定义两个队列q1,q2，一个用来存储元素，一个用作为辅助队列Queue<Integer> q1=new LinkedList<>();  Queue<Integer> q2=new LinkedList<>(); public MyStack() {}//入栈public void push(int x) {q2.offer(x);while (!q1.isEmpty()) {q2.offer(q1.poll());}Queue<Integer> temp = q1;q1 = q2;q2 = temp;}//出栈public int pop() {return q1.poll();}//获取栈顶元素public int top() {return q1.peek();}public boolean empty() {return q1.isEmpty();}
}

第二题：用栈实现队列

问题描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

解题思路：

使用两个栈s1和s2，s1用来模拟入队列，s2用来模拟出队列；
入队列时：直接将元素放入s1中；
出队列时：如果s2是空的，将s1中的所有元素导入到s2中，将s2栈顶元素删除；
获取队头元素：如果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()){//将s1中的所有元素导入到s2中while(s1.size()>0){s2.push(s1.pop());  }  }return s2.pop();}public int peek() {if(s2.empty()){while(s1.size()>0){s2.push(s1.pop());}}return s2.peek();}public boolean empty() {return s1.isEmpty() && s2.isEmpty(); }
}

第三题：实现一个最小栈

问题描述：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) —— 将元素 x 推入栈中
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。
• getMin() —— 检索栈中的最小元素。

解题思路：

入栈时：

当S2不空时，将元素在S1，S2中各放入一份；
若S2 不空，就将 val 与 S2 栈顶元素进行比较，当val小于等于S2的栈顶元素时，将val 在S1 和S2中个放入一份，当val大于S2的栈顶元素时，将val 放入S1中；

出栈时：

当S1 和S2栈顶元素相等时，S2出栈；
S1每次都要出栈一个元素；

栈顶元素就在S1中

最小值就在S2中

class MinStack {Stack<Integer> s1=new Stack<>();Stack<Integer> s2=new Stack<>();public MinStack() {}//入栈public void push(int val) {if(s2.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();}  
}