服务器IP做网址打开网站,专注江苏网站建设,江西响应式网页建设价格,wordpress yeti1.92前言看过笔者前两篇介绍的 Java版数据结构 数组和 栈的盆友#xff0c;都给予了笔者一致的好评#xff0c;在这里笔者感谢大家的认可#xff01;#xff01;#xff01;由于本章介绍的数据结构是 队列#xff0c;在队列的实现上会基于前面写的 动态数组来实现#xff0c…前言看过笔者前两篇介绍的 Java版数据结构 数组和 栈的盆友都给予了笔者一致的好评在这里笔者感谢大家的认可由于本章介绍的数据结构是 队列在队列的实现上会基于前面写的 动态数组来实现而 队列又和 栈不论是从特点上和操作上都有类似之处所以在这里对这两种数据结构不了解的朋友可以去看一下笔者前两篇文章介绍的数据结构 数组和 栈这里笔者把链接贴出来看过的盆友可以跳过此步骤...Java版-数据结构-数组Java版-数据结构-栈介绍队列是一种特殊的线性表它只允许在表的前端front进行删除操作而在表的后端rear进行插入操作和栈一样队列是一种操作受限制的线性表。进行插入操作的端称为队尾进行删除操作的端称为队头。队列的操作方式和 栈类似唯一的区别在于队列只允许新数据在后端rear进行添加。特点队列是一种线性结构只能从一端队尾添加元素从另一端队首取出元素先进先出First In First OutFIFO之前在介绍栈的时候通过示意图来帮助大家了解什么是栈这里我仍采用示意图形式向大家演示队列常用的两个操作 入队操作和 出队操作。队列入队操作这里我们可以形象地想成我们到银行办理业务排队的场景现在A、B、C三个元素分别到银行柜台排成一条队办理业务我们都是文明的孩纸总不能插队O(∩_∩)O哈依次排队的元素是A、B、C。队列出队操作当元素 A办理完业务时当前是元素 A先离开队列然后是元素 B最后是元素 C我们时刻要牢记队列入队是从 队尾一端进行入队出队是从 队首一端进行出队是一种先进先出的数据结构。本文会介绍队列的两张实现方式一种是数组队列另外一种是循环队列考虑篇幅长度原因本篇我们暂时只介绍数组队列循环队列放在下一篇介绍。数组队列底层基于数组实现底层原理分析现在我们声明一个数组的长度capacity3元素个数为size0的int类型数组的空队列在这里假设对队列的 队首为数组的 左侧 队尾为数组的 右侧示意图如下:现在如果我们有四个元素A、B、C、D要入队元素 A入队元素 A已经入队了现在开始元素 B入队元素 A和元素 B已经入队了现在开始元素 C入队元素 A、 B和 C已经分别入队了现在如果我们要开始元素 D入队根据我们之前定义的动态数组的特性如果元素 D进行入队操作会发现此时我们的数组已经满了这时候数组会自动地 扩容扩容的原理新建一个容量是原数组容量两倍的数组把原数组中的元素依次拷贝到新的数组中最后引用指向新的数组的原来的两倍具体扩容多少盆友可以自行设置示意图如下到这里我们已经完成了元素:A、B、C、D的入队操作了现在我们来看一下它们的出队操作根据队列的特性队列是一种 先进先出的数据结构之前入队操作顺序依次是 A-B-C-D那么出队操作顺序仍然是 A-B-C-D现在我们来看一下元素 A和元素 B出队后的示意图元素 C和 D的出队原理和元素 A出队的原理一样直至全部出队完成变成空队列在元素出队的过程中相应地也会进行缩容操作之前笔者这边定义当数组中元素的个数size等于数组容量capacity的一半时数组会进行缩容操作这也正是动态数组的特点。了解了数组队列的底层原理之后接下来我们用代码来实现一下建议盆友在看之前自己可以尝试写一下然后在看这样印象可能会比较深刻O(∩_∩)O哈队列基本操作向队列中添加元素入队void enqueue(E e);从队列中取出元素出队E dequeue();获取队首元素E getFront();获取队列中元素个数int getSize(); 判断队列是否为空boolean isEmpty();代码实现接口定义 Queuepublic interface QueueE {/*** 入队** param e*/void enqueue(E e);/*** 出队** return*/E dequeue();/*** 获取队首元素** return*/E getFront();/*** 获取队列中元素的个数** return*/int getSize();/*** 判断队列是否为空** return*/boolean isEmpty();
}DynamicArrayQueue 类实现接口 Queuepublic class DynamicArrayQueueE implements QueueE {/*** 用数组存放队列中元素的个数*/private DynamicArrayE dynamicArray;/*** 指定容量初始化队列** param capacity*/public DynamicArrayQueue(int capacity) {dynamicArray new DynamicArray(capacity);}/*** 默认容量初始化队列*/public DynamicArrayQueue() {dynamicArray new DynamicArray();}Overridepublic void enqueue(E e) {dynamicArray.addLast(e);}Overridepublic E dequeue() {return dynamicArray.removeFirst();}Overridepublic E getFront() {return dynamicArray.getFirst();}Overridepublic int getSize() {return dynamicArray.getSize();}Overridepublic boolean isEmpty() {return dynamicArray.isEmpty();}Overridepublic String toString() {return DynamicArrayQueue{ 【队首】dynamicArray dynamicArray }【队尾】;}
}测试类 DynamicArrayQueueTestpublic class DynamicArrayQueueTest {Testpublic void testArrayQueue() {// 指定容量capacity6初始化队列DynamicArrayQueueString dynamicArrayQueue new DynamicArrayQueue(3);System.out.println(初始队列 dynamicArrayQueue);// 准备入队元素ListString 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{【队首】dynamicArrayDynamicArray{data[null, null, null], size0,capacity3}}【队尾】元素A、B、C入队DynamicArrayQueue{【队首】dynamicArrayDynamicArray{data[A, B, C], size3,capacity3}}【队尾】元素D入队发生扩容DynamicArrayQueue{【队首】dynamicArrayDynamicArray{data[A, B, C, D, null, null], size4,capacity6}}【队尾】元素A出队发生缩容DynamicArrayQueue{【队首】dynamicArrayDynamicArray{data[B, C, D], size3,capacity3}}【队尾】元素B出队DynamicArrayQueue{【队首】dynamicArrayDynamicArray{data[C, D, null], size2,capacity3}}【队尾】细心的盆友会发现因为队列的底层是数组来实现的队列的出队操作实际上就是删除数组中的第一个元素后面的所有元素都要往前面挪一位其实这样性能是比较低下的时间复杂度是O(n)级别的。我们想如果元素进行出队操作后能否不挪动后面的元素还能维持队列的特性这样问题不就解决了吗盆友可以自行思考一下。完整版代码GitHub仓库地址Java版数据结构-队列数组队列 欢迎大家【关注】和【Star】本篇完成的数组队列是基于之前【Java版-数据结构-数组】动态数组来实现的下一篇笔者会给大家介绍用循环队列来解决数组队列带来的性能问题。接下来笔者还会一一的实现其它常见的数组结构。静态数组动态数组栈数组队列循环队列链表循环链表二分搜索树优先队列堆线段树字典树AVL红黑树哈希表....持续更新中欢迎大家关注公众号小白程序之路whiteontheroad第一时间获取最新信息
