循环队列来了解一下!!

简介: 循环队列来了解一下!!

笔者在之前的一篇文章,详细的介绍了:队列之单向链表与双向链表的模拟实现:https://blog.csdn.net/weixin_64308540/article/details/128742090?spm=1001.2014.3001.5502 感兴趣的各位老铁,可以参考一下啦!

下面进入循环队列的讲解部分:

对于队列,在这个之前我们就已经知道:需要用数组来实现!!数组!

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

当我们给其下标的时候:

假设:我们在里面存储数据的时候:

每次存储一个数据,那么rear就往后走一步!当这个情况下:

  1. rear从7下标如何到0下标??(怎么过去?)
  2. 假设rear从7下标已经到0下标,那么此时,到底是满了?还是没满??这也是一个值得思考的问题!!
  3. 需要注意以下的这种情况:

在这种情况下:当我们一边存储,一边删除,那么就会出现,不是在0下标相遇的情况!因此,我们需要注意:这种情况下,如何判断循环列表是否已经存储满了呢??

解决方案:

对于问题1:我们可以用:rear=(rear+1)%length,length表示数组长度!这样就可以实现数组下标的跨越!

对于问题2:我们可以定义usedSize记录存储的有效数据,通过usedSize与数组的长度相比,那么,我们就可以清晰的得出,循环列表是否存储满的结论!

对于如何判断循环列表满的情况:我们可以用牺牲一个空间来表示满!!

在这个思路过程中,我们可以让rear先走一步,看看是否与front相遇,若相遇(上图的情况)则为满!在上图中:我们牺牲rear所对应的空间来表示满!!

经过上述的讲解,那么,我们已经知道了循环列表的操作,及其思路,接下来我们就可以:设计循环队列了!:622. 设计循环队列 - 力扣(LeetCode)

622. 设计循环队列

难度中等440收藏分享切换为英文接收动态反馈

设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 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

提示:

  • 所有的值都在 0 至 1000 的范围内;
  • 操作数将在 1 至 1000 的范围内;
  • 请不要使用内置的队列库。

经过上述 的题目分析,我们可以写出一下的简单代码:

首先,根据题目中的代码,我们定义了一个:MyCircularQueue的类!

然后我们开始进行代码的准备阶段:

private int[] elem;//数组
    private int front;//表示列表的头
    private int rear;//表示列表的尾

在之前的分析中,我们知道,循环队列的底层是一个数组,因此,我们第一了一个数组,一个front表示列表的头,rear表示列表的尾!!

根据构造器来定义数组的长度为k,但是,由于我们所用的是:浪费一个空间来表示满的情况:因此我们需要多定义一个数组的长度:k+1

//构造器,设置队列的长度为k
    public MyCircularQueue(int k){
        //如果是浪费空间,这里必须多加一个!
        this.elem=new int[k+1];
    }
  1. 入队列:向循环列表中插入一个元素,如果插入成功则返回true
//入队列:向循环列表中插入一个元素,如果插入成功则返回true
    public boolean enQueue(int value){
        //检查队列是否为满??
        if (isFull()){
            return false;//在不扩容的情况下,满了,就不能入!
        }
        //在队列不满的情况下
        elem[rear]=value;//存放数据
        rear=(rear+1)%elem.length;//确保循环
        return true;
    }

在这个里面,我们用了一个检查队列是否为满的判断,所以:……

//检查循环队列是否为满?
    public boolean isFull(){
        //第一种写法
        if ((rear+1)%elem.length==front){
            return true;
        }
        return false;
        //第二种写法:
        //return (rear+1)%elem.length==front;
    }

其实这个第二种的写法,很简单!很简单!

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

对于上述的这个代码,通过front往后走了一步,此时数据还在循环队列里面,但是,由于没有记录下来,所以,便就相当于删除了!

  1. 从队列的队首获取元素,如果队列为空,则返回-1
//从队列的队首获取元素,如果队列为空,则返回-1
    public int Front(){
        if (isFull()) {
            return -1;
        }
        //得到对头元素
        return elem[front];
    }

