【JavaDS】队列与集合Queue,Deque的理解和使用

✨博客主页: XIN-XIANG荣
✨系列专栏:【Java实现数据结构】
✨一句短话: 难在坚持,贵在坚持,成在坚持!

文章目录

一. 什么是队列

1. 队列的特点

队列也是一种组织数据的方式 , 队列中的元素具有先进先出的特点 , 是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表 .

队列的几个术语：

• 进行插入操作的一端称做队尾（tail/rear）。
• 进行删除操作的一端称做队首或队头（head/front）。
• 向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素。
• 从队列中删除元素称为出队或离队，元素出队后，其后继元素就成为队首元素。

2. 队列的模拟实现

队列可以使用链表或者顺序表来实现 , 在Java集合框架中的队列就是用双链表来实现的 , 下文会介绍到双端队列和循环队列 , 在这里采用单链表来实现队列 .

我们这里设置单链表中的两个引用head和tail用来指向头节点和尾节点 , 需要注意的是我们应该让单链表的头做队头 , 单链表的尾做队尾 , 也就是从单链表的尾入队 , 头出队 , 此时入队和出队操作的时间时间复杂度都为O(1) ; 而如果反过来入队使用头插 , 入队的时间复杂度为O(1) , 此时出队要删除单链表最后一个节点 , 需要先找到其前一个节点 , 出队的时间复杂度就为O(N)了;

如果使用双链表来实现栈的话那就简单了 , 由于是是双向的 , 不管哪一端来做队头/队尾 , 时间复杂度都为O(1) ; 会了单链表的 , 双链表的不在话下了 .

MyQueue.java

