资讯专栏INFORMATION COLUMN

Java版-数据结构-队列(数组队列)

khs1994 / 2179人阅读

摘要:队列的操作方式和栈类似,唯一的区别在于队列只允许新数据在后端进行添加。

前言

看过笔者前两篇介绍的Java版数据结构数组的盆友,都给予了笔者一致的好评,在这里笔者感谢大家的认可!!!

由于本章介绍的数据结构是队列,在队列的实现上会基于前面写的动态数组来实现,而队列又和不论是从特点上和操作上都有类似之处,所以在这里对这两种数据结构不了解的朋友,可以去看一下笔者前两篇文章介绍的数据结构数组,这里笔者把链接贴出来(看过的盆友可以跳过此步骤...)

Java版-数据结构-数组

Java版-数据结构-栈

介绍

队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

队列的操作方式和类似,唯一的区别在于队列只允许新数据在后端(rear)进行添加。

特点

队列是一种线性结构

只能从一端(队尾)添加元素,从另一端(队首)取出元素

先进先出,First In First Out(FIFO)

之前在介绍栈的时候,通过示意图来帮助大家了解什么是栈;这里,我仍采用示意图形式向大家演示队列常用的两个操作:入队操作出队操作

队列入队操作

这里我们可以形象地想成我们到银行办理业务排队的场景,现在A、B、C三个元素分别到银行柜台排成一条队办理业务(我们都是文明的孩纸,总不能插队O(∩_∩)O哈!),依次排队的元素是:A、B、C。

队列出队操作

当元素A办理完业务时,当前是元素A先离开队列,然后是元素B,最后是元素C

我们时刻要牢记队列,入队是从队尾一端进行入队,出队是从队首一端进行出队,是一种:先进先出的数据结构。

本文会介绍队列的两张实现方式,一种是数组队列,另外一种是循环队列,考虑篇幅长度原因,本篇我们暂时只介绍数组队列,循环队列放在下一篇介绍。

