【数据结构】详解环形队列

爱被打了一巴掌 2024-04-17 10:33 60阅读 0赞

#### 文章目录 ####

*  ?引言
 *  ?\[循环队列\](https://leetcode.cn/problems/design-circular-queue/description/)
 *   *  ??题目描述
     *  ??示例：
     *  ??提示
     *  ??思路解析：
     *   *  ?数组下标循环的小技巧
         *  ?区分空与满
         *  ?创建队列
         *  ?判断是否为满
         *  ?检查循环队列是否为空
         *  ?插入元素
         *  ?删除元素
         *  ?从队首获取元素
         *  ?从队尾获取元素
         *  ?完整代码：
 *  ⭕总结

## ?引言 ##

队列的操作算法是笔试面试中较为常见的题目。  
本文将着重介绍平时面试中常见的关于队列的应用题目，马上要进行秋招了。希望对你们有帮助 \_?  
![在这里插入图片描述][94b094fa0d0f42bcac0a437a41e1eff4.png]

## ?[循环队列][Link 1] ##

![在这里插入图片描述][bdb58524f11642d5b2585f3d60f2517a.png]

### ??题目描述 ###

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

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

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

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

class MyCircularQueue {
        
    
        public MyCircularQueue(int k) {
        
    
        }
        
        public boolean enQueue(int value) {
        
    
        }
        
        public boolean deQueue() {
        
    
        }
        
        public int Front() {
        
    
        }
        
        public int Rear() {
        
    
        }
        
        public boolean isEmpty() {
        
    
        }
        
        public boolean isFull() {
        
    
        }
    }
    
    /**
     * 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();
     */

### ??示例： ###

![在这里插入图片描述][8fd34274800a41738823f12af7b817ba.png]

### ??提示 ###

![在这里插入图片描述][ce7475f4bd774bb9ad83e22adc33feb4.png]

### ??思路解析： ###

要解决循环队列的有如下几个难题：

*  数组的下标如何实现循环
 *  如何判别数组是否满了

#### ?数组下标循环的小技巧 ####

1.  下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length  
    ![b937407ba5ca481bb6955858894483d1.png][]
2.  下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length  
    ![在这里插入图片描述][8a5d0da8887743fe910fca84e2b72052.png]

#### ?区分空与满 ####

有三个方法：

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

博主这里采用第二个方法，如下图所示：  
![在这里插入图片描述][06185f9ac72449f0a15ffe91bb117351.png]

#### ?创建队列 ####

由于我们需要浪费一个空间来判断是否为满，随意在构造方法时回多构造一个空间

代码实现如下：

private int[] elem;
        private int front;//表示队列的头
        private int rear;//表示队列的尾
        public MyCircularQueue(int k) {
        
            this.elem = new int[k+1];
        }

#### ?判断是否为满 ####

我们只需要判断队尾的下一个元素是否为队尾就好

由于队列是循环的，所以我们需要利用数组循环下标的技巧来找

代码实现如下：

public boolean isFull() {
        
            return (rear+1)%elem.length == front;
        }

#### ?检查循环队列是否为空 ####

当队尾等于队头时

//检查循环队列是否为空。
        public boolean isEmpty() {
        
            return rear == front;
        }

#### ?插入元素 ####

做法如下：

*  判断是否为满
 *  若为满。返回false
 *  若不为满，则在elem下标为rear处插入该元素
 *  队尾向后走一步，返回true；

代码实现如下：

//向循环队列插入一个元素。如果成功插入则返回真
        public boolean enQueue(int value) {
        
            if(isFull() ) {
        
                return false;
            }
            elem[rear] = value;
            rear = (rear+1)%elem.length;
            return true;
        }

#### ?删除元素 ####

做法如下：

*  判断是否为null
 *  若为null。返回false
 *  若不为null，队首向后走一步，返回true；

实现如下：

//从循环队列中删除一个元素。如果成功删除则返回真。
        public boolean deQueue() {
        
            if(isEmpty() ) {
        
                return false;
            }
            front = (front+1)%elem.length;
            return true;
        }

#### ?从队首获取元素 ####

做法如下：

*  如果队列为空，返回 -1
 *  不为空，返回数组elem下标为fornt的值

代码如下：

//从队首获取元素。如果队列为空，返回 -1 。
        public int Front() {
        
            if(isEmpty() ) {
        
                return -1;
            }
            return elem[front];
        }

#### ?从队尾获取元素 ####

做法如下：

*  如果队列为空，返回-1
 *  不为空，如果为队尾下标为1，返回下标为elem.length-1的元素
 *  下标不为1，返回数组下标为rear-1的值

代码如下：

//从队尾获取元素。如果队列为空，返回 -1 。
        public int Rear() {
        
            if(isEmpty() ) {
        
                return -1;
            }
            if(rear == 0) {
        
                return elem[elem.length-1];
            }
            return elem[rear-1];
        }

#### ?完整代码： ####

class MyCircularQueue {
        
        private int[] elem;
        private int front;//表示队列的头
        private int rear;//表示队列的尾
        public MyCircularQueue(int k) {
        
            this.elem = new int[k+1];
        }
        //向循环队列插入一个元素。如果成功插入则返回真
        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;
        }
        //从队首获取元素。如果队列为空，返回 -1 。
        public int Front() {
        
            if(isEmpty() ) {
        
                return -1;
            }
            return elem[front];
        }
        //从队尾获取元素。如果队列为空，返回 -1 。
        public int Rear() {
        
            if(isEmpty() ) {
        
                return -1;
            }
            if(rear == 0) {
        
                return elem[elem.length-1];
            }
            return elem[rear-1];
        }
        //检查循环队列是否为空。
        public boolean isEmpty() {
        
            return rear == front;
        }
        //判断是否为满
        public boolean isFull() {
        
            return (rear+1)%elem.length == front;
        }
    }

## ⭕总结 ##

关于《【数据结构】详解环形队列》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！

[94b094fa0d0f42bcac0a437a41e1eff4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/35f85dfe306441c583ad0498faee5a0a.png
[Link 1]: https://leetcode.cn/problems/design-circular-queue/description/
[bdb58524f11642d5b2585f3d60f2517a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/e433c861a07843639e311a7e2a66255d.png
[8fd34274800a41738823f12af7b817ba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/99d740ba39c04df8935a750f407e7d92.png
[ce7475f4bd774bb9ad83e22adc33feb4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/281d2c6fa38a4b659708d5827b26c068.png
[b937407ba5ca481bb6955858894483d1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/cf0770efb37e434eb418b4808ed19154.png
[8a5d0da8887743fe910fca84e2b72052.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/e768418e3b014ec0a7f6362818a30df3.png
[06185f9ac72449f0a15ffe91bb117351.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/8e3b1c85be5c4e088f151e1cec49c016.png