系列文章目录

集合及数据结构第八节（下）———— 队列(Queue)、队列的模拟实现和练习

队列(Queue)、队列的模拟实现和练习

1. 队列的概念
2. 队列的使用
3. 队列模拟实现
4. 循环队列
5. 双端队列
6. 练习题

---

---

一、队列(Queue)

1.队列的概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First
In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）

2.队列的使用（ * * ）

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

java">import java.util.LinkedList;
import java.util.Queue;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.size());System.out.println(q.peek()); // 获取队头元素q.poll();System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());}}

3.队列模拟实现（ * * * ）

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有
两种：顺序结构 和 链式结构。而队列的实现使用链式结构更好。

定义接口

java">public interface Iquque {boolean offer(int val);//入队列int poll();//出队列int peek();//获取队头元素int size();//获取队列中有效元素个数boolean empty();//检测队列是否为空
}```
### <font color = "golden yellow'"> 定义队列的内部类</font>```javastatic class ListNode {//将节点定义成内部类public int val;//数据域public ListNode next;//后驱节点（引用类型）public  ListNode prev;//前驱节点public ListNode(int val) {this.val = val;//没有初始化next默认为null（因为next是引用数据类型）}}public ListNode head;//头节点public ListNode last;//尾节点public int usedsize;//有效节点个数

接口的实现

入队列

思路：

第一次插入时head和last都指向这个节点

代码实现：

java">    public boolean offer(int val) {//入队列ListNode node = new ListNode(val);//创建一个node节点用来存放插入的数据if(head == null){//插入第一个数据this.head = node;this.last = node;}else {//有其他节点，进行尾插last.next = node;//先绑定后面更安全node.prev = this.last;this.last = node;}usedsize++;return true;//插入成功}

出队列

java">public class QueueEmptyWrong extends RuntimeException{public QueueEmptyWrong(String message){super(message);}
}

java">    public int poll() {//出队列if (head == null){//队列为空，抛出异常throw new QueueEmptyWrong("队列是空的，不能进行出队列");}int retVal = head.val;//用来存放这个节点的val值if (head.next == null){//只有一个节点head = null;last = null;return retVal;//返回这个节点的val值}//不止一个节点时head = head.next;//头节点不在指向第一个节点（指向第二个节点）head.prev = null;//第二个节点的前驱置为null(第一个节点出队列前)usedsize--;return retVal;//返回这个节点的val值}

获取队头元素

java">    public int peek() {//获取队头元素if (head == null){//队列为空，抛出异常throw new QueueEmptyWrong("队列是空的，不能进行出队列");}return head.val;//返回头节点的val值}

获取队列中有效元素个数

java">    public int size() {//获取队列中有效元素个数return usedsize;}

获取队头元素

java">    public boolean empty() {//检测队列是否为空return head == null;}

4.循环队列

实际中有时还会使用一种队列叫循环队列。如操作系统中讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。

如何区分空与满

1. 通过添加usedsize 属性记录
2. 浪费一个空间表示满

3. 使用标记

数组下标循环的小技巧

1. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length
   
2. 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length
   

设计循环队列

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，能使用这些空间去存储新的值。

队列的实现应该支持如下操作：

• MyCircularQueue(k): 构造器，设置队列长度为 k 。
• Front: 从队首获取元素。如果队列为空，返回 -1 。
• Rear: 获取队尾元素。如果队列为空，返回 -1 。
• enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
• deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
• isEmpty(): 检查循环队列是否为空。
• isFull(): 检查循环队列是否已满。

java">class MyCircularQueue {public int[] elem;public int front;//队头public int rear; //队尾public MyCircularQueue(int k) {//构造器，设置队列长度为 k 。elem = new int[k + 1];//实际能存放的数据只有k个}public boolean enQueue(int value) {//向循环队列插入一个元素。如果成功插入则返回真if (isFull()){//如果满了就不能放了return false;}//没有满就要插入元素elem[rear] = value;rear = (rear + 1) % elem.length;return true;}public boolean deQueue() {//从循环队列中删除一个元素。如果成功删除则返回真if (isEmpty()){//如果队列是空的就不能删除return false;}front = (front + 1) % elem.length;return true;}public int Front() {//从队首获取元素。如果队列为空，返回 -1if (isEmpty()){//如果队列是空的返回-1return -1;}return elem[front];}public int Rear() {//获取队尾元素。如果队列为空，返回 -1if (isEmpty()){//如果队列是空的返回-1return -1;}int index = (rear == 0) ? elem.length - 1 : rear -1;//当队尾指向0下标的位置时return elem[index];                                     // index队尾对应 下标就是elem.length - 1,否则直接就是rear - 1}public boolean isEmpty() {//检查循环队列是否为空。return front == rear;//当front 和 rear相等时为空}public boolean isFull() {//检查循环队列是否已满return (rear + 1) % elem.length == front;}
}

5.双端队列 (Deque)

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

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

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

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

二、练习题

1.用队列实现栈

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

实现 MyStack 类：

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

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty
这些操作。 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 ,只要是标准的队列操作即可。

思路：

1. 创建两个队列。入栈的时候，哪个队列不为空放到哪个队列里（两个都是空的指定放到第一个里面）
2. 出栈的时候哪个不为空出哪个（出size - 1 个元素放到第二个、队列里，再出第一个队列的元素）
3. 当两个队列同时是空的，模拟的栈就是空的

代码实现：

java">class MyStack {private Queue<Integer> queue1;private Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {//将元素 x 压入栈顶if (!queue1.isEmpty()){//第一个队列不为空,放进第一个队列queue1.offer(x);} else if (!queue2.isEmpty()) {//第二个队列不为空,放进第二个队列queue2.offer(x);}else {//两个都是空的指定放到第一个里面queue1.offer(x);}}public int pop() {// 移除并返回栈顶元素if (empty()) {//当两个队列都是是空的,返回-(错误)return -1;}if (!queue1.isEmpty()){//第一个队列不为空,出size - 1个元素到queue2中int size = queue1.size();for (int i = 0; i < size - 1; i++) {int x = queue1.poll();//弹出第size - 1个元素放到x里面queue2.offer(x);//存到queue2里面}return queue1.poll();//再出第一个队列的元素} else  {//第二个队列不为空,出size - 1个元素到queue1中int size = queue2.size();for (int i = 0; i < size - 1; i++) {int x = queue2.poll();//弹出第size - 1个元素放到x里面queue1.offer(x);//存到queue1里面}return queue2.poll();//再出第二个队列的元素}}public int top() {//返回栈顶元素。if (empty()) {//当两个队列都是是空的,返回-(错误)return -1;}if (!queue1.isEmpty()){//第一个队列不为空,出size 个元素到queue2中int size = queue1.size();int x = -1;for (int i = 0; i < size ; i++) {x = queue1.poll();//弹出第size 个元素放到x里面queue2.offer(x);//存到queue2里面}return x;//返回队列最后的元素（栈顶的元素）} else  {//第二个队列不为空,出size 个元素到queue1中int size = queue2.size();int x = -1;for (int i = 0; i < size ; i++) {x = queue2.poll();//弹出第size 个元素放到x里面queue1.offer(x);//存到queue1里面}return x;//返回队列最后的元素（栈顶的元素）}}public boolean empty() {//如果栈是空的，返回 true ；否则，返回 falsereturn queue1.isEmpty() && queue2.isEmpty();//当两个队列同时是空的，模拟的栈就是空的}
}

2.用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

思路：

• 入队的时候，都放到第一个栈里。
  
• 出队的时候，把第一个栈的元素移到第二个栈中，然后再出第二个栈中的元素。
• List item

代码实现：

java">package queuedemo;import java.util.Stack;class MyQueue {private Stack<Integer> s1;//第一个栈private Stack<Integer> s2;//第二个栈public MyQueue() {s1 = new Stack<>();//实例化s1s2 = new Stack<>();//实例化s2}public void push(int x) {// 将元素 x 推到队列的末尾s1.push(x);}public int pop() {//从队列的开头移除并返回元素if (empty()){//如果队列为空，返回-1return -1;}if (s2.empty()){//当s2为空的时候把s1的元素移到s2里（当s2不为空的时候先把s2出完）while (!s1.empty()){s2.push(s1.pop());}}return s2.pop();}public int peek() {//返回队列开头的元素if (empty()){//如果队列为空，返回-1return -1;}if (s2.empty()){//当s2为空的时候把s1的元素移到s2里while (!s1.empty()){s2.push(s1.pop());}}return s2.peek();}public boolean empty() {//如果队列为空，返回 true ；否则，返回 falsereturn s1.empty() && s2.empty();}
}