【数据结构Java版】Queue队列的活用

清疚 2024-04-01 09:17 78阅读 0赞

**目录**

一、队列的定义

二、队列的使用

（1）主要方法

（2）实例演示

（3）注意事项

三、队列的模拟实现

四、循环队列

（1）循环队列定义

（2）循环队列的表示

1.数组循环的方法

2.区分空满的方法

（3）循环队列的实现

五、双端队列

六、队列相关练习题

--------------------

## 一、队列的定义 ##

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾（Tail/Rear）

出队列：进行删除操作的一端称为队头（Head/Front）

查看队头元素：peek

队列：java中，队列的含义被淡化了，队列使用Queue接口来表示。

java.util.Queue继承Collection(接口)

接口与类关系示意图：

![658a5a8361b14b179fe542a3b41c8635.png][]

## 二、队列的使用 ##

### （1）主要方法 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="text-align:center;"><strong>方法</strong></td> 
   <td style="text-align:center;"><strong>功能</strong></td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">boolean offer(E e)</td> 
   <td style="text-align:center;">入队列</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">E poll()</td> 
   <td style="text-align:center;">出队列</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">peek()</td> 
   <td style="text-align:center;">获取队头元素</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">int size()</td> 
   <td style="text-align:center;">获取队列中有效元素个数</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">boolean isEmpty()</td> 
   <td style="text-align:center;">检测队列是否为空</td> 
  </tr> 
 </tbody> 
</table>

### （2）实例演示 ###

import java.util.LinkedList;
    import java.util.Queue;
    
    public class QueueDemo {
        public static void main1(String[] args) {
            Queue <Integer> queue =new LinkedList<>();
            queue.offer(11);
            queue.offer(23);//从队尾入队列
            System.out.println(queue.peek());//查看队头元素，11
            System.out.println(queue.size());//查看元素个数，2
            System.out.println(queue.poll());//从队头出队列，并将删除元素返回，11
            if(queue.isEmpty()){//判断队列是否为空
                System.out.println("队列为空");
            }else{
                System.out.println(queue.size());
            }
        }
    }

### ![dfc2098c111446b2a4bf73baa391cd55.png][] （3）注意事项 ###

1.入队列：基本不会报错，返回true（当队列满时，入队列会出错。当我们使用LinkedList链表实现队列时。原则上人为链表是无限长，不会满。基本遇不到入队列错误。）

2.出队列：当返回值是null时，代表队列中没有元素。

3.查看队首元素：当返回值是null时，代表队列中没有元素。

## 三、队列的模拟实现 ##

/*
    元素类型是 long 类型
     */
    public class Queue {
        static class Node {
            long value;
            Node next;
    
            Node(long value) {
                this.value = value;
                this.next = null;
            }
        }
    
        // 为了方便头删 + 尾插，记录头节点 + 尾结点
        private Node head;
        private Node last;
        private int size;
    
        public Queue() {
            this.head = this.last = null;
            this.size = 0;
        }
    
        public void offer(long e) {
            // 放入队列 -> 尾插
            Node node = new Node(e);
            if (this.last != null) {
                this.last.next = node;
                this.last = node;
            } else {
                this.head = this.last = node;
            }
            this.size++;
        }
    
        public long poll() {
            if (size == 0) {
                throw new RuntimeException("队列是空的");
            }
    
            // 记录当前队首元素
            long e = this.head.value;
            // 进行头删
            this.head = this.head.next;
            if (this.head == null) {
                this.last = null;
            }
            size--;
    
            return e;
        }
    
        public long peek() {
            if (size == 0) {
                throw new RuntimeException("队列是空的");
            }
    
            return this.head.value;
        }
    
        public int size() {
            return this.size;
        }
    
        public boolean isEmpty() {
            return size() != 0;
        }
    }

## 四、循环队列 ##

### （1）循环队列定义 ###

为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。

假溢出：系统作为队列用的存储区还没有满,但队列却发生了溢出,我们把这种现象称为"假溢出"。

### ![477a314cebdf460c89258cabc3b36dc3.png][]（2）循环队列的表示 ###

#### 1.数组循环的方法 ####

a. 下标**最后再往后**(offset 小于 array.length): **index = (index + offset) % array.length**

![d9e74430985a4cdfa52817766f7dfe7b.png][]  
b. 下标**最前再往前**(offset 小于 array.length): **index = (index + array.length - offset) % array.length**

![18570596594c4a3ab389e12ebb07ffd6.png][]

#### 2.区分空满的方法 ####

理论上解决的办法：

1. 通过添加 size 属性记  
2. 保留一个位置  
3. 使用标记

**队满：rear+1=front**

**队空：rear=front**

![57b1e4474a634da0a72d5ef7feddb1ed.png][]

### （3）循环队列的实现 ###

