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

网友投稿 237 2022-12-12


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

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

一.队列的概念

(1)队列也是一种线性结构

(2)相比数组,队列对应的操作是数组的子集

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

(4)队列是一种先进先出的数据结构(FIFO)

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

对于队列,我们关注的相关实现如下:

二、代码实现

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

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

package Queue;

public interface Queue {

//获取队列中元素个数

int getSize();

//队列中元素是否为空

boolean isEmpty();

//入队列

void enqueue(E e);

//出队列

E dequeue();

//获取队首元素

E getFront();

}

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

package Queue;

public class ArrayQueue implements Queue {

private DynamicArray array;

//构造函数,传入队列的容量capacity构造函数

public ArrayQueue(int capacity) {

array = new DynamicArray(capacity);

}

//无参构造函数,默认队列的容量capacity=10

public ArrayQueue() {

array = new DynamicArray();

}

//获取队列中元素数据是否为空

@Override

public boolean isEmpty() {

return array.isEmpty();

}

//获取队列中元素个数

@Override

public int getSize() {

return array.getSize();

}

//获取队列的容量

public int getCapacity() {

return array.getCapacity();

}http://

//入队操作

@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 queue = new ArrayQueue();

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算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。


版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:Spring FactoriesLoader机制实例详解
下一篇:Java表格JTable代码实例解析
相关文章

 发表评论

暂时没有评论,来抢沙发吧~