一、队列
队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。
二、双端队列
双端队列是只既可以在表的前端进行插入和删除操作,又可以在表的后端进行插入和删除操作。
三、ArrayDeque的实现
Java中的双端队列是用数组实现的,类的全限名称是java.util.ArrayDeque,该类的声明如下:
该类继承了AbstractCollection类,实现了Deque、Cloneable和Serializable接口。实现Cloneable和Serializable接口的主要目的是为了实现克隆和序列化。
该类中定义了四个个成员变量
其中elements是数组的首地址,head是指向队首的下标,tail是指向队尾的下一个位置的下标。MIN_INITIAL_CAPACITY 定义了在创建队列是,如果有指定长度,而且指定长度小于MIN_INITIAL_CAPACITY,则使用MIN_INITIAL_CAPACITY 作为数组的最小长度。
其构造函数有一下几种:
第一种构造函数,默认情况下,数组的长度为16。
第二种构造函数,给定数组长度,则调用allocateElements()函数,分配数组空间。allocateElements()函数的实现如下:
对于一个给定长度,先判断是否小于定义的最小长度,如果小于,则使用定义的最小长度作为数组的长度。否则,找到比给定长度大的最小的2的幂数(在if里面的以为语句实现这一功能)。
第三种构造函数,给定一个集合,先分配空间,然后添加到集合中。
从上面的三种构造函数中,可以判断出来,数组的长度是2的幂数,定义为2的幂数个人认为有两个原因:
1.伙伴系统
操作系统分配内存的方法使用伙伴系统的话,每一块的大小都是2的幂数,如果分配的内存大小为2的幂数,可以减少内存分配的时间。
伙伴系统在百度百科中的解释:http://baike.baidu.com/view/4935190.htm
2.插入和删除的速度
对于数组,如果head的值为0,时,在队首插入元素,有一种方法是将全部元素都向后移动一位,然后将新的元素插入。这样子的话,插入和删除的速度会非常慢,特别是在元素很多的情况下。另一种方法就是在head的值为0时,在队首插入元素,可以将head的值置为(数组的长度-1)。也就是将新插入的元素放到数组的最后,以此类推。在计算插入元素位置下标的时候,数组长度是2的幂数就用处了。下面是插入元素时,计算插入位置的值的语句
length-1的值为高位全为0,低位全为1,通过按位相与,可以得出应该插入元素的位置。
然后就是该类的一些方法了,有点面向对象的思想的都应该会想到,应该有头插,头删,尾插,尾删等等一些操作,在此就不一一列出了,实现起来也比较简单。关键还是要了解ArrayDeque的实现机制。
分享到:
相关推荐
数据结构与算法课设——医院候诊管理系统.docx数据结构与算法课设——医院候诊管理系统.docx数据结构与算法课设——医院候诊管理系统.docx数据结构与算法课设——医院候诊管理系统.docx数据结构与算法课设——医院...
自己用C++实现的双端队列数据结构,通过测试,并有注释。有需要的朋友可以看一看
VC++2010编程演练数据结构《1》循环双端队列
这是我学数据结构时做的作业,绝对可以运行!纯粹的交流学习,希望可以帮助大家!
模拟数据按客户到达的先后顺序依次由键盘输入,对应每位客户有两个数据,到达时刻和需要办理业务的时间。 Input 第一行:一天内的客户总人数n 第二行:第一个客户的到达时刻和需要办理业务的时间 第三行:第二个...
用双端队列(deque)实现栈的功能, 数据结构作业 栈(先进后出)的一种数据结构 内含一个cpp文件和两个头文件。
软 件 学 院 上 机 实 验 报 告 课程名称: 数据结构 实验项目: 队列的应用 实 验 室: 耘 慧420 姓 名: 学 号 专业班级: 实验时间: 2016.11.17 "实验成绩 "评阅教师 " " " " "实验目的及要求 " "(一) 目的 " "1...
输入若干个整数, 以0结束, 利用入队的操作生成一个循环队列, 求该队列的长度。
数据结构课设——小大根交替堆实现的双端优先级队列及应用
主要介绍了Java数据结构之队列的简单定义与使用方法,简单描述了队列的功能、特点,并结合java实例形式分析了队列的简单定义与使用方法,需要的朋友可以参考下
数据结构之队列数据结构之队列数据结构之队列数据结构之队列数据结构之队列数据结构之队列数据结构之队列数据结构之队列数据结构之队列
本文实例讲述了Python实现的数据结构与算法之双端队列。分享给大家供大家参考。具体分析如下: 一、概述 双端队列(deque,全名double-ended queue)是一种具有队列和栈性质的线性数据结构。双端队列也拥有两端:队...
双端队列(deque,double-ended queue),是一种具有队列和栈的性质的数据结构。 双端队列中每一端,都可以进行存入和取出,去其中一段,都像一个栈一样。 存取也只限定在两端,不能在中间 双端队列的实现 通过...
数据结构之队列,队列增删改查
标签:Java 数据结构 算法 作者 : Maxchen 版本 : V1.0.0 日期 : 2020/3/29 目录1.队列的概念2.数组模拟队列3.队列运行测试 1.队列的概念 队列同样是一种特殊的线性表,其插入和删除的操作分别在表的两端进行,...
熟悉队列的定义,队列的特点以及队列的基本操作。能够根据实际情况选择合适的存储结构,解决实际问题。 2.实验内容: 利用循环队列模拟舞伴配对问题: 1、利用循环队列模拟舞伴配对问题。在舞会上,男、女各自排成...
双端队列,在基础类上派生 用来实现平移递推滤波数据存储
数据结构中队列的具体实现,给出了代码,可以加强对队列这一数据结构的理解和应用。希望大家下载后自己实现一下,得出正确的结果,真正的理解这一结构的思想。数据结构中队列的具体实现,给出了代码,可以加强对队列...