[Data structure]队列&环形队列 | 一文带你彻底搞懂队列和环形队列(内附详细图解和代码实现)

这篇具有很好参考价值的文章主要介绍了[Data structure]队列&环形队列 | 一文带你彻底搞懂队列和环形队列(内附详细图解和代码实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

⭐作者介绍:大二本科网络工程专业在读,持续学习Java,努力输出优质文章
⭐作者主页:@逐梦苍穹
⭐所属专栏:数据结构。数据结构专栏主要是在讲解原理的基础上拿Java实现
⭐如果觉得文章写的不错,欢迎点个关注一键三连😉有写的不好的地方也欢迎指正,一同进步😁

1、简介

队列分为两种,一种是简单队列,一种是环形队列

队列是一种常见的数据结构,它是一种线性结构,可以理解为只允许在一端进行插入操作,而在另一端进行删除操作的线性表。在队列中,进行插入操作的一端称为队尾,进行删除操作的一端称为队头。
队列的特点是先进先出,即先插入的元素先被删除。队列可以用于很多场景,比如计算机中的任务调度、打印机任务队列等等。

环形队列是一种特殊的队列,它是在队列的基础上添加了一些限制条件,使得队列可以在固定大小的存储空间下进行循环使用。环形队列可以用数组实现,数组中的元素按照一定的顺序排列,并且当队列头或者队列尾指针到达数组的尾部时,会自动从数组的头部开始重新循环使用。

环形队列的一个好处是,当队列满时,可以通过覆盖队列头部的元素来继续存储新的元素,这样可以使得队列在一定程度上具有循环使用的能力,节省存储空间。但是在使用环形队列时需要注意一些细节问题,比如队列空、队列满、队列大小等等。

2、应用场景

队列和环形队列在计算机科学和工程中有许多应用场景,以下是一些例子:
  1.任务调度:操作系统可以使用队列来实现任务调度,将各个进程放入队列中按照优先级进行调度执行。
  2.消息传递:在消息队列系统中,消息被放入队列中,并按照一定的顺序被处理。
  3.网络通信:网络传输中,消息包可以被组织成队列的形式,以确保它们以正确的顺序被传输和处理。
  4.打印机任务队列:打印机可以使用队列来管理多个打印任务,确保它们按照正确的顺序进行打印。
  5.广度优先搜索算法:广度优先搜索算法可以使用队列来实现,搜索树的每一层节点可以被放入队列中,
   以便按照广度优先的顺序进行搜索。
  6.循环播放音频:在音频播放器中,可以使用环形队列来实现循环播放,确保音频可以以连续的方式进行播放。
  7.缓存:在计算机系统中,缓存可以使用队列来实现,最近使用的数据可以放入队列的队尾,以便快速访问。
总之,队列和环形队列在很多场景中都有着广泛的应用,它们是实现许多计算机科学和工程问题的重要工具。

3、优缺点

队列和环形队列的优缺点如下:

  1. 队列的优点:
    1.1. 先进先出的特性可以确保处理顺序的正确性
    1.2. 简单易用,具有清晰的操作方式
    1.3. 适合于需要按顺序进行处理的场景。
  2. 队列的缺点:
    2.1. 无法在任意位置插入和删除元素,只能在队列的两端进行操作
    2.2. 如果队列的长度未知,可能会导致存储空间的浪费。
  3. 环形队列的优点:
    3.1. 可以循环利用存储空间,节省存储空间
    3.2. 可以快速地在队列头和队列尾进行操作
    3.3. 具有固定大小的存储空间,可以避免内存泄漏等问题。
  4. 环形队列的缺点:
    4.1. 需要额外的指针来维护队列的状态,增加了复杂度
    4.2. 不能有效地利用存储空间,因为一旦队列满了,就需要覆盖队列头的元素
    4.3. 队列的大小必须预先定义好,难以动态调整。

综上所述,队列和环形队列各自有其优缺点,需要根据具体的应用场景来选择合适的数据结构。如果需要按照顺序处理元素并且不需要动态调整队列的大小,可以选择队列;如果需要节省存储空间并且能够循环利用队列的存储空间,可以选择环形队列。

4、图解

4.1、普通队列

[Data structure]队列&环形队列 | 一文带你彻底搞懂队列和环形队列(内附详细图解和代码实现)

实现思路:

  1. front 就指向队列的第一个元素的前一个位置, 也就是font队头索引值为-1
  2. rear 指向队列的最后一个元素,rear初始值为-1
  3. 当队列满时,条件是 rear == maxSize - 1 【满】
  4. 对队列为空的条件, rear == front【空】
  5. 队列中有效的数据的个数 (rear - front)
    后面要在这个实现思路上面做优化,优化为环形队列

4.2、环形队列

[Data structure]队列&环形队列 | 一文带你彻底搞懂队列和环形队列(内附详细图解和代码实现)
实现思路:

  1. front 变量的含义做一个调整: front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素
    front 的初始值 = 0
  2. rear 变量的含义做一个调整:rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.
    rear 的初始值 = 0
  3. 当队列满时,条件是 (rear + 1) % maxSize == front 【满】
  4. 对队列为空的条件, rear== front【空】
  5. 当我们这样分析, 队列中有效的数据的个数 (rear + maxSize - front) % maxSize
  6. 我们就可以在原来的队列上修改得到,一个环形队列

此处队列满,有效数据个数的分析如下:

  1. front=2,rear=0,MaxSize假设为5,那么最多存储4个数据(约定俗成,后面解释)
  2. 当rear>front,有效数据为:rear-front
  3. 当rear<front,环形队列就生效了。此时最后一个出队列的数据的索引值,排在了第一个出队列的数据的索引值之后,那么就要算出(后索引减前索引为多少,即rear-front),发现是负的。
  4. 此时的有效数据就应该为:(rear + maxSize - front) % maxSize。这里为什么要加maxSize,是因为要补偿rear-front为负数的那部分
  5. 比如rear-front=-2,-2+MaxSize=3,3%5=3,所以有效个数是三个。
    求出是-2,说明此时距离队列全部填充数据,还少了两个数据(一个是约定的空一个位置,一个是rear和front之间),那么此时加上maxSize,刚好弥补这两个欠缺的数据(因为数组长度有限,所以抵消掉负数之后,剩下的就是有效数据)

下面说一下关于为什么队列满的索引值是 (maxSize-1)-1 :
这是一个约定俗成的记法,只是为了增加代码的阅读性,此处浪费数组最后一个存储空间进行约定。也可以不这么处理。

5、代码实现(Java)

5.1、普通队列实现

先看一下代码总体实现思路:
  [Data structure]队列&环形队列 | 一文带你彻底搞懂队列和环形队列(内附详细图解和代码实现)

代码编写流程:

  1. 编写有参构造器,传入整数初始化数组容量,在构造器中对front和rear"指针"初始化为-1;
  2. 判断队列是否为空
  3. 判断队列是否为满
  4. 判断队列有多少个有效数据
  5. 添加数据
  6. 取出数据
  7. 显示头数据

重点是取数据、添加数据和有效数据的个数:
  [Data structure]队列&环形队列 | 一文带你彻底搞懂队列和环形队列(内附详细图解和代码实现)
  [Data structure]队列&环形队列 | 一文带你彻底搞懂队列和环形队列(内附详细图解和代码实现)
  [Data structure]队列&环形队列 | 一文带你彻底搞懂队列和环形队列(内附详细图解和代码实现)

完整代码如下(内附详细注释):

package queueArray;

import java.util.Arrays;

/**
 * @author 逐梦苍穹
 * @date 2023/4/17 13:44
 */
public class QueueArray {
    public int maxSize; //确定最大容量
    public int front; //队列头
    public int rear; //队列尾
    public int[] array; //数组实现队列

    /**
     * 初始化构造器。此处有一个JavaSE的知识:声明了有参构造器,则自动缺失了无参构造器
     */
    public QueueArray(int maxSize) {
        this.maxSize = maxSize;
        front = -1;
        rear = -1;
        array = new int[maxSize];
    }

    /**
     * 判断队列是否为空
     */
    public boolean isEmpty() {
        return rear == front;
    }

    /**
     * 判断队列是否为满
     */
    public boolean isFull() {
        return rear == (maxSize - 1);
    }

    /**
     * 判断队列中存放了多少个有效数据
     */
    public int effectiveData() {
        return (rear - front);
    }

    /**
     * 添加数据到队列(先进后出原则)
     */
    public void addQueue(int addData) {
        //先判断是否为满
        if (isFull()) {
            System.out.println("队列满,无法添加");
        } else {
            rear++;
            array[rear] = addData;
        }
    }

    /**
     * 从队列中取数据(先进后出原则)
     */
    public int getQueue() {
        //判断是否空
        if (isEmpty()) {
            System.out.println("队列空,无法获取");
            return 0;
        } else {
            front++; //front一开始索引是-1,所以要先自增1才能取到队列中的数据
            int temporary = array[front];
            array[front] = 0;
            return temporary;
        }
    }

    /**
     * 显示当前队列中所有的有效数据
     */
    public void showQueueData() {
        //判断是否为空
        if (isEmpty()) {
            System.out.println("队列空,无法显示");
        } else {
            for (int i = front + 1; i <= rear; i++) {
                System.out.printf("array[%d] = %d\n", i, array[i]);
            }
        }
    }

    /**
     * 显示头数据(并非取出)
     */
    public void showHeadData() {
        if (isEmpty()) {
            System.out.println("队列空,无法显示头数据");
        } else {
            System.out.println(array[front + 1]);
        }
    }

    @Override
    public String toString() {
        return "QueueArray{" +
                "maxSize=" + maxSize +
                ", front=" + front +
                ", rear=" + rear +
                ", array=" + Arrays.toString(array) +
                '}';
    }
}

普通队列存在的问题:空间无法复用。只能单向存储,无法循环存储:
  [Data structure]队列&环形队列 | 一文带你彻底搞懂队列和环形队列(内附详细图解和代码实现)

5.2、环形队列实现

现环形队列的重要思想:取模(对maxSize取模)

相比于之前的普通队列实现,在普通队列代码的基础上,作出如下修改:
1. front和rear初始化为0,指向数组第一个位置
2. rear的最大值不再是maxSize-1,而是预留了一个作为约定。即为(maxSize - 1 -1)
3. 判断队列是否为满:(rear + 1) % maxSize == front

4. 有效数据的个数:(rear - front + maxSize) % maxSize
5. 添加数据的rear"指针":rear = (rear + 1) % maxSize
5. 取出数据的front"指针":front = (front + 1) % maxSize

6. 显示所有数据的for循环起止条件

修改部分的代码如下:
  [Data structure]队列&环形队列 | 一文带你彻底搞懂队列和环形队列(内附详细图解和代码实现)
  [Data structure]队列&环形队列 | 一文带你彻底搞懂队列和环形队列(内附详细图解和代码实现)
  [Data structure]队列&环形队列 | 一文带你彻底搞懂队列和环形队列(内附详细图解和代码实现)
  [Data structure]队列&环形队列 | 一文带你彻底搞懂队列和环形队列(内附详细图解和代码实现)
  [Data structure]队列&环形队列 | 一文带你彻底搞懂队列和环形队列(内附详细图解和代码实现)
[Data structure]队列&环形队列 | 一文带你彻底搞懂队列和环形队列(内附详细图解和代码实现)

代码的总体实现思路和之前的普通队列一致。

下面是环形队列的完整代码:

package queueArray;

import java.util.Arrays;

/**
 * @author 逐梦苍穹
 * @date 2023/4/17 13:44
 */
public class CircleQueueArray {
    public int maxSize; //确定最大容量
    public int front; //队列头
    public int rear; //队列尾,最后一个存储数据的索引为 (maxSize - 1) - 1
    public int[] array; //数组实现队列

    /**
     * 初始化构造器。此处有一个JavaSE的知识:声明了有参构造器,则自动缺失了无参构造器
     */
    public CircleQueueArray(int maxSize) {
        //front和rear不需要初始化,在环形队列的实现中默认为0
        this.maxSize = maxSize;
        array = new int[maxSize];
    }

    /**
     * 判断队列是否为空:
     */
    public boolean isEmpty() {
        return rear == front;
    }

    /**
     * 判断队列是否为满:(rear + 1) % maxSize == front
     */
    public boolean isFull() {
        //使用这种方式是因为环形队列,rear有可能是在front的后面
        return (rear + 1) % maxSize == front;
    }

    /**
     * 判断队列中存放了多少个有效数据
     */
    public int effectiveData() {
        //加上maxSize是为了弥补当rear<front这种情况下空出来的数据
        return (rear - front + maxSize) % maxSize;
    }

    /**
     * 添加数据到队列(先进后出原则)
     */
    public void addQueue(int addData) {
        //先判断是否为满
        if (isFull()) {
            System.out.println("队列满,无法添加");
        } else {
            //这里先把数据添加,再把rear后移
            array[rear] = addData;
            //后移要取模,因为要同时考虑普通队列和循环队列的情况
            rear = (rear + 1) % maxSize;
        }
    }

    /**
     * 从队列中取数据(先进后出原则)
     */
    public int getQueue() {
        //判断是否空
        if (isEmpty()) {
            System.out.println("队列空,无法获取");
            return 0;
        } else {
            //front默认为0
            int temporary = array[front];
            array[front] = 0;
            //front指针下移一位,但是这里要取模
            front = (front + 1) % maxSize;
            return temporary;
        }
    }

    /**
     * 显示当前队列中所有的有效数据
     */
    public void showQueueData() {
        //判断是否为空
        if (isEmpty()) {
            System.out.println("队列空,无法显示");
        } else {
            //现在是从front开始
            for (int i = front; i < front + effectiveData(); i++) {
                System.out.printf("array[%d] = %d\n", i % maxSize, array[i % maxSize]);
            }
        }
    }

    /**
     * 显示头数据(并非取出)
     */
    public void showHeadData() {
        if (isEmpty()) {
            System.out.println("队列空,无法显示头数据");
        } else {
            System.out.println(array[front]);
        }
    }

    @Override
    public String toString() {
        return "CircleQueueArray{" +
                "maxSize=" + maxSize +
                ", front=" + front +
                ", rear=" + rear +
                ", array=" + Arrays.toString(array) +
                '}';
    }
}

到这里,队列和环形队列就介绍完了。
如果有什么错误请大家不吝赐教
也可以一起探讨学习😊文章来源地址https://www.toymoban.com/news/detail-416524.html

到了这里,关于[Data structure]队列&环形队列 | 一文带你彻底搞懂队列和环形队列(内附详细图解和代码实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 3分钟带你彻底搞懂 Kafka

    实时数据处理 ,从名字上看,很好理解,就是将数据进行实时处理,在现在流行的微服务开发中,最常用实时数据处理平台有 RabbitMQ、RocketMQ 等消息中间件。 这些中间件,最大的特点主要有两个: 服务解耦 流量削峰 在早期的 web 应用程序开发中,当请求量突然上来了时候,

    2024年04月16日
    浏览(55)
  • 一文彻底搞懂JSON数据

    什么是JSON,为什么需要JSON,JSON的3种形式,JSON常用的方法等 TIP JSON指的是全称是:javascript对象表示法 JSON是Ajax发送和接收数据的一种格式 JSON是一种轻量级的数据交互格式, 其为字符串类型 (面试题会考到) JSON是一种语法,用来序列化对象、数组、数值、字符串、布尔值和

    2024年02月06日
    浏览(49)
  • 【算法】一文彻底搞懂ZAB算法

    最近需要设计一个分布式系统,需要一个中间件来存储共享的信息,来保证多个系统之间的数据一致性,调研了两个主流框架Zookeeper和ETCD,发现都能满足我们的系统需求。 其中ETCD是K8s中采用的分布式存储,而其底层采用了RAFT算法来保证一致性,之前已经详细分析了Raft算法

    2024年02月02日
    浏览(58)
  • 一文彻底搞懂Maven配置(终结版)

    下载安装 提示:安装之前需要先确认好自己需要哪个版本的maven,避免浪费时间。 官网下载:https://maven.apache.org/download.cgi 历史版本下载:https://archive.apache.org/dist/maven/maven-3/ maven配置setting.xml localRepository 该值表示构建系统本地仓库的路径 interactiveMode 表示maven是否需要和用

    2024年02月04日
    浏览(43)
  • 一文彻底搞懂ssh的端口转发

    端口转发是突破网络域隔离的一个手段。在学习这个知识的时候需要不断自问 为什么需要端口转发? 应用场景是什么呢? SSH 隧道或 SSH 端口转发可以用来在 客户端和服务器之间建立一个加密的 SSH 连接 如下图,通过它来把本地流量转发到服务器端,或者把服务器端流量转发

    2023年04月22日
    浏览(46)
  • 万字长文,带你彻底搞懂 HTTPS(文末附实战)

    大家好,我是满天星,欢迎来到我的技术角落,本期我将带你一起来了解 HTTPS。 PS:本文首发于微信公众号:技术角落。感兴趣的同学可以查看并关注:https://mp.weixin.qq.com/s/HbEhD93S7y3p8amlzS2sKw 其实网上写 HTTPS 的文章也不少了,但是不少文章都是从原理上泛泛而谈,只讲概念,

    2023年04月14日
    浏览(43)
  • 10分钟的时间,带你彻底搞懂JavaScript数据类型转换

    前言  📫 大家好,我是南木元元,热衷分享有趣实用的文章,希望大家多多支持,一起进步!  🍅  个人主页: 南木元元 目录 JS数据类型 3种转换类型 ToBoolean ToString ToNumber 对象转原始类型 隐式类型转换 结语 JS数据类型 首先我们需要知道,js中数据类型分为两大类: 基本

    2024年02月05日
    浏览(50)
  • 一文彻底搞懂BJT及其放大特性(图解说明)

    前置知识:PN结 一文彻底搞懂PN结及其单向导电性(图解说明)-CSDN博客 BJT的基本结构如上图所示,在左侧是宽度较窄,浓度非常高的N型离子参杂。中间是非常窄的P型离子参杂。而左侧是浓度较低的N型离子参杂。 在N型参杂区和P型参杂区之间会形成PN结,因此BJT实际上内部是

    2024年02月08日
    浏览(39)
  • 一文彻底搞懂流水线加法器

    目录 1.流水线加法器应用场景 2.流水线加法器本质原理(与普通加法器区别) 3.流水线加法器实现 4.流水线加法器代码Verilog代码实现 首先最重要的是明白我们流水线加法器是什么,我们其实对于流水线其实并不陌生,我们常常可以听到说工厂中存在流水线,他是一种工业上

    2024年02月08日
    浏览(116)
  • 一文彻底搞懂Kafka如何保证消息不丢失

    Producer:生产者,发送消息的一方。生产者负责创建消息,然后将其发送到 Kafka。 Consumer:消费者,接受消息的一方。消费者连接到 Kafka 上并接收消息,进而进行相应的业务逻辑处理。 Consumer Group:将多个消费者组成一个消费者组,一个消费者组可以包含一个或多个消费者。

    2024年04月22日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包