数组队列(底层基于数组实现
底层原理分析

现在我们声明一个数组的长度(capacity=3),元素个数为(size=0)的int类型数组的空队列,在这里,假设对队列的队首为数组的左侧队尾为数组的右侧,示意图如下:

现在如果我们有四个元素:A、B、C、D要入队

元素A入队

元素A已经入队了,现在开始元素B入队

元素A和元素B已经入队了,现在开始元素C入队

元素ABC已经分别入队了,现在如果我们要开始元素D入队,根据我们之前定义的动态数组的特性,如果元素D进行入队操作,会发现此时我们的数组已经满了,这时候数组会自动地扩容(扩容的原理:新建一个容量是原数组容量两倍的数组,把原数组中的元素依次拷贝到新的数组中,最后引用指向新的数组)的原来的两倍(具体扩容多少,盆友可以自行设置)示意图如下:

到这里我们已经完成了元素:A、B、C、D的入队操作了,现在我们来看一下,它们的出队操作,根据队列的特性,队列是一种先进先出的数据结构,之前入队操作顺序依次是:A->B->C->D,那么出队操作顺序仍然是:A->B->C->D

现在我们来看一下元素A和元素B出队后的示意图:

元素CD的出队原理和元素A出队的原理一样,直至全部出队完成,变成空队列

在元素出队的过程中,相应地也会进行缩容操作,之前笔者这边定义,当数组中元素的个数(size)等于数组容量(capacity)的一半时,数组会进行缩容操作,这也正是动态数组的特点。

了解了数组队列的底层原理之后,接下来我们用代码来实现一下(建议盆友,在看之前,自己可以尝试写一下,然后在看,这样印象可能会比较深刻O(∩_∩)O哈!)

队列基本操作

向队列中添加元素(入队)

void enqueue(E e);

从队列中取出元素(出队)

E dequeue();

获取队首元素

E getFront();

获取队列中元素个数

int getSize();

判断队列是否为空

boolean isEmpty();
代码实现

接口定义Queue

public interface Queue {
    /**
     * 入队
     *
     * @param e
     */
    void enqueue(E e);

    /**
     * 出队
     *
     * @return
     */
    E dequeue();

    /**
     * 获取队首元素
     *
     * @return
     */
    E getFront();

    /**
     * 获取队列中元素的个数
     *
     * @return
     */
    int getSize();

    /**
     * 判断队列是否为空
     *
     * @return
     */
    boolean isEmpty();
}

DynamicArrayQueue 类实现接口 Queue

public class DynamicArrayQueue implements Queue {

    /**
     * 用数组存放队列中元素的个数
     */
    private DynamicArray dynamicArray;

    /**
     * 指定容量,初始化队列
     *
     * @param capacity
     */
    public DynamicArrayQueue(int capacity) {
        dynamicArray = new DynamicArray<>(capacity);
    }

    /**
     * 默认容量,初始化队列
     */
    public DynamicArrayQueue() {
        dynamicArray = new DynamicArray<>();
    }


    @Override
    public void enqueue(E e) {
        dynamicArray.addLast(e);
    }

    @Override
    public E dequeue() {
        return dynamicArray.removeFirst();
    }

    @Override
    public E getFront() {
        return dynamicArray.getFirst();
    }

    @Override
    public int getSize() {
        return dynamicArray.getSize();
    }

    @Override
    public boolean isEmpty() {
        return dynamicArray.isEmpty();
    }

    @Override
    public String toString() {
        return "DynamicArrayQueue{" +
                "【队首】dynamicArray=" + dynamicArray + "}【队尾】";
    }
}

测试类: DynamicArrayQueueTest

public class DynamicArrayQueueTest {
    @Test
    public void testArrayQueue() {
        // 指定容量(capacity=6)初始化队列
        DynamicArrayQueue dynamicArrayQueue = new DynamicArrayQueue(3);
        System.out.println("初始队列:" + dynamicArrayQueue);

        // 准备入队元素
        List enQueueElements = Arrays.asList("A", "B", "C");

        // 元素入队
        enQueueElements.forEach(x -> dynamicArrayQueue.enqueue(x));
        System.out.println("元素A、B、C入队:" + dynamicArrayQueue);

        // 此时如果又有一个元素D入队,会发生扩容操作 (size == capacity)进行扩容
        dynamicArrayQueue.enqueue("D");
        System.out.println("元素D入队,发生扩容:" + dynamicArrayQueue);


        // 元素A出队,会发生缩容操作(size == capacity / 2)进行缩容
        dynamicArrayQueue.dequeue();
        System.out.println("元素A出队,发生缩容:" + dynamicArrayQueue);

        // 元素B出队
        dynamicArrayQueue.dequeue();
        System.out.println("元素B出队:" + dynamicArrayQueue);

    }
}

运行结果

初始队列:DynamicArrayQueue{【队首】dynamicArray=DynamicArray{data=[null, null, null], size=0,capacity=3}}【队尾】

元素A、B、C入队:DynamicArrayQueue{【队首】dynamicArray=DynamicArray{data=[A, B, C], size=3,capacity=3}}【队尾】

元素D入队,发生扩容:DynamicArrayQueue{【队首】dynamicArray=DynamicArray{data=[A, B, C, D, null, null], size=4,capacity=6}}【队尾】

元素A出队,发生缩容:DynamicArrayQueue{【队首】dynamicArray=DynamicArray{data=[B, C, D], size=3,capacity=3}}【队尾】

元素B出队:DynamicArrayQueue{【队首】dynamicArray=DynamicArray{data=[C, D, null], size=2,capacity=3}}【队尾】
细心的盆友,会发现,因为队列的底层是数组来实现的,队列的出队操作实际上就是:删除数组中的第一个元素,后面的所有元素都要往前面挪一位;其实这样性能是比较低下的,时间复杂度是O(n)级别的。

我们想如果元素进行出队操作后,能否不挪动后面的元素,还能维持队列的特性,这样问题不就解决了吗?盆友可以自行思考一下。

完整版代码GitHub仓库地址:Java版数据结构-队列(数组队列) 欢迎大家【关注】和【Star

本篇完成的数组队列是基于之前【Java版-数据结构-数组】动态数组来实现的,下一篇笔者会给大家介绍用循环队列来解决数组队列带来的性能问题。接下来,笔者还会一一的实现其它常见的数组结构。

静态数组

动态数组

数组队列

循环队列

链表

循环链表

二分搜索树

优先队列

线段树

字典树

AVL

红黑树

哈希表

....

持续更新中,欢迎大家关注公众号:小白程序之路(whiteontheroad),第一时间获取最新信息!!!

笔者博客地址:http:www.gulj.cn

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/73942.html

相关文章

  • Java-数据结构-队列(循环队列

    摘要:为了方便大家查阅,笔者在这里贴出相关的地址版数据结构数组版数据结构栈版数据结构队列数组队列为了解决数组队列带来的问题,本篇给大家介绍一下循环队列。 前情回顾 在上一篇,笔者给大家介绍了数组队列,并且在文末提出了数组队列实现上的劣势,以及带来的性能问题(因为数组队列,在出队的时候,我们往往要将数组中的元素往前挪动一个位置,这个动作的时间复杂度O(n)级别),如果不清楚的小伙伴欢迎查看阅读...

    Lin_YT 评论0 收藏0
  • 阿里 2021 最全 Java 并发编程笔记,看完我才懂了“内卷”的真正意义

    摘要:纯分享直接上干货操作系统并发支持进程管理内存管理文件系统系统进程间通信网络通信阻塞队列数组有界队列链表无界队列优先级有限无界队列延时无界队列同步队列队列内存模型线程通信机制内存共享消息传递内存模型顺序一致性指令重排序原则内存语义线程 纯分享 , 直接上干货! 操作系统并发支持 进程管理内存管...

    不知名网友 评论0 收藏0
  • Java 性能调优指南之 Java 集合概览

    摘要:单线程集合本部分将重点介绍非线程安全集合。非线程安全集合框架的最新成员是自起推出的。这是标准的单线程阵营中唯一的有序集合。该功能能有效防止运行时造型。检查个集合之间不存在共同的元素。基于自然排序或找出集合中的最大或最小元素。 【编者按】本文作者为拥有十年金融软件开发经验的 Mikhail Vorontsov,文章主要概览了所有标准 Java 集合类型。文章系国内 ITOM 管理平台 O...

    gnehc 评论0 收藏0
  • 剑指Offer(Java) 持续更新中

    摘要:面试题从尾到头打印链表输入一个链表,从尾到头打印链表每个节点的值面试题重建二叉树输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。例如输入前序遍历序列和中序遍历序列,则重建二叉树并返回。队列中的元素为类型。其中负数用补码表示。 面试题2 单例(之前有整理,略) 面试题3 二维数组中的查找 public boolean find(int target, int [][] arra...

    justCoding 评论0 收藏0
  • Java-数据结构-栈

    摘要:介绍栈是一种后进先出的线性表数据结构,分为栈顶和栈底两端,仅允许在表的一端插入元素,这一端被称为栈顶,另外一端称之为栈底。 介绍 栈是一种后进先出的线性表数据结构,分为栈顶和栈底两端,仅允许在表的一端插入元素,这一端被称为栈顶,另外一端称之为栈底。栈,只有两种操作,分为入栈(压栈)和出栈(退栈);向栈中添加元素的操作叫做入栈,相反从栈中删除元素叫做出栈。 特点 只能从栈顶添加元素或者...

    voidking 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<