publicclassMyQueue{staticclassListNode{publicint val;publicListNode next;publicListNode(int val){this.val = val;}}publicListNode head;publicListNode tail;publicint usedSzie;publicvoidoffer(int val){ListNode node =newListNode(val);if(this.head ==null){this.head = node;this.tail = node;}else{this.tail.next = node;this.tail =this.tail.next;}this.usedSzie++;}publicintpoll(){if(this.head ==null){thrownewMyEmptyQueueException("当前队列为空");}int ret =this.head.val;this.head =this.head.next;//如果只有一个节点,要将tail置空if(this.head ==null){this.tail =null;}this.usedSzie--;return ret;}publicintpeek(){if(this.head ==null){thrownewMyEmptyQueueException("当前队列为空");}returnthis.head.val;}publicbooleanempty(){returnthis.head ==null;}publicintgetUsedSzie(){returnthis.usedSzie;}}

MyEmptyQueueException.java

publicclassMyEmptyQueueExceptionextendsRuntimeException{publicMyEmptyQueueException(){}publicMyEmptyQueueException(String message){super(message);}}

3. 循环队列

上面已经实现了用链表来实现队列 , 那么用顺序表如何来实现队列呢 ; 我们知道顺序表是具有随机访问的特点的 , 将若干个元素入队后 , 每次出队操作后 , 该元素原来所在的空间就无法再使用了 , 这就使得顺序表得空间利用不充分 ;

而如果采用循环队列就可以解决这个问题 , 如果数组最后一个空间已经有了元素 , 但前面由于出队有了空缺 , 此时再有元素入队就能重新从数组的尾部跳到数组的头部 , 对已经出队的空间进行重新利用 , 这样就避免了空间的浪费 .

实现循环队列还需要考虑的一个问题是，如何确定队列是空还是满？

这里我们设置队头引用为front，队尾引用为rear，顺序表长度为len。

• 方式1：

记录队列元素个数size，当size的值与顺序表的长度相等时，代表队列已满 ; size值为0表示队列为空。

• 方式2：

使用一个boolean类型的成员变量flag标记，初始为false，当每次成功入队时将flag设置为true，成功出队时将flag设置为false ; 那么，当front == rear && flag == true表示“在入队操作之后front == rear”, 显然入队造成的front == rear的原因就是队列满了 ; **所以 ,**当rear == front && flag == true表示队列已满，同理 , 当rear == front && flag == false表示队列为空。

• 方式3：

牺牲一个单位的空间，front 就指向队列的第一个元 , rear 指向队列的最后一个元素的后一个位置 , 在每次入队前判断（rear+1）% len是否与front相等，如果相等表示队列已满，如果rear == front则表示队列为空。

• 数组下标循环的小技巧

1. 往后走(offset 小于 array.length): index = (index + offset) % array.length

这里的意思是 , 长度为9的循环链表中 , 7下标位置 , 偏移4个位置 , 到了2位置

1. 往前走(offset 小于 array.length): index = (index + array.length - offset) % array.length

这里的意思是 , 长度为9的循环链表中 , 2下标位置 , 偏移4个位置 , 到了7位置

4. 双端队列

双端队列是指两端都可以进行进队和出队操作的队列，将队列的两端分别称为前端和后端，两端都可以入队和出队。

双端队列同时遵守了先进先出和后进先出的原则，所以可以说它是一种把队列和栈相结合的一种数据结构 ;

所以双端队列既能够当队列使用，也能当栈使用，Java底层是使用双链表(LinkedList)来实现双端队列(Deque)和队列(Queue)的 ;

限制一端进行出队或入队的双端队列称为受限的双端队列。

二. 集合-Queue,Deque

1. 结构介绍

在Java中，Queue和Deque是两个接口，底层是通过双链表实现的 , 使用时必须创建LinkedList的对象 ;

这里观察Queue,Deque接口与LinkedList类关系 ;

LinkedList类实现了Queue,Deque接口，Deque接口扩展了Queue接口，三者都扩展或继承了Collection和Iterable接口。

2. 方法介绍

Queue接口提供了队列增删查改等基本操作的方法，Deque接口提供了双端队列操作的一系列方法，LinkedList类实现了Queue,Deque接口，因此可以使用Queue引用LinkedList对象当队列使用，Deque引用LinkedList对象当双端队列使用，当然也可以直接使用LinkedList引用LinkedList对象当队列，双端队列，双链表等数据结构使用。

由于在实际开发中Deque使用的并不是非常多 , 所以这里只列出Queue接口中常用的方法 :
方法****作用boolean add(E e)队尾入队，入队失败引发异常boolean offer(E e)队尾入队，入队失败不引发异常（推荐）E remove()对头出队，并返回队头元素，出队失败引发异常E poll()对头出队，并返回队头元素，出队失败不引发异常（推荐）E element()获取队头元素，获取失败引发异常E peek()获取队头元素，获取失败不引发异常（推荐）

• add系列方法与offer系列方法的区别：

两者都是在队列队头或队尾插入元素，前者（add）插入元素失败会引发异常，后者（offer）插入元素失败不会引发异常，只会以返回false的形式表示插入元素失败，如果是有容量限制的队列，使用offer系列方法更加合适。

• remove系列方法与poll系列方法的区别：

两者都是在队列队头或队尾删除并返回元素，前者（remove）删除元素失败会引发异常，后者（poll）删除元素失败不会引发异常，只会以返回null的形式表示删除元素失败，如果是有容量限制的队列，使用poll系列方法更加合适。

• get系列方法与peek系列方法的区别：

两者都是在队列队头或队尾获取并返回元素，前者（get）获取元素失败会引发异常，后者（peek）获取元素失败不会引发异常，只会以返回null的形式表示获取元素失败，如果是有容量限制的队列，使用peek系列方法更加合适。

代码示例 :

publicstaticvoidmain(String[] args){Queue<Integer> q =newLinkedList<>();
        q.offer(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);
        q.offer(5);// 从队尾入队列System.out.println(q.size());System.out.println(q.peek());// 获取队头元素
        q.poll();System.out.println(q.poll());// 从队头出队列，并将删除的元素返回if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());}}