Java数组队列概念与用法实例分析

2023-07-28 14:12:14 182

本文实例讲述了Java数组队列概念与用法。分享给大家供大家参考，具体如下：

一.队列的概念

（1）队列也是一种线性结构

（2）相比数组，队列对应的操作是数组的子集

（3）只允许在一端插入数据操作，在另一端进行删除数据操作，进行插入操作的一端称为队尾（入队列），进行删除操作的一端称为队头（出队列）

（4）队列是一种先进先出的数据结构（FIFO）

此处我们先来学习一下顺序队列 ，顺序队列 就是用数组实现：比如有一个ｎ个元素的队列，数组下标0的一端是队头，入队操作就是通过数组下标一个个顺序追加，不需要移动元素，但是如果删除队头元素，后面的元素就要往前移动，对应的时间复杂度就是O(n)。

对于队列，我们关注的相关实现如下：

二、代码实现

对于该节的相关代码，我们新建一个package（Queue）,同时为了理解方便，此时把动态数组相关代码拷贝到该包中。

1.先创建一个Queue接口，里面定义上面所述的方法

packageQueue;

publicinterfaceQueue{
//获取队列中元素个数
intgetSize();

//队列中元素是否为空
booleanisEmpty();

//入队列
voidenqueue(Ee);

//出队列
Edequeue();

//获取队首元素
EgetFront();
}

2.创建一个类ArrayQueue实现Queue接口并重写Object类的toString()方法

packageQueue;

publicclassArrayQueueimplementsQueue{
privateDynamicArrayarray;


//构造函数，传入队列的容量capacity构造函数
publicArrayQueue(intcapacity){
array=newDynamicArray(capacity);
}

//无参构造函数，默认队列的容量capacity=10
publicArrayQueue(){
array=newDynamicArray();
}

//获取队列中元素数据是否为空
@Override
publicbooleanisEmpty(){
returnarray.isEmpty();
}

//获取队列中元素个数
@Override
publicintgetSize(){
returnarray.getSize();
}

//获取队列的容量
publicintgetCapacity(){
returnarray.getCapacity();
}

//入队操作
@Override
publicvoidenqueue(Ee){
array.addLast(e);
}

//出队操作
@Override
publicEdequeue(){
returnarray.removeFirst();
}

//获取队首元素
@Override
publicEgetFront(){
returnarray.getFirst();
}

//重写object类的toString方法
@Override
publicStringtoString(){
StringBuilderres=newStringBuilder();
res.append("Queue:");
res.append("front[");//体现左侧为队首
for(inti=0;i
3.测试
新建一个TestMain类，添加一个main函数来测试我们编写好的ArrayQueue类
相关代码如下：
packageQueue;

publicclassTestMain{
publicstaticvoidmain(String[]args){
ArrayQueuequeue=newArrayQueue();
for(inti=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算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》
希望本文所述对大家java程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

Java数组队列概念与用法实例分析

一.队列的概念

二、代码实现

三、数组队列的复杂度分析

热门推荐

随机推荐