Java基础之数组模拟循环队列
作者:在下木子李 发布时间:2022-08-29 12:58:06
一、队列简介
队列是一个有序列表,遵循“先入先出”的原则,即先存入队列的数据要先取出,后存入的数据后取出。
队列有两种存储表示,顺序表示和链式表示。顺序表示可以用数组来实现。
二、数组模拟队列
用数组模拟队列时,设两个值front=0,rear=0。front表示队列首部第一个数据所在位置,rear表示尾部最后一个数据的下一个位置。
将数据插入数组队列时(入队),从尾部进行插入,即array[rear] = value,同时rear后移,rear++。取出数据时(出队),从头部取出数据,value = array[front],同时front后移front++。
当front=0,rear=maxSize(数组的最大长度),队列满,不能再存入数据。
这时如果执行出队操作,又有空间可以存储,但继续插入数据,会出现溢出现象,即因数组越界而导致程序非法操作错误。而实际上空间并未占满,所以称这种现象为“假溢出”。这是由“队尾入队,队头出队”的限制操作所造成的。
如何解决“假溢出”的问题呢?
答案就是循环队列。
三、数组模拟循环队列
将顺序队列变为一个环状空间,front、rear和队列元素之间的关系不变,只是在循环队列中,front、rear依次后移加1的操作可用“模”运算来实现。
通过取模,front、rear就可以在顺序表空间内以头尾衔接的方式“循环”移动。
元素出队后,front = (front+1)%maxSize ;
元素入队后,rear = (rear+1)%maxSize 。
(maxSize为数组队列的最大长度)
例如,队列最大长度为4,当rear=3时,存入数据,array[3]=value,rear后移一位,如果没有取模运算,则rear=4,这时继续插入数据,array[4]越界。
如果进行取模运算,rear = (rear+1)%maxSize ,这时rear=0,rear又重新回到了0的位置。这样的运算,使得rear的值在0、1、2、3之间循环。
front的值同理。
写了这么多字,感觉还不如看代码来得更容易理解一点。
四、代码实现
数组模拟循环队列
package com.ArrayQueue;
import java.util.Scanner;
public class CircleArrayQueueDemo {
public static void main(String args[]){
int maxSize = 4;
CircleArrayQueue queue = new CircleArrayQueue(maxSize);
Scanner scanner = new Scanner(System.in);
char key;
boolean loop = true;
while (loop) {
//根据输入的不同字母,进行对应的操作
System.out.println("a(add):添加一个数据");
System.out.println("g(get):取出一个数据");
System.out.println("h(head):展示头部数据");
System.out.println("s(show):展示所有数据");
System.out.println("q(quit):退出程序");
//因为判满条件的缘故,队列的最大容量实为maxSize-1
System.out.printf("(队列的最大容量为:%d)\n",maxSize-1);
key = scanner.next().charAt(0);//接收一个字符
try {
switch (key) {
case 'a':
System.out.println("请输入一个数:");
int value = scanner.nextInt();
queue.addQueue(value);
System.out.println("数据添加成功。");
break;
case 'g':
System.out.printf("取出的数据为:%d\n", queue.getQueue());
break;
case 'h':
queue.headQueue();
break;
case 's':
queue.showQueue();
break;
case 'q':
scanner.close();
loop = false;
System.out.println("程序已退出。");
break;
default:
break;
}
} catch (RuntimeException e) {
System.out.println(e.getMessage());
}
}
}
}
/**
* 队列的顺序表示
* 数组模拟循环队列
*/
class CircleArrayQueue{
private int maxSize;
private int front;//指向头元素所在位置
private int rear;//指向尾元素所在位置的下一个位置
private int arr[];//存放数据的数组
//构造器,传入数组最大容量值
public CircleArrayQueue(int size){
maxSize = size;
front = 0;
rear = 0;
//虽然数组最大容量为maxSize,但实际用于存储的只有maxSize-1
arr = new int[maxSize];
}
//判空条件:front == rear
public boolean isEmpty(){
return front == rear;
}
//判满条件:(rear+1)%maxSize == front
public boolean isFull(){
return (rear+1)%maxSize == front;
}
//添加数据,入队
public void addQueue(int n){
//判满
checkFull();
arr[rear] = n;
rear = (rear+1)%maxSize;
}
//取出数据,出队
public int getQueue(){
//判空
checkEmpty();
int value = arr[front];
front = (front+1)%maxSize;
return value;
}
//队列中的有效值个数
public int size(){
return (rear-front+maxSize)%maxSize;
}
//展示队列的所有数据
public void showQueue(){
//判空
checkEmpty();
for(int i=front;i<front+size();i++){
System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
}
System.out.printf("当前front=%d,rear=%d\n",front,rear);
}
//展示位于队列头部的元素值,不改变front的指向
public void headQueue(){
//判空
checkEmpty();
System.out.printf("头部数据是:%d\n",arr[front]);
}
//检测出队列为空时,打印当前front,rear的值,抛出异常
public void checkEmpty(){
if (isEmpty()) {
System.out.printf("当前front=%d,rear=%d\n",front,rear);
throw new RuntimeException("队列为空,不能取数据");
}
}
//检测出队列满时,打印当前front,rear的值,抛出异常
public void checkFull(){
if(isFull()){
System.out.printf("当前front=%d,rear=%d\n",front,rear);
throw new RuntimeException("队列已满,不能添加数据");
}
}
}
五、运行结果
来源:https://blog.csdn.net/weixin_44902943/article/details/109202455
猜你喜欢
- 目前较常用的分页实现办法有两种:1.每次翻页都修改SQL,向SQL传入相关参数去数据库实时查出该页的数据并显示。2.查出数据库某张表的全部数
- 在实际的项目开发中会有很多的对象,如何高效、方便地管理对象,成为影响程序性能与可维护性的重要环节。Java 提供了集合框架来解决此类问题,线
- 下载UEditorhttps://ueditor.baidu.com/website/download.html下载完整源码和JSP版本Sp
- 本文实例展示了C#中this指针的用法,对于初学者进一步牢固掌握C#有很大帮助,具体内容如下:一、this指针是什么:这里有一些面向对象编程
- 任务超时处理是比较常见的需求,比如在进行一些比较耗时的操作(如网络请求)或者在占用一些比较宝贵的资源(如数据库连接)时,我们通常需要给这些操
- Java基本概念JDK包含了不少Java开发相关命令。如,javac、java、javap、javaw、javadoc。虽然现在的Java开
- 1.基本概念首先我们需要弄清楚几个概念:面向对象是什么、类是什么、对象又是什么?还是逐个来说1.1面向对象我们常说Java是面向对象的语言,
- 前言在我们的日常的编程当中,并发是始终离不开的主题,而在并发多线程当中,线程池又是一个不可规避的问题。多线程可以提高我们并发程序的效率,可以
- 一、@RequestMapping@RequestMapping注解的源码:@Target({ElementType.TYPE, Eleme
- 本文实例为大家分享了java实现幸运抽奖功能的具体代码,供大家参考,具体内容如下本系统较为简单,未使用是什么多的算法,也未添加保存文件读取文
- 随着C语言的学习慢慢结束,博主也要开始学习一门新语言了,那就是java。所以博主将会开启一个新的关于java的专栏,所以想要慢慢和我一起学习
- 一. 线性表中的顺序表线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见
- 前言我们从以下几个方面研究:SpringBoot的启动依赖启动器starter有什么作用启动引导类是怎么运行的内置的tomcat服务器原理p
- Java是面向对象的编程语言,在我们开发Java应用的程序员的专业术语里,Java这个单词其实指的是Java开发工具,也就是JDK(Java
- Jetty和tomcat的比较Tomcat和Jetty都是一种Servlet引擎,他们都支持标准的servlet规范和JavaEE的规范。架
- 这两个update都是使用generator生成的mapper.xml文件中,对dao层的更新操作update更新传回数据的所有字段,没有传
- 一、面向对象的4个基本特征抽象性、封装性、继承性和多态性。抽象性分为过程抽象和数据抽象。封装性封装将数据以及加在这些数据上的操作组织在一起,
- OOP语言的三大特征即:面向对象的三个比较重要的思想封装官话:将数据和操作数据的方法进行有机结合,隐藏对象的属性和实现细节,仅对外公开接口进
- 相信大家最关心的肯定不是什么一大堆的破理论,然后还似懂非懂的,最关心得莫过于服务之间的参数传递,数据获取。Ok,今天就告诉大家三种微服务之间
- 本文实例讲述了C#显示文件夹下所有图片文件的方法。分享给大家供大家参考。具体实现方法如下:<%@ Page Language=&quo