数据结构----队列,双向队列(Deque),循环队列
1.队列的基本知识
队列的基本特性就是先进先出(FIFO),也就是第一个进去的元素第一个出来。即队列就是一个只允许在一端进行插入,在另一端进行删除操作的线性表。Queue接口与List、Set同一级别,都是继承了Collection接口。
2.队列按照实现方式也分为两种:
①单向队列(Queue):只能在一段插入数据,另一端删除数据。
②双向队列(Deque):每一段都可以进行插入数据和删除数据的操作。
3.双向队列(LinkedList实现了Deque接 口)
双向队列是一个线性Collection,既然是线性表,按照存储方式那就有两种:基于数组的顺序存储方式和基于链表的链式存储方式。支持在两端插入和移出元素。Deque是(double ended queue)双端队列的缩写,通常读为deck。大多数的Deque实现对于他们能够包含的元素数没有固定的限制,但是此接口即支持有容量限制的双端队列,也支持没有固定大小限制的双端队列。此接口提供了两端访问元素的方法,提供了插入,删除和检查元素的方法。
即双向队列可以当栈使用也可以当队列来使用。
(1)队列与双向队列方法的比较
(2)栈与双向队列方法的比较
4.队列的实现
①顺序队列的实现
顺序队列是基于数组实现的,针对于队列的操作主要有:插入,删除,查找元素,队列长度,是否为空。
②链式队列的实现
链式队列与顺序队列有所不同,每个节点不仅仅保存当前元素的值,还有只想下一个元素的指针
③循环队列
循环队列是一种顺序存储结构表示的队列,为了解决假溢出问题而将他设置成头尾相接的循环队列,他的基本操作如下:
1、初始化循环队列
2、销毁循环队列
3、清空循环队列
4、检测循环队列是否为空
5、返回循环队列的元素个数
6、返回循环队列头元素
7、向队尾插入元素
8、删除并返回队头元素
9、遍历循环队列
在Java中,我们可以将循环队列视作一个类,通过成员变量数组来表示一组地址连续的存储单元,再定义两个成员变量front和rear,将循环队列的基本操作定义成类的方法,循环效果则用“模”运算实现,以此来实现循环队列。这样,初始化循环队列就是将类实例化,销毁就是销毁实例化出来的对象。