⭐️前言⭐️

本篇文章介绍与栈比较相像的另一种线性数据结构——队列（Queue），它与栈的数据操作不同。

博客主页： 【如风暖阳】
精品Java专栏【JavaSE】、【备战蓝桥】、【JavaEE初阶】、【MySQL】、【数据结构】
欢迎点赞 收藏 ⭐留言评论 私信必回哟

本文由 【如风暖阳】 原创，首发于 CSDN

博主将持续更新学习记录收获，友友们有任何问题可以在评论区留言

博客中涉及源码及博主日常练习代码均已上传码云(gitee)、GitHub

Queue——队列

1.概念

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特性。

入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

2.队列的使用

注意：在Java中，Queue是个接口，所以在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口

代码实例：

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());//1System.out.println(queue.poll());//1System.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;elsehead=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方法返回链表头，就是栈的栈顶，也就是队列的队头。

5.经典面试题

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();}}

⚡️最后的话⚡️

总结不易，希望uu们不要吝啬你们的哟(＾Ｕ＾)ノ~ＹＯ！！如有问题，欢迎评论区批评指正