Java 循环队列/环形队列的实现流程
之前，我们使用链表实现了基础队列，链接放在这里可以去康康哟
Java栈和基础队列的实现详解
之所以没有选择数组来实现，是因为每有一个元素出队，数组中所有剩下的元素都需要向前移动一次，因此没有链表高效。
此时，我们就引出了循环队列的概念。
循环队列，又称环形队列，逻辑上是一个环，物理上依然是线性表。
head-指向队列的第一个元素
tail-指向队列最后一个元素的下一个位置
当tail走到数组末尾时，下一步再次返回数组头部（从0开始）
出队之后的元素就访问不到了，此时逻辑上已经将它删除了，tail向后走到该位置时覆盖它即可。此时就解决了数组队列需要一直搬运元素的问题。
了解循环队列的概念之后，我们就能明白它的几个基础知识:
当head == tail 时，表示队列为空
根据上面 head 和 tail 的定义，队列已满时，tail 指向最后一个元素的下一个位置，也就是head ，此时我们就无法区分环形队列到底是已满还是为空。所以我们在环形队列的数组中浪费一个空间，在区分数组是否已满，如下图，就是一个已满的队列
那么如何移动 tail 指针使他返回数组头部呢？我们运用取模操作：
tail = ( tail + 1 ) % 数组.length;
根据上式我们就能判断队列是否已满的方法：
( tail + 1 ) % 数组.length == head;
此时 head 和 tail 引用向后移动时，不能简单的 +1，要 ++ 之后对数组长度取模，这样就可以返回数组头部继续向后移动:
head = ( head +1 ) % 数组.length;
tail = ( tail +1 ) % 数组.length;
那么如何获取当前队列最后一个元素的索引呢?
图①中最后一个元素的索引就是 tail -1
图②的tail恰好在数组第一个位置，这时最后一个元素下标就是 数组.length -1
综上：数组最后一个元素的索引lastIndex
lastIndex = tail == 0 ? 数组.length -1 : tail -1;
代码实现：
public interface Queue<E> {
void offer(E val);//入队
E poll();//出队，返回出队的值
E peek();//返回队首元素
boolean isEmpty();//判断是否为空
}
import java.util.NoSuchElementException;
//基于整型的循环队列
public class LoopQueue implements Queue<Integer>{
private Integer[] data;
private int head;//队首元素
private int tail;//队尾元素的下一个位置
private int size;//当前元素个数
public LoopQueue(int n){
//n为希望保存的元素个数
//在循环队列中要浪费一个元素空间，来判断是否已满，所以 +1
data = new Integer[n + 1];
}
@Override
//添加元素
public void offer(Integer val) {
if(isFull()){
throw new ArrayIndexOutOfBoundsException("queue is full, cannot offer new val");
}
data[tail] = val;
//tail向后移
tail = (tail + 1) % data.length;
size++;
}
@Override
//出队
public Integer poll() {
if (isEmpty()){
throw new NoSuchElementException("queues empty!cannot poll");
}
Integer val = data[head];
//head向后移动
head = (head + 1) % data.length;
size--;
return val;
}
@Override
public Integer peek() {
if (isEmpty()){
throw new NoSuchElementException("queues empty!cannot poll");
}
return data[head];
}
@Override
//判断是否为空
public boolean isEmpty() {
return tail == head;
}
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append("front[");
//取得最后一个元素的下标
int lastIndex = tail == 0 ? data.length-1 : tail-1;
for (int i = head; i != tail; ) {
sb.append(data[i]);
if (i != lastIndex){
sb.append(",");
}
i = (i+1) % data.length;
}
sb.append("]tail");
return sb.toString();
}
//判断队列是否已满
public boolean isFull(){
return (tail + 1) % data.length == head;
}
}
//代码测试
public class LoopQueueTest {
public static void main(String[] args) {
Queue<Integer> loopQueue = new LoopQueue(5);
for (int i = 0; i < 5; i++) {
loopQueue.offer(i+1);
}
System.out.println(loopQueue);
// loopQueue.offer(1);
System.out.println(loopQueue.poll());
System.out.println(loopQueue);
}
}
运行结果：
到此这篇关于Java 循环队列/环形队列的实现流程的文章就介绍到这了,更多相关Java 循环队列内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
Java语言通过三种方法实现队列的示例代码
目录 队列 图解 数组模拟队列 队列优化—循环队列 代码 使用java内部队列 代码 队列 队列是一种特殊的线性表,只允许在表的前端进行删除操作,在表的后端进行插入操作. 队列是一个有序列表,可以用数组或是链表来实现. 遵循先入先出的原则.即:先存入队列的数据,要先取出.后存入的要后取出. 就相当于我们日常生活中的排队,先来先服务,后来的只能在后面进行排队等待. 图解 数组模拟队列 通过对定义的了解,发现队列很像我们的数组,那我们是不是可以通过数组来模拟队列,下面我们来实践一下. 首先先分析一下
-
java实现队列queue数据结构详解
目录 概念 队列中两个主要操作 队列遵循以下条件: 队列的数组实现 总结 概念 队列是一种非原始(特殊)的线性表,是一种先进先出(FIFO)的数据结构.它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作. FIFO:first input first output,即先添加的元素,先移除,最后添加的元素,最后移除. 工作方式类似于商场排队结账情形: 数组模拟队列图示: 队列中两个主要操作 插入值操作:insert ——> enqueue(入队) ——>参数是要插
-
Java队列数据结构的实现
1.队列的基本概念 什么是队列? 队列是一种特殊的线性表 它只允许在表的前端(队头)进行删除操作 在表的后端(队尾)进行插入操作 队列是一个有序表(可以用数组或链表实现) 队列先进先出 队列开辟的是一块连续的空间 顺序队列中的溢出现象: 真溢出:当队列满时,做进栈运算产生空间溢出的现象. 假上溢:由于入队和出队操作中,头尾指针只增加不减小,致使被删元素的空间永远无法重新利用.当队列中实际的元素个数远远小于向量空间的规模时,也可能由于尾指针已超越向量空间的上界而不能做入队操作. 2.循环队列 在实
-
Java栈和基础队列的实现详解
目录 栈(stack) 栈支持的三个核心操作: 栈的常见实际应用: 栈的实现 队列 无论是哪种队列,都必须支持三个核心操作: 基础队列的实现 栈和队列:都是线性表,都是基于List基础上的实现 线性表:数组,链表,字符串,栈,队列 元素按照一条“直线”排列,线性表这个结构中,一次添加单个元素 栈(stack) 一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作.进行数据插入和删除操作的一端称为栈顶,另一端称为栈底.栈中的数据元素遵守后进先出LIFO(Last In First Out)
-
java数组实现循环队列示例介绍
从顶部进去数据,从底部出来数据,用数组实现队列,但是下面这个队列,只能进行一次存数值,取数值,不够完善. import java.util.Scanner; public class ArrayQueueDemo { public static void main(String[]args){ //定义队列大小maxsize ArrayQueue arrayQueue=new ArrayQueue(3); Scanner scanner=new Scanner(System.in); char
-
Java 循环队列/环形队列的实现流程
之前,我们使用链表实现了基础队列,链接放在这里可以去康康哟 Java栈和基础队列的实现详解 之所以没有选择数组来实现,是因为每有一个元素出队,数组中所有剩下的元素都需要向前移动一次,因此没有链表高效. 此时,我们就引出了循环队列的概念. 循环队列,又称环形队列,逻辑上是一个环,物理上依然是线性表. head-指向队列的第一个元素 tail-指向队列最后一个元素的下一个位置 当tail走到数组末尾时,下一步再次返回数组头部(从0开始) 出队之后的元素就访问不到了,此时逻辑上已经将它删除了,tail
-
Java 循环队列/环形队列的实现流程
之前,我们使用链表实现了基础队列,链接放在这里可以去康康哟 Java栈和基础队列的实现详解 之所以没有选择数组来实现,是因为每有一个元素出队,数组中所有剩下的元素都需要向前移动一次,因此没有链表高效. 此时,我们就引出了循环队列的概念. 循环队列,又称环形队列,逻辑上是一个环,物理上依然是线性表. head-指向队列的第一个元素 tail-指向队列最后一个元素的下一个位置 当tail走到数组末尾时,下一步再次返回数组头部(从0开始) 出队之后的元素就访问不到了,此时逻辑上已经将它删除了,tail
-
java数组实现队列及环形队列实现过程解析
这篇文章主要介绍了java数组实现队列及环形队列实现过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 代码内容 ArrayQueue---用数组实现队列 package com.structure; import java.util.Scanner; /** * @auther::9527 * @Description: 数组模拟队列 * @program: jstl2 * @create: 2019-10-05 08:58 */ pub
-
Java 单向队列及环形队列的实现原理
目录 队列的特点 图解实现过程: 优化解决--环形队列实现思路 环形队列各步骤及各方法实现讲解 最后: 队列的特点 1.可以使用数组和链表两种方式来实现. 2.遵循先入先出(FIFO)的规则,即先进入的数据先出. 3.属于有序列表. 图解实现过程: 1.定义一个固定长度的数组,长度为maxSize. 2.设置两个指针first = -1(指向队列第一个数据的前一位,这样保证在添加第一个数据以后头指针为0,和数组的下标一样,且用于操作出队)和last = -1(指向队尾,用于操作入队). 3
-
Java循环队列原理与用法详解
本文实例讲述了Java循环队列原理与用法.分享给大家供大家参考,具体如下: 在正式进行循环队列学习之前,我们先来看看在顺序队列中删除队首元素出现的问题 (1)设一个容量为capacity=8,size=5(a,b,c,d,e)的数组,左侧为队首.右侧为队尾. (2)出队一个元素后,需整体往前移动一位 #出队 #2整体前移一位 关于该种操作方式我们很容易得出时间复杂度为O(n). 这时我们就想可不可以在出队元素后,整体元素不往前移,而是在数组中记下队首front是谁,同时队尾tail指向在下一次元
-
java中用数组实现环形队列的示例代码
本篇文章主要讲述了使用数组实现环形队列的思路以及具体代码 一.队列是什么 我们先来看下百科的解释: 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,队列是一种操作受限制的线性表.进行插入操作的端称为队尾,进行删除操作的端称为队头. 总结起来两点: 1.一种线性表 2.添加操作只能在表尾,删除操作在表头(先进先出) 二.实现队列的思路 1.初始化一个空队列 初始化一个大小固定的数组,并将头指针,尾指针都指向下表为0的位置,但其
-
Java循环队列与非循环队列的区别总结
非循环循环队列 判满:(rear+1) % maxsize == front 判空:front == rear 队列元素个数:rear = (rear + maxsize - front) % maxsize front指针移动方式:front = (front + 1) % maxsize rear指针移动方式:rear= (rear+ 1) % maxsize import java.awt.Font; import java.util.Scanner; import javax.manag
-
Java队列篇之实现数组模拟队列及可复用环形队列详解
队列简介 队列是一个有序列表,可以用数组或是链表来实现. 遵循先入先出的原则.即先存入队列的数据,先取出,后存入的后取出. 示意图:(使用数组模拟队列示意图) 有两个分别指向头部和尾部的"指针". 数组模拟队列(无法复用) 1.实现思路 队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的声明如下图,其中maxSize是该队列的最大容量. 因为队列的输出.输入是分别从前后端来处理,因此需要两个变量front及rear分别记录队列前后端的下标,front会随着数据输出而改变
-
java数据结构基础:顺序队列和循环队列
目录 队列: 顺序队列: 代码实现: 循环队列: 代码实现: 总结 队列: 队列是一种受限制的线性表 只允许在表的一端进行插入,另一端进行删除 插入的一端称作队尾,删除的一端称作队头 具有先进先出的特性 顺序队列: 队列底层数据采用数组存储 设置队头指针front指向队头元素前一个位置,初始值为-1 设置队尾指针rear指向队尾元素,初始值为-1 判满:rear == maxSize - 1 判空:rear == front 代码实现: //顺序队列 public class ArrayQueu
-
Java多线程(单例模式,堵塞队列,定时器)详解
目录 一.单例模式 饿汉模式 懒汉模式 懒汉模式 二.堵塞队列 实现BlockingQueue 三.定时器 总结 一.单例模式 单例模式是一种设计模式,针对一些特定的场景,研究出对应的解决方案,.有些对象在代码中只应该有一个实例,单例模式就是强制某个类只能有一个实例. 单例模式的实现,主要依托于static关键字(被static 修饰的成员,静态成员,把当前的成员变成类属性而不是实例属性~)每个类对象只有一份 单例模式实现有两种,饿汉模式和懒汉模式 饿汉模式 饿汉模式实现:实例创建出现在"类加载