数组队列

一.队列的概念

(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类

相关代码如下:

 1 package Queue;
 2 
 3 public class TestMain {
 4     public static void main(String[] args) {
 5         ArrayQueue<Integer> queue = new ArrayQueue<Integer>();
 6         for (int i = 0; i < 10; i++) {
 7             queue.enqueue(i);
 8             System.out.println(queue);
 9 
10             if(i%3==2){//每添加3个元素出队列一个
11                 queue.dequeue();
12                 System.out.println(queue);
13             }
14 
15         }
16 
17     }
18 }

对于第7行代码是测试入队列操作的,第10、11行代码的意思是每添加3个元素出队列一个元素。结果为:

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

对于出队的时间复杂度为O(n)的解释:

 由于实现数组队列的底层是动态数组,入队操作就是通过数组下标一个个顺序追加,不需要移动元素,但是如果删除队头元素(removeFirst()方法),后面的元素就要往前移动,对应的时间复杂度就是O(n)。这样当有数组中有大量数据时性能肯定是不好的,下一节我们将进行改进,使得出队的时间复杂度为O(1)。

 源码地址 https://github.com/FelixBin/dataStructure/tree/master/src/Queue

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 循环队列

    (1)设一个容量为capacity=8,size=5(a,b,c,d,e)的数组,左侧为队首、右侧为队尾。

    wfaceboss
  • Python 小知识点(1)

    1.Python命名规则------>下划线连接    girl_of_wfb="lgl"

    wfaceboss
  • 使用java数组,并开始封装我们自己的数组

    今天感冒了,全身酸软无力,啥样不想做,就来学习吧,此节我们从初步使用java中提供的数组,然后分析相关情况,过渡到封装我们自己的数组。

    wfaceboss
  • 并发编程之阻塞队列

    爱撒谎的男孩
  • LeetCode 225:用队列实现栈 Implement Stack using Queues

    Implement the following operations of a stack using queues.

    爱写bug
  • Java集合--Queue(Java中实现2)

    贾博岩
  • Java数据结构和算法(五)——队列

      前面一篇博客我们讲解了并不像数组一样完全作为存储数据功能,而是作为构思算法的辅助工具的数据结构——栈,本篇博客我们介绍另外一个这样的工具——队列。栈是后进先...

    IT可乐
  • Java并发编程(六)阻塞队列

    前言 在 Android多线程(一)线程池这篇文章时,当我们要创建ThreadPoolExecutor的时候需要传进来一个类型为BlockingQueue的参数...

    用户1269200
  • 35.python 线程队列Queue-FIFO

    之前的文章中讲解很多关于线程间通信的知识,比如:线程互斥锁lock,线程事件event,线程条件变量condition 等等,这些都是在开发中经常使用的内容,而...

    猿说编程[Python和C]
  • Java阻塞队列

    ?原文地址为https://www.cnblogs.com/haixiang/p/12354520.html,转载请注明出处!

    海向

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动