这个代码很简单,笔者就不再详细的介绍了!

  1. 获取队列的队尾元素,如果队列为空,则返回-1
//获取队列的队尾元素,如果队列为空,则返回-1
    public int Rear(){
        if (isEmpty()){
            return -1;
        }
        //得到队尾元素
        int index=(rear==0)?elem.length-1 :rear-1;
        return elem[index];
    }

对于这个问题,我们需要思考的是:rear在0下标的时候,若直接返回elem[rear-1],可能会造成越界!!因此我们才有着上述的: int index=(rear==0)?elem.length-1 :rear-1; return elem[index];

在上述的过程中,我们使用了检查数组是否为空的情况:isEmpty()

//检查数组是否为空
    public boolean isEmpty(){
        return front==rear;//相遇
    }

上述便是我们的全部思路,因此,我们的整体代码为:

public class MyCircularQueue {
    private int[] elem;//数组
    private int front;//表示列表的头
    private int rear;//表示列表的尾
    //构造器,设置队列的长度为k
    public MyCircularQueue(int k) {
        //如果是浪费空间,这里必须多加一个!
        this.elem = new int[k + 1];
    }
    //入队列:向循环列表中插入一个元素,如果插入成功则返回true
    public boolean enQueue(int value) {
        //检查队列是否为满??
        if (isFull()) {
            return false;//在不扩容的情况下,满了,就不能入!
        }
        //在队列不满的情况下
        elem[rear] = value;
        rear = (rear + 1) % elem.length;
        return true;
    }
    //检查循环队列是否为满?
    public boolean isFull() {
        //第一种写法
        if ((rear + 1) % elem.length == front) {
            return true;
        }
        return false;
        //第二种写法:
        //return (rear+1)%elem.length==front;
    }
    //从循环队列中删除一个元素,如果成功删除,则返回true
    public boolean deQueue(){
        if (isFull()){
            return false;
        }
        front=(front+1)% elem.length;
        return true;
    }
    //从队列的队首获取元素,如果队列为空,则返回-1
    public int Front(){
        if (isFull()) {
            return -1;
        }
        //得到对头元素
        return elem[front];
    }
    //获取队列的队尾元素,如果队列为空,则返回-1
    public int Rear(){
        if (isEmpty()){
            return -1;
        }
        //得到队尾元素
        int index=(rear==0)?elem.length-1 :rear-1;
        return elem[index];
    }
    //检查数组是否为空
    public boolean isEmpty(){
        return front==rear;//相遇
    }
}

若有不懂得地方,可以私聊我一下!!

相关文章
|
6月前
链式队列的实现
链式队列的实现
44 0
|
6月前
|
C++
数据结构(顺序队列 循环队列
数据结构(顺序队列 循环队列
26 0
|
6月前
|
存储
循环队列的实现(附完整代码)
循环队列的实现(附完整代码)
66 1
|
机器学习/深度学习
循环队列的实现
循环队列的实现
|
6月前
循环队列详解
循环队列详解
|
6月前
|
机器学习/深度学习 存储
leetcode:循环队列
leetcode:循环队列
|
6月前
|
存储 缓存 算法
队列的学习(二) 循环队列
队列的学习(二) 循环队列 循环队列是一种基于数组实现的队列,相比于普通队列,它的插入和删除操作更加高效。循环队列可以避免在队列头部删除元素时进行大量的数据搬移操作,实现了队列的“循环利用”。
SWUSTOJ 965: 循环队列
SWUSTOJ 965: 循环队列
110 0
|
存储 缓存 算法
【数据结构】队列(循环队列和链队列)详细讲解各种操作
【数据结构】队列(循环队列和链队列)详细讲解各种操作
890 0
|
机器学习/深度学习 存储 算法
【数据结构与算法】用队列实现栈&&用栈实现队列&&设计循环队列
【数据结构与算法】用队列实现栈&&用栈实现队列&&设计循环队列
【数据结构与算法】用队列实现栈&&用栈实现队列&&设计循环队列