Java代码实现循环队列的示例代码
作者:1 Byte 时间:2023-11-23 23:51:25
循环队列结构
队列特点
队列为一种特殊的线性表,特殊之处在于它只允许在表的前端(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
标签:Java,循环队列
0
投稿
猜你喜欢
C#检查指定对象是否存在于ArrayList集合中的方法
2023-07-28 00:45:17
在Maven下代理服务器设定的方式
2023-10-15 02:17:13
Java8使用stream实现list中对象属性的合并(去重并求和)
2023-06-23 13:44:40
C#开发中的垃圾回收机制简析
2022-08-06 14:10:56
详谈jvm--Java中init和clinit的区别
2022-01-10 10:35:22
C#实现启用与禁用本地网络的方式小结【3种方式】
2022-04-21 18:45:14
Spring-boot的debug调试代码实例
2023-10-17 04:49:01
SpringBoot项目中分页插件PageHelper无效的问题及解决方法
2021-07-08 23:25:55
Android音频开发之音频采集的实现示例
2022-04-12 16:28:31
深入讲解Java Maven配置
2022-07-01 05:09:21
java中for和forEach的速度比较实例Demo
2022-06-20 07:09:58
Android提高之BroadcastReceiver实例详解
2021-12-13 20:22:22
深入探讨Linux静态库与动态库的详解(一看就懂)
2023-07-04 01:02:28
浅谈Android onTouchEvent 与 onInterceptTouchEvent的区别详解
2021-05-30 02:56:55
Java程序员面试中的多线程问题总结
2021-12-12 07:48:33
C# winform程序读取文本中的值实例讲解
2023-03-17 21:36:51
C#实现的sqlserver操作类实例
2023-04-24 12:13:06
spring AOP的After增强实现方法实例分析
2023-06-10 13:52:06
解决BeanUtils.copyProperties无法成功封装的问题
2023-11-23 14:59:23
解决Mybatis的@Param()注解导致分页失效的问题
2022-05-01 13:24:53