Java数组队列概念与用法实例分析
作者:WFaceBoss 发布时间:2023-11-18 04:18:31
本文实例讲述了Java数组队列概念与用法。分享给大家供大家参考,具体如下:
一.队列的概念
(1)队列也是一种线性结构
(2)相比数组,队列对应的操作是数组的子集
(3)只允许在一端插入数据操作,在另一端进行删除数据操作,进行插入操作的一端称为队尾(入队列),进行删除操作的一端称为队头(出队列)
(4)队列是一种先进先出的数据结构(FIFO)
此处我们先来学习一下顺序队列 ,顺序队列 就是用数组实现:比如有一个n个元素的队列,数组下标0的一端是队头,入队操作就是通过数组下标一个个顺序追加,不需要移动元素,但是如果删除队头元素,后面的元素就要往前移动,对应的时间复杂度就是O(n)。
对于队列,我们关注的相关实现如下:
二、代码实现
对于该节的相关代码,我们新建一个package(Queue),同时为了理解方便,此时把动态数组相关代码拷贝到该包中。
1.先创建一个Queue接口,里面定义上面所述的方法
package Queue;
public interface Queue<E> {
//获取队列中元素个数
int getSize();
//队列中元素是否为空
boolean isEmpty();
//入队列
void enqueue(E e);
//出队列
E dequeue();
//获取队首元素
E getFront();
}
2.创建一个类ArrayQueue实现Queue接口并重写Object类的toString()方法
package Queue;
public class ArrayQueue<E> implements Queue<E> {
private DynamicArray<E> array;
//构造函数,传入队列的容量capacity构造函数
public ArrayQueue(int capacity) {
array = new DynamicArray<E>(capacity);
}
//无参构造函数,默认队列的容量capacity=10
public ArrayQueue() {
array = new DynamicArray<E>();
}
//获取队列中元素数据是否为空
@Override
public boolean isEmpty() {
return array.isEmpty();
}
//获取队列中元素个数
@Override
public int getSize() {
return array.getSize();
}
//获取队列的容量
public int getCapacity() {
return array.getCapacity();
}
//入队操作
@Override
public void enqueue(E e) {
array.addLast(e);
}
//出队操作
@Override
public E dequeue() {
return array.removeFirst();
}
//获取队首元素
@Override
public E getFront() {
return array.getFirst();
}
//重写object类的toString方法
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Queue:");
res.append("front [");//体现左侧为队首
for (int i = 0; i < array.getSize(); i++) {
res.append(array.get(i));
if (i != array.getSize() - 1) {
res.append(",");
}
}
res.append("] tail");//体现右侧为队尾
return res.toString();
}
}
3.测试
新建一个TestMain类,添加一个main函数来测试我们编写好的ArrayQueue类
相关代码如下:
package Queue;
public class TestMain {
public static void main(String[] args) {
ArrayQueue<Integer> queue = new ArrayQueue<Integer>();
for (int i = 0; i < 10; i++) {
queue.enqueue(i);
System.out.println(queue);
if(i%3==2){//每添加3个元素出队列一个
queue.dequeue();
System.out.println(queue);
}
}
}
}
对于第7行代码是测试入队列操作的,第10、11行代码的意思是每添加3个元素出队列一个元素。结果为:
三、数组队列的复杂度分析
对于出队的时间复杂度为O(n)的解释:
由于实现数组队列的底层是动态数组,入队操作就是通过数组下标一个个顺序追加,不需要移动元素,但是如果删除队头元素(removeFirst()方法),后面的元素就要往前移动,对应的时间复杂度就是O(n)。这样当有数组中有大量数据时性能肯定是不好的,下一节我们将进行改进,使得出队的时间复杂度为O(1)。
源码地址 https://github.com/FelixBin/dataStructure/tree/master/src/Queue
希望本文所述对大家java程序设计有所帮助。
来源:https://www.cnblogs.com/wfaceboss/p/10627316.html
猜你喜欢
- 这些属性都是可外部配置且可动态替换的,既可以在典型的 Java 属性文件中配置,亦可通过 properties 元素的子元素来传递。例如:&
- java加载properties文件的六种方法总结java加载properties文件的六中基本方式实现java加载properties文件
- 一、抽象类1.抽象类1.1抽象类的定义在Java面向对象当中,所有的对象都是用过类进行描绘的,但是并不是所有的类都是用来描绘对象的,如果一个
- 前天在做批量数据导入新增时,要对数据进行有效性判断,其中还要去除重复,如果没出现linq的话可能会新声明一个临时对象集合,然后遍历原始数据判
- Mybatis条件if test使用枚举值1.正确package com.weather.weatherexpert.common.util
- 里氏替换原则,OCP作为OO的高层原则,主张使用“抽象(Abstraction)”和“多态(Polymorphism)”将设计中的静态结构改
- 前言在网络通信中,通信传输数据容易被截取或篡改,如果在传输用户隐私数据过程中,被不法分子截取或篡改,就可能导致用户受到伤害,比如被诈 骗,所
- 1.点击上传按钮进行如下操作,通过表单名称以及input名称获取相应的值,对于上传的文件,使用.files来获取,因为包含文件的上传,所以采
- 1.首先解释一下什么是方法重载?方法重载是指在同一个类中方法同名,参数不同,调用时根据实参的形式,选择与他匹配的方法执行操作的一种技术。这里
- 1.WinMergeWinMerge是一款运行于Windows系统下的文件比较和合并工具https://winmerge.org/downl
- 一、MyBatisPlusConfig中配置分页插件/** * 配置分页插件 * @
- Spring Boot 自动装配最重要的注解@SpringBootApplication@Target(ElementType.TYPE)@
- 类加载子系统classLoader 只负责对字节码文件的加载,至于是否可以运行,还要看执行引擎。加载的类信息存放于方法区的内存空间,除了类信
- 1 问题手写一个程序,完成List集合对象的逆序遍历2 方法创建List接口的多态对象向创建好list集合添加元素使用hasPrevious
- 一、类加载流程类加载的流程可以简单分为三步:加载连接初始化而其中的连接又可以细分为三步:验证准备解析下面会分别对各个流程进行介绍。1.1 类
- AOP我想大家都很清楚,有时候我们需要处理一些请求日志,或者对某些方法进行一些监控,如果出现例外情况应该进行怎么样的处理,现在,我们从spr
- 简单之美,springmvc,mybatis就是一个很好的简单集成方案,能够满足一般的项目需求。闲暇时间把项目配置文件共享出来,供大家参看:
- 本文实例讲述了C#实现身份证号码验证的方法。分享给大家供大家参考。具体实现方法如下:随着现在互联网的发展,越来越多的注册用户的地方都用到了身
- maven打包指定jdk的版本问题今天遇到个问题,项目中新写了一个接口,其中用到了lambda表达式,本地跑是没问题的,但提交到gitLab
- 创建hander文件夹在 java 源码目录下创建hander文件夹, 在该文件夹下创建CustomAuthenticationFailHa