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

这篇具有很好参考价值的文章主要介绍了【数据结构】详解环形队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🌏引言

队列的操作算法是笔试面试中较为常见的题目。
本文将着重介绍平时面试中常见的关于队列的应用题目,马上要进行秋招了。希望对你们有帮助 _😀
【数据结构】详解环形队列,数据结构,数据结构,java,队列,开发语言

🍀循环队列

【数据结构】详解环形队列,数据结构,数据结构,java,队列,开发语言

🐱‍👤题目描述

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

🐱‍👓示例:

【数据结构】详解环形队列,数据结构,数据结构,java,队列,开发语言

🐱‍🐉提示

【数据结构】详解环形队列,数据结构,数据结构,java,队列,开发语言

🐱‍🏍思路解析:

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

  • 数组的下标如何实现循环

  • 如何判别数组是否满了

📌数组下标循环的小技巧

  1. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length
    【数据结构】详解环形队列,数据结构,数据结构,java,队列,开发语言
  2. 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length
    【数据结构】详解环形队列,数据结构,数据结构,java,队列,开发语言

📌区分空与满

有三个方法:

  1. 通过添加 size 属性记录

  2. 保留一个位置

  3. 使用标记

博主这里采用第二个方法,如下图所示:
【数据结构】详解环形队列,数据结构,数据结构,java,队列,开发语言

🚩创建队列

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

代码实现如下:

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

⭕总结

关于《【数据结构】详解环形队列》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!文章来源地址https://www.toymoban.com/news/detail-690464.html

到了这里,关于【数据结构】详解环形队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——循环队列详解

    目录 一、循环队列的定义 二、 循环队列的基本操作 三、循环队列的实现  1、循环队列的定义 2、循环队列的初始化  3、循环队列出队  4、循环队列入队  5、队列判空 6、 队列判满 7、取队头元素 8、输出队列  9、求队列长度  四、完整代码  五、小结  六、参考文献 一、

    2024年02月04日
    浏览(44)
  • 数据结构:队列Queue详解

    队列 :只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表。进行插入操作的一端称为 队尾 ,删除操作的一端称 队头 。 入队列 :进行插入操作的一端称为 队尾 。 出队列 :进行删除操作的一端称为 队头 。 在 Java 中, Queue是个接口,底层是通过链表

    2024年02月11日
    浏览(37)
  • 数据结构之队列的详解

    队列是一种先入先出(FIFO)的线性表数据结构 添加和删除操作只在表的两端进行,一端为队头,另一端为队尾 添加操作在队尾进行,称为入队或进队,删除操作在队头进行,称为出队 队列的图示 java内部的api 可以使用数组或链表实现队列 使用数组实现时,需要维护两个指针front和rea

    2024年02月03日
    浏览(34)
  • 数据结构之队列详解(包含例题)

    队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。 我们可以用 单链表模拟 实现顺序队列。 队列采

    2024年02月13日
    浏览(42)
  • 【数据结构】C语言队列(详解)

    前言: 💥🎈个人主页:​​​​​​Dream_Chaser~ 🎈💥 ✨✨专栏:http://t.csdn.cn/oXkBa ⛳⛳本篇内容:c语言数据结构--C语言实现队列 目录 一.队列概念及结构 1.1队列的概念 1.2队列的结构 二.队列的实现 2.1头文件 2.2链式队列的结构定义 2.3队列接口的定义 2.4初始化队列 2.5判断队列

    2024年02月10日
    浏览(44)
  • C++数据结构之队列详解

    队头填充进四个元素 此时思考一个问题,当删除元素时(元素出队列时)会出现假饱和的情况,如上图m_data[0]和m_data[1]再进行出队列操作之后,这两个位置可以容纳新的元素,但m_rear没有回到原本的m_data[0]位置,因此需要引入一个新的队列结构,环形队列,m_rear这个位置可以

    2024年02月05日
    浏览(41)
  • 数据结构——优先队列c++详解

    百度百科定义 优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.在最小优先队列(min priority queue)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;对于最大优先队列(max priority queue),查找操

    2024年02月09日
    浏览(39)
  • 【数据结构】队列---C语言版(详解!!!)

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

    2024年02月10日
    浏览(50)
  • 数据结构之栈与队列详解

    栈和队列是一种特殊的线性结构,他与之前学的线性结构不同,栈和队列是拥有一种特殊规则的线性结构,虽然它是用数组或者链表实现,但是只有符合这种规则才能被称作栈或者队列 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和

    2024年01月16日
    浏览(44)
  • 【算法与数据结构】队列的实现详解

    队列的概念: 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 新添加的元素添加到队尾,只能从队头取出元素。 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头 队列特征如

    2024年04月13日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包