数据结构--环形队列的介绍与实现

article/2025/9/28 2:38:54

数据结构--环形队列实现

    • 一、环形队列实现原理
      • 环形队列的几个判断条件
    • 二、代码实现
      • 1.环形队列类（CircleQueue）
      • 2.环形队列类测试类
      • 3.程序运行结果
      • 4.完整代码

环形队列可以用数组实现，也可以使用循环链表实现.在使用数组实现循环队列的时候，需要理解清楚队列头和队列尾的判断空还是满的处理方法；

环形队列的优点：

  • 避免假溢出现象（由于入队和出队的操作，头尾指针只增加不减少，致使被删元素的空间永远无法重新利用，当队列继续存储元素时，出现尾指针已经到达了队列尾，而实际头指针前面并未满的情况），可以将队列空间充分重复利用
  • 首尾相连的FIFO的数据结构，采用数据的线性空间，数据组织简单，能快速知道队列是否满/空
  • 广泛用于网络数据收发，和不同程序间数据交换，均使用了环形队列

一、环形队列实现原理

  • 内存上并没有环形的结构，因此环形队列实际上是数组的线性空间来实现的。

  • 当数据到了尾部该如何处理呢？它将转回到原来位置进行处理，通过取模操作来实现

环形队列的几个判断条件

front:指向队列的第一个元素，初始值front=0

rear: 指向队列的最后一个元素的后一个位置（预留一个空间作为约定）,初始值rear=0

maxSize: 数组的最大容量

  • 队空：front == rear

  • 队满：(rear+1)%maxSize == front

  • 队列中的有效数据个数：（rear+maxSize-front）% maxSize

在这里插入图片描述

其中判断队列满的思想的话，可以看下图，因为是环形的，起初front=rear=0，每当添加元素时，将rear++，但是其实预留了一个长度没有用，比如定义的队列数组长度为5时，但是实际上可以使用的地址就是0,1,2,3，此时rear=4, 4这个空间用来判断队满的条件（rear+1）%maxSize==front

在这里插入图片描述

二、代码实现

1.环形队列类（CircleQueue）

