Java代码实现循环队列的示例代码
作者:1 Byte 发布时间:2023-11-23 23:51:25
标签:Java,循环队列
循环队列结构
队列特点
队列为一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表。
循环队列优缺点
循环队列的优点:
可以有效的利用资源。用数组实现队列时,如果不移动,随着数据的不断读写,会出现假满队列的情况。即尾数组已满但头数组还是空的;循环队列也是一种数组,只是它在逻辑上把数组的头和尾相连,形成循环队列,当数组尾满的时候,要判断数组头是否为空,不为空继续存放数据。
循环队列的缺点:
循环队列中,由于入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针,造成队空和队满时头尾指针均相等。因此,判别队列是"空"是"满"需要特殊处理 —— 判断队列为空的条件还是head == tail,但是判断队列已满的条件则是(tail+1)%size==head。
应用场景
最经典的就是类似于约瑟夫环的问题,可以使用循环队列。
Java代码实现循环队列
// 基于数组实现一个循环链表
public class CircleArrayQueue<T> {
// 定义数组用于存放数据
private T[] arr;
private int head; // 记录队列头
private int tail; // 记录队列尾
private int size; // 数组大小
// 循环链表初始化
public CircleArrayQueue(int cap){
this.arr = (T[])new Object[cap];
this.head = 0;
this.tail = 0;
this.size = cap;
}
// 入队方法
public void offer(T data){
// 判断循环队列是否已满,满了就直接return
if((tail + 1) % size == head){
return;
}
arr[tail] = data; // 向尾加入元素
tail = (tail + 1) % size; // 将尾指针后移1,考虑端点情况处理
}
// 出队方法
public T poll(){
// 循环队列为空则直接返回null
if(isEmpty()){
return null;
}
T pollData = arr[head]; // 找到出队元素
arr[head] = null; // 清除出队位置的元素
head = (head + 1) % size; // 将尾指针后移1,考虑端点情况处理
return pollData;
}
// 判断循环队列是否为空
public boolean isEmpty(){
return head == tail;
}
// 测试
public static void main(String[] args) {
CircleArrayQueue<String> arrayQueue = new CircleArrayQueue<>(5);
arrayQueue.offer("a");
arrayQueue.offer("b");
arrayQueue.offer("c");
arrayQueue.offer("d");
arrayQueue.offer("e");
arrayQueue.offer("f");
System.out.println(arrayQueue);
String poll1 = arrayQueue.poll();
System.out.println("出队元素:" + poll1);
String poll2 = arrayQueue.poll();
System.out.println("出队元素:" + poll2);
}
}
来源:https://blog.csdn.net/qq_40436854/article/details/120497409
0
投稿
猜你喜欢
- 1. 面试第一步,自我介绍。这个自我介绍,在整个面试当中可以说是第一步,如果你能把你想说的重点说出来,把面试官带到你准备好的技术点中,可以说
- 本文实例为大家分享了android TextView跑马灯效果的具体代码,供大家参考,具体内容如下一、要点设置四个属性android:sin
- 用java压缩/解压文件: import java.io.*; import java.awt.*; import java.aw
- 这篇文章主要介绍了springboot如何使用AOP做访问请求日志,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价
- 本文主要给大家介绍java的InputStream 流的使用。(1)FileInputstream: 子类,读取数据的通道使用步骤:1.获取
- 本文研究的主要是Java回调函数与观察者模式的实现,具体介绍和实现代码如下。观察者模式(有时又被称为发布(publish )-订阅(Subs
- 我们在学习接口的时候。能够在里面做一些方法的调用。不过今天所要讲的JDBC,虽然也是连接数据库的一种接口,不过与类接口有着很大的区别,大家要
- 前言:我们每天都在编写Java代码,编译,执行。很多人已经知道Java源代码文件(.java后缀)会被Java编译器编译为字节码文件(.cl
- [LeetCode] 3. Longest Substring Without Repeating Characters 最长无重复字符的子
- java解析json数组最简单的json数组[ { &quo
- 概述JavaScript是目前web开发中不可缺少的脚本语言,js不需要编译即可运行,运行在客户端,需要通过浏览器来解析执行JavaScri
- 实践过程效果代码public partial class Form1 : Form{ public Form1()
- 1.引言在开发中,拖放是一种比较常见的手势操作,使用它能够让应用的交互更加地便捷和友好,本文将简要介绍如何为Android中的View添加拖
- 前言AndroidStudio升级到3.0之后,gradle版本也随之升级到了3.0.0版本。当gradle插件升级到3.0.0及以上后,我
- 年纪大了,以前做过的东西过阵子还是会忘,今天使用jenkins持续集成工具时用到了eclipse上传新maven工程至svn,上传完毕后改了
- MongoDB是介于关系数据库和非关系数据库之间的一种产品,文件的存储格式为BSON(一种JSON的扩展),这里就主要介绍Java通过使用m
- 前两天发现 idea 终于更新了2020.1版本,新增了好多的特性,这里不介绍,主要写一下中文插件的安装首先下载新版 安装包 https:/
- 了解YMP框架YMP于2014年10月25日正式发布1.0版本,在此之前就已在实际项目中得到广泛使用,从最初仅限团队内部使用,到合作伙伴的开
- 一、synchronized 有不足新事物的出现要不是替代老事物,要么就是对老事物的补充JUC 的 locks 就是对 synchroniz
- 只能输入数字:"^[0-9]*$"。只能输入n位的数字:"^\d{n}$"。只能输入至少n位的数字: