本文实例讲述了Java数组队列概念与用法。分享给大家供大家参考,具体如下:
一。队列的概念,
(1)队列也是一种线性结构
(2)相比数组,队列对应的操作是数组的子集
(3)只允许在一端插入数据操作,在另一端进行删除数据操作,进行插入操作的一端称为队尾(入队列),进行删除操作的一端称为队头(出队列)
(4)队列是一种先进先出的数据结构(FIFO)
,此处我们先来学习一下顺序队列,, 顺序队列,就是用数组实现:比如有一个n个元素的队,列数组下标0的一端是队头,入队操作就是通过数组下标一个个顺序追加,不需要移动元素,但是如果删除队头元素,后面的元素就要往前移动,对应的时间复杂度就是O (n)。
对于队列,我们关注的相关实现如下:
二、代码实现
对于该节的相关代码,我们新建一个包(队列),同时为了理解方便,此时把动态数组相关代码拷贝到该包中。
1。先创建一个队列接口,里面定义上面所述的方法
包队列;
公共接口Queue{//获取队列中元素个数
int getSize ();//队列中元素是否为空
布尔isEmpty ();//入队列
空队列(E);//出队列
E出列();//获取队首元素
E getFront ();
}
2。创建一个类ArrayQueue实现队列接口并重写对象类的toString()方法
包队列;
公开课ArrayQueue实现Queue{
私人DynamicArray数组;//构造函数,传入队列的容量能力构造函数
公共ArrayQueue (int能力){
数组=new DynamicArray(能力);
}//无参构造函数,默认队列的容量能力=10
公共ArrayQueue () {
数组=new DynamicArray ();
}//获取队列中元素数据是否为空
@Override
公共布尔isEmpty () {
返回array.isEmpty ();
}//获取队列中元素个数
@Override
公共int getSize () {
返回array.getSize ();
}//获取队列的容量
公共int getCapacity () {
返回array.getCapacity ();
}//入队操作
@Override
公共空间排队(E E) {
array.addLast (e);
}//出队操作
@Override
公共E出列(){
返回array.removeFirst ();
}//获取队首元素
@Override
公共E getFront () {
返回array.getFirst ();
}//重写对象类的toString方法
@Override
公共字符串toString () {
StringBuilder res=new StringBuilder ();
res.append(“队列:”);
res.append(“[");//体面前现左侧为队首
for (int i=0;我& lt;array.getSize ();我+ +){
res.append (array.get (i));
如果(我!=array.getSize () - 1) {
res.append (", ");
}
}
res.append(“尾巴”);//体现右侧为队尾
返回res.toString ();
}
}
3。测试
新建一个TestMain类,添加一个主函数来测试我们编写好的ArrayQueue类
相关代码如下:
包队列;
公开课TestMain {
公共静态void main (String [] args) {
ArrayQueue队列=new ArrayQueue ();
for (int i=0;我& lt;10;我+ +){
queue.enqueue(我);
System.out.println(队列);
如果(我% 3==2){//每添加3个元素出队列一个
queue.dequeue ();
System.out.println(队列);
}
}
}
}
对于第7行代码是测试入队列操作的,第十,第十一行代码的意思是每添加3个元素出队列一个元素。结果为:
三,数组队列的复杂度分析
对于出队的时间复杂度为O (n)的解释:
,由于实现数组队列的底层是动态数组,入队操作就是通过数组下标一个个顺序追加,不需要移动元素,但是如果删除队头元素(removeFirst()方法),后面的元素就要往前移动,对应的时间复杂度就是O (n)。这样当有数组中有大量数据时性能肯定是不好的,下一节我们将进行改进,使得出队的时间复杂度为O (1)。