> [622. 设计循环队列][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

class MyCircularQueue {
        private int []array;
        private int size=0;
        private int frontIndex;
        private int rearIndex;
    
        public MyCircularQueue(int k) {
            array=new int[k];
        }
        
        public boolean enQueue(int value) {
            if(isFull()){
                return false;
            }
            array[rearIndex]=value;
            rearIndex=(rearIndex+1)%array.length;
            size++;
            return true;
        }
        
        public boolean deQueue() {
            if(isEmpty()){
                return false;
            }
            frontIndex+=1;
            if(frontIndex==array.length){
                frontIndex=0;
            }
            size--;
            return true;
    
        }
        
        public int Front() {
            if(isEmpty()){
                return -1;
            }
            return array[frontIndex];
        }
        
        public int Rear() {
             if(isEmpty()){
                return -1;
            }
            int index=rearIndex;
            index=(rearIndex-1+array.length)%array.length;
            return array[index];
        }
        
        public boolean isEmpty() {
            return size==0;
        }
        
        public boolean isFull() {
            return size==array.length;
        }
    }

![4478a8c6b77043bca3e7dcbf59a5f7fd.png][]

## 五、双端队列 ##

双端队列（deque）是指允许两端都可以进行入队和出队操作的队列，deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。Deque是一个接口，使用时必须创建LinkedList的对象。![bd42f7c7497b4b9080ea24f0db7eca35.png][]

![0625571ccff04f9ba4269619c5701bc8.png][]

## 六、队列相关练习题 ##

> [225. 用队列实现栈][225.]
> 
> 难度简单632
> 
> 请你仅使用两个队列实现一个后入先出（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（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
> 
> **示例：**
> 
>     输入：
>     ["MyStack", "push", "push", "top", "pop", "empty"]
>     [[], [1], [2], [], [], []]
>     输出：
>     [null, null, null, 2, 2, false]
>     
>     解释：
>     MyStack myStack = new MyStack();
>     myStack.push(1);
>     myStack.push(2);
>     myStack.top(); // 返回 2
>     myStack.pop(); // 返回 2
>     myStack.empty(); // 返回 False

class MyStack {
        private final Queue<Integer> queue1=new LinkedList<>();
        private final Queue<Integer> queue2=new LinkedList<>();
        private Queue<Integer> 存元素的队列=queue1;
        private Queue<Integer> 辅助队列=queue2;
        public MyStack() {
    
        }
        
        public void push(int x) {
            存元素的队列.offer(x);
        }
        
        public int pop() {
            int size=存元素的队列.size();
            for(int i=0;i<size-1;i++){
                辅助队列.offer(存元素的队列.poll());
            }
            int e=存元素的队列.poll();
            Queue<Integer> tmp=辅助队列;
            辅助队列=存元素的队列;
            存元素的队列=tmp;
            return e;
        }
        
        public int top() {
            int size=存元素的队列.size();
            for(int i=0;i<size-1;i++){
                辅助队列.offer(存元素的队列.poll());
            }
            int e=存元素的队列.poll();
            Queue<Integer> tmp=辅助队列;
            辅助队列=存元素的队列;
            存元素的队列=tmp;
            存元素的队列.offer(e);
            return e;
        }
        
        public boolean empty() {
            return 存元素的队列.isEmpty();
        }
    }

![3734820ac51a423ab22c91d60d2eede0.png][]

--------------------

![6751f0f16bf74056a404762421a5050a.png][]

[658a5a8361b14b179fe542a3b41c8635.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/7e3d0342ada74d57bead9db14949993c.png
[dfc2098c111446b2a4bf73baa391cd55.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/e3cd2899cf5c413181ec1844774ca7fc.png
[477a314cebdf460c89258cabc3b36dc3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9023e13dc30d4bb79d044e2c4d76a3f6.png
[d9e74430985a4cdfa52817766f7dfe7b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d7d16cda1ddd468e853f9e63ef5c225e.png
[18570596594c4a3ab389e12ebb07ffd6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/207e9a08768b44abaee46b274d1d9264.png
[57b1e4474a634da0a72d5ef7feddb1ed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/10d276f1ad5f4baf9b017c3557f6aecf.png
[622.]: https://leetcode.cn/problems/design-circular-queue/
[4478a8c6b77043bca3e7dcbf59a5f7fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/c80643913e5d4aa68335a68d5c131f55.png
[bd42f7c7497b4b9080ea24f0db7eca35.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9653409db704417dba519c221b31c2e8.png
[0625571ccff04f9ba4269619c5701bc8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/cb93e9827b3f41e0b62b8ab14e1c6be4.png
[225.]: https://leetcode.cn/problems/implement-stack-using-queues/
[3734820ac51a423ab22c91d60d2eede0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/027332506707487bb801e02b4bae6a43.png
[6751f0f16bf74056a404762421a5050a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f8a291d2b47b4724b6cc2d352e90e2a4.png