Java数组队列 Java数组队列概念与用法实例分析
WFaceBoss 人气:0本文实例讲述了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程序设计有所帮助。
加载全部内容