/*** 环形队列类* 构造器* 判断是否已满、判断是否空、查看队列数据、显示队列的有效数据个数、入队列、出队列*/class CircleQueue {
//    数组的最大容量private final int maxSize;
//    front指向队列的第一个元素，初始值为0private int front;
//    rear指向队列的最后一个元素的后一个位置，空出一个空间作为约定，初始值为0private int rear;
//    存放数据，模拟队列private final int[] arr;//    创建队列构造器public CircleQueue(int maxSize) {this.maxSize = maxSize;front = 0;rear = 0;arr = new int[maxSize];}//    判断队列是否已满public boolean isFull() {return (rear + 1) % maxSize == front;}//    判断队列是否为空public boolean isEmpty() {return rear == front;}//    查看队列数据,显示队列所有数据public void showQueue() {if (isEmpty()) {System.out.println("队列为空，没有数据！");return;}
//        从front开始遍历，注意遍历的元素个数for (int i = front; i < front + size(); i++) {System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);}}//    求出当前队列有效数据的个数public int size() {return (rear + maxSize - front) % maxSize;}//    显示队列的头数据，注意不是取出数据public int headQueue() {if (isEmpty()) {throw new RuntimeException("队列是空的，没有数据！");}return arr[front];}//    添加数据到队列public void addQueue(int n) {if (isFull()) {System.out.println("队列已满");return;}arr[rear] = n;System.out.println(n + "成功添加到队列");//        将rear后移，这里必须考虑取模rear = (rear + 1) % maxSize;}//    从队列取出数据,，出队列public int getQueue() {if (isEmpty()) {throw new RuntimeException("队列为空，无法取出数据");}//        这里需要分析出front是指向队列的第一个元素//        1. 先把front对应的值保留到一个临时变量//        2. 将front后移，考虑取模//        3. 将临时保存的变量取回int value = arr[front];front = (front + 1) % maxSize;return value;}

2.环形队列类测试类

/*** @author Manix * 环形队列测试类*/public class CircleArrayQueueDemo {public static void main(String[] args) {
//        创建一个环形队列，maxSize设置说明，4，其队列的有效数据最大为3CircleQueue circleQueue = new CircleQueue(4);
//      接收用户输入char key = ' ';Scanner scanner = new Scanner(System.in);boolean loop = true;
//        输出一个菜单while (loop) {System.out.println("s(show),显示队列数据");System.out.println("e(exit),退出队列");System.out.println("a(add),添加数据到队列");System.out.println("g(get),获取队列数据");System.out.println("h(head),获取队列头数据");
//          接收输入的字符key = scanner.next().charAt(0);switch (key) {case 's':circleQueue.showQueue();break;case 'a':System.out.println("输入一个数：");int value = scanner.nextInt();circleQueue.addQueue(value);break;case 'g':try {int res = circleQueue.getQueue();System.out.printf("取出的数据是%d\n", res);} catch (Exception e) {System.out.println(e.getMessage());}break;case 'h':try {int res = circleQueue.headQueue();System.out.printf("队列头的数据是%d\n", res);} catch (Exception e) {System.out.println(e.getMessage());}break;case 'e':loop = false;scanner.close();break;default:break;}}System.out.println("-----程序退出-----");}
}

3.程序运行结果

s(show),显示队列数据
e(exit),退出队列
a(add),添加数据到队列
g(get),获取队列数据
h(head),获取队列头数据
s
队列为空，没有数据！
s(show),显示队列数据
e(exit),退出队列
a(add),添加数据到队列
g(get),获取队列数据
h(head),获取队列头数据
a
输入一个数：
10
10成功添加到队列
s(show),显示队列数据
e(exit),退出队列
a(add),添加数据到队列
g(get),获取队列数据
h(head),获取队列头数据
a
输入一个数：
20
20成功添加到队列
s(show),显示队列数据
e(exit),退出队列
a(add),添加数据到队列
g(get),获取队列数据
h(head),获取队列头数据
a
输入一个数：
60
60成功添加到队列
s(show),显示队列数据
e(exit),退出队列
a(add),添加数据到队列
g(get),获取队列数据
h(head),获取队列头数据
a20
输入一个数：
20
队列已满
s(show),显示队列数据
e(exit),退出队列
a(add),添加数据到队列
g(get),获取队列数据
h(head),获取队列头数据
s
arr[0]=10
arr[1]=20
arr[2]=60
s(show),显示队列数据
e(exit),退出队列
a(add),添加数据到队列
g(get),获取队列数据
h(head),获取队列头数据
a
输入一个数：
30
队列已满
s(show),显示队列数据
e(exit),退出队列
a(add),添加数据到队列
g(get),获取队列数据
h(head),获取队列头数据
s
arr[0]=10
arr[1]=20
arr[2]=60
s(show),显示队列数据
e(exit),退出队列
a(add),添加数据到队列
g(get),获取队列数据
h(head),获取队列头数据
g
取出的数据是10
s(show),显示队列数据
e(exit),退出队列
a(add),添加数据到队列
g(get),获取队列数据
h(head),获取队列头数据
g
取出的数据是20
s(show),显示队列数据
e(exit),退出队列
a(add),添加数据到队列
g(get),获取队列数据
h(head),获取队列头数据
s
arr[2]=60
s(show),显示队列数据
e(exit),退出队列
a(add),添加数据到队列
g(get),获取队列数据
h(head),获取队列头数据
h
队列头的数据是60
s(show),显示队列数据
e(exit),退出队列
a(add),添加数据到队列
g(get),获取队列数据
h(head),获取队列头数据

4.完整代码

/*** @author Manix* 环形队列测试类*/public class CircleArrayQueueDemo {public static void main(String[] args) {
//        创建一个环形队列，maxSize设置说明，4，其队列的有效数据最大为3CircleQueue circleQueue = new CircleQueue(4);
//      接收用户输入char key = ' ';Scanner scanner = new Scanner(System.in);boolean loop = true;
//        输出一个菜单while (loop) {System.out.println("s(show),显示队列数据");System.out.println("e(exit),退出队列");System.out.println("a(add),添加数据到队列");System.out.println("g(get),获取队列数据");System.out.println("h(head),获取队列头数据");
//          接收输入的字符key = scanner.next().charAt(0);switch (key) {case 's':circleQueue.showQueue();break;case 'a':System.out.println("输入一个数：");int value = scanner.nextInt();circleQueue.addQueue(value);break;case 'g':try {int res = circleQueue.getQueue();System.out.printf("取出的数据是%d\n", res);} catch (Exception e) {System.out.println(e.getMessage());}break;case 'h':try {int res = circleQueue.headQueue();System.out.printf("队列头的数据是%d\n", res);} catch (Exception e) {System.out.println(e.getMessage());}break;case 'e':loop = false;scanner.close();break;default:break;}}System.out.println("-----程序退出-----");}
}/*** 环形队列类* 构造器* 判断是否已满、判断是否空、查看队列数据、显示队列的有效数据个数、入队列、出队列*/class CircleQueue {
//    数组的最大容量private final int maxSize;
//    front指向队列的第一个元素，初始值为0private int front;
//    rear指向队列的最后一个元素的后一个位置，空出一个空间作为约定，初始值为0private int rear;
//    存放数据，模拟队列private final int[] arr;//    创建队列构造器public CircleQueue(int maxSize) {this.maxSize = maxSize;front = 0;rear = 0;arr = new int[maxSize];}//    判断队列是否已满public boolean isFull() {return (rear + 1) % maxSize == front;}//    判断队列是否为空public boolean isEmpty() {return rear == front;}//    查看队列数据,显示队列所有数据public void showQueue() {if (isEmpty()) {System.out.println("队列为空，没有数据！");return;}
//        从front开始遍历，注意遍历的元素个数for (int i = front; i < front + size(); i++) {System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);}}//    求出当前队列有效数据的个数public int size() {return (rear + maxSize - front) % maxSize;}//    显示队列的头数据，注意不是取出数据public int headQueue() {if (isEmpty()) {throw new RuntimeException("队列是空的，没有数据！");}return arr[front];}//    添加数据到队列public void addQueue(int n) {if (isFull()) {System.out.println("队列已满");return;}arr[rear] = n;System.out.println(n + "成功添加到队列");//        将rear后移，这里必须考虑取模rear = (rear + 1) % maxSize;}//    从队列取出数据,，出队列public int getQueue() {if (isEmpty()) {throw new RuntimeException("队列为空，无法取出数据");}//        这里需要分析出front是指向队列的第一个元素//        1. 先把front对应的值保留到一个临时变量//        2. 将front后移，考虑取模//        3. 将临时保存的变量取回int value = arr[front];front = (front + 1) % maxSize;return value;}}

http://chatgpt.dhexx.cn/article/O4DuYUim.shtml

相关文章

【数据结构(C语言描述)】环形队列

【数据结构(C语言描述)】环形队列

目录 一、基础知识二、数组实现环队2.1 初始化2.2 判断环队是否为空2.3 判断环队是否为满2.4 入队2.5 出队2.6 取队头元素2.7 取队尾元素2.8 销毁环队 三、链表实现环队3.1 初始化3.2 判断环队是否为空3.3 判断环队是否为满3.4 入队3.5 出队3.6 取队头元素3.7 取队尾元素3.8 销…
阅读更多...
环形队列原理，全网最通俗易懂

环形队列原理，全网最通俗易懂

队列是什么 队列是一种很常见的数据结构&#xff0c;满足先进先出的方式&#xff0c;如果我们设定队列的最大长度&#xff0c;那就意味着进队列和出队列的元素的数量实则满足一种动态平衡。 如果我们把首次添加入队列的元素作为一个一维坐标的原点&#xff0c;那么随着队列中…
阅读更多...
Mysql 死锁和死锁的解决方案

Mysql 死锁和死锁的解决方案

最近在研究Mysql底层原理&#xff0c;研究到了死锁&#xff0c;感觉挺有意思&#xff0c;在这里和大家分享一下 前置知识&#xff1a;需要了解锁的种类&#xff0c;如表锁、行锁&#xff1b;行锁又分为记录锁、间隙锁、临键锁等等&#xff1b;什么情况下会加表锁&#xff0c;什…
阅读更多...
mysql死锁演示

mysql死锁演示

背景&#xff1a; 线上日志突然爆了有数据库死锁的日志。 通过以下语句查询数据库死锁的日志 SHOW ENGINE INNODB STATUS 通过 日志分析&#xff0c;看到了两条update语句并且是里面有子查询。还有两个表的更新顺序问题。 解决方案是&#xff1a;加了分布式锁&#xff0c;…
阅读更多...
记录一次mysql死锁

记录一次mysql死锁

一&#xff0c;死锁发现 项目中有一个接口包含更新操作1&#xff0c;后面发现更新失败&#xff0c;通过查看应用程序日志&#xff0c;发现发生了死锁 sql 1 如下 1.最初版本根据id为条件&#xff0c;更新&#xff08;plan_start_time 二级索引&#xff09; update tt_task …
阅读更多...
深入MySQL死锁场景

深入MySQL死锁场景

总结死锁需满足以下条件&#xff1a; 2个或者2个以上的并发事务操作并发事务之间存在锁冲突锁冲突关系成环形 GAP锁和Insert的隐式锁&#xff0c;最容易导致死锁&#xff0c;以下分析从这俩典型场景开始。 1. 表结构 建立以下表作为场景验证&#xff0c;id为主键&#xff0…
阅读更多...
mysql死锁查询语句

mysql死锁查询语句

mysql 死锁:如何解决mysql死锁 可直接在mysql命令行执行&#xff1a;showengineinnodbstatus\G;查看造成死锁的sql语句&#xff0c;分析索引情况&#xff0c;然后优化sql然后showprocesslist;另外可以打开慢查询日志&#xff0c;linux下打开需在my.cnf的[mysqld]里面加上以下内…
阅读更多...
MySQL死锁排查步骤

MySQL死锁排查步骤

系列文章目录 第一章&#xff1a;sql_mode模式 第二章&#xff1a;optimize table、analyze table、alter table、gh-ost 第三章&#xff1a;InnoDB MVCC原理 第四章&#xff1a;sql语句执行过程 第五章&#xff1a;Percona Toolkit工具简介 第六章&#xff1a;MySQL索引 第七…
阅读更多...
MySql死锁过程

MySql死锁过程

死锁一般怎么导致呢&#xff0c; 抛开一堆概念&#xff0c; 我就把死锁当成死结。 就是你代码获取锁的顺序问题。 MySql的死锁和我们正常代码也一样&#xff0c; 都是互通的&#xff0c; 当你修改一个表的行数据的时候&#xff0c; 就需要对那一行数据进行加锁。 所以很容易想…
阅读更多...
中秋遇到mysql死锁怎么办

中秋遇到mysql死锁怎么办

文章目录 前言一、什么是死锁二、死锁的产生条件三、死锁示例四、死锁的分析和查看1.查看最近1个死锁信息2.查看正在运行中的事务信息3.查看加锁信息 五、死锁的内部处理方案1.死锁探测机制2.锁等待超时机制 六、手动释放锁1.表级锁手动释放2.行级锁手动释放 七、死锁的优化策略…
阅读更多...
mysql 死锁分析

mysql 死锁分析

一、 什么是死锁 死锁是指两个或两个以上的进程在执行过程中,因争夺资源而造成的一种互相等待的现象,若无外力作用,它们都将无法推进下去.此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等的进程称为死锁进程.二、 死锁产生的四个必要条件 1.互斥条件&#xff1a;指进…
阅读更多...
MySQL死锁分析

MySQL死锁分析

背景知识 MySQL数据库InnoDB引擎的行级锁在使用时是在索引记录上加锁的。 行级锁从占有模式上分为&#xff1a; 排他锁&#xff1a;独占行数据&#xff0c;如某事务获取了该行记录的排他锁&#xff0c;其他事务在获取该记录的排他锁和共享锁时需等待&#xff1b;共享锁&…
阅读更多...
故障分析 | MySQL死锁案例分析

故障分析 | MySQL死锁案例分析

作者&#xff1a;杨奇龙 网名“北在南方”&#xff0c;资深 DBA&#xff0c;主要负责数据库架构设计和运维平台开发工作&#xff0c;擅长数据库性能调优、故障诊断。 本文来源&#xff1a;原创投稿 *爱可生开源社区出品&#xff0c;原创内容未经授权不得随意使用&#xff0c;转…
阅读更多...
MySQL死锁

MySQL死锁

参考博客&#xff1a; https://blog.csdn.net/sinat_41653656/article/details/109629094 Mysql 锁类型和加锁分析 MySQL有三种锁的级别&#xff1a;页级、表级、行级。 表级锁&#xff1a;开销小&#xff0c;加锁快&#xff1b;不会出现死锁&#xff1b;锁定粒度大&#xff…
阅读更多...
mysql死锁语句_Mysql死锁

mysql死锁语句_Mysql死锁

笔者最近在生产环境错误日志上看到updating database. Cause: com.mysql.jdbc.exceptions.jdbc4.MySQLTransactionRollbackException: Deadlock found when trying to get lock; try restarting transaction 这样的日志 ，网上看了很多文章 发现这篇文章 跟自己的场景非常接近…
阅读更多...
【MySQL锁篇】MySQL死锁问题以及解决方案

【MySQL锁篇】MySQL死锁问题以及解决方案

目录 一、MySQL出现死锁的场景 二、MySQL当中的死锁现象 三、Insert语句怎样加锁的 隐式锁&显示锁 记录之间加有间隙锁 遇到唯一键冲突或者主键冲突的时候加锁 如果主键索引重复&#xff1a; ​​​​​​如果唯一二级索引重复: 四、如何避免MySQL当中的死锁现象 方案…
阅读更多...
mysql死锁介绍以及解决

mysql死锁介绍以及解决

什么是死锁 死锁是2个线程在执行过程中&#xff0c; 因争夺资源而造成的相互等待的现象&#xff0c;若无外力作用&#xff0c;它们将无法推进下去。 死锁产生的4个必要条件 互斥条件 指进程对所分配的资源进行排他性使用&#xff0c;即一段时间内某资源只有一个进程占用&#…
阅读更多...
MySQL - 死锁的产生及解决方案

MySQL - 死锁的产生及解决方案

MySQL - 死锁的产生及解决方案 1. 死锁与产生死锁的四个必要条件1.1 什么是死锁1.2 死锁产生的4个必要条件 2. 死锁案例2.1 表锁死锁2.2 行锁死锁2.3 共享锁转换为排他锁 3. 死锁排查4. 实例分析4.1 案例描述4.2 案例死锁问题复现4.3 死锁排查4.4 解决死锁 5. 如何避免死锁 1. …
阅读更多...
MySql 死锁

MySql 死锁

MySql 死锁 一、什么是死锁InnoDB存储引擎定义了四种类型的行锁隔离等级对加锁的影响当前数据对加锁的影响 二、为什么会形成死锁两阶段锁协议产生死锁的四个必要条件 三、MySQL 如何处理死锁&#xff1f;杀死进程MySQL表间隙锁排他锁共享锁分析行锁定行锁优化 四、如何避免发生…
阅读更多...
论文阅读|SMPL2015

论文阅读|SMPL2015

摘要&#xff1a; 我们提出了一个学习过的人体形状和姿势相关的形状变化模型&#xff0c;该模型比以前更准确建模并与现有的图形管线兼容。我们的蒙皮多人线性模型&#xff08;SMPL&#xff09;是基于蒙皮顶点的模型&#xff0c;可以准确地表示各种各样的人体姿态。模型的参数是…
阅读更多...
推荐文章

Copyright @ 2022~2023