?博客主页: XIN-XIANG荣
?系列专栏:【Java实现数据结构】
?一句短话: 难在坚持,贵在坚持,成在坚持!
一. 什么是队列
1. 队列的特点
队列也是一种组织数据的方式 , 队列中的元素具有先进先出的特点 , 是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表 .
队列的几个术语：
- 进行插入操作的一端称做队尾（tail/rear）。
- 进行删除操作的一端称做队首或队头（head/front）。
- 向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素。
- 从队列中删除元素称为出队或离队，元素出队后，其后继元素就成为队首元素。
2. 队列的模拟实现
队列可以使用链表或者顺序表来实现 , 在Java集合框架中的队列就是用双链表来实现的 , 下文会介绍到双端队列和循环队列 , 在这里采用单链表来实现队列 .
我们这里设置单链表中的两个引用head和tail用来指向头节点和尾节点 , 需要注意的是我们应该让单链表的头做队头 , 单链表的尾做队尾 , 也就是从单链表的尾入队 , 头出队 , 此时入队和出队操作的时间时间复杂度都为O(1) ; 而如果反过来入队使用头插 , 入队的时间复杂度为O(1) , 此时出队要删除单链表最后一个节点 , 需要先找到其前一个节点 , 出队的时间复杂度就为O(N)了;
如果使用双链表来实现栈的话那就简单了 , 由于是是双向的 , 不管哪一端来做队头/队尾 , 时间复杂度都为O(1) ; 会了单链表的 , 双链表的不在话下了 .
MyQueue.java
public class MyQueue {
static class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public ListNode head;
public ListNode tail;
public int usedSzie;
public void offer(int val) {
ListNode node = new ListNode(val);
if(this.head == null) {
this.head = node;
this.tail = node;
}else {
this.tail.next = node;
this.tail = this.tail.next;
}
this.usedSzie++;
}
public int poll() {
if(this.head == null) {
throw new MyEmptyQueueException("当前队列为空");
}
int ret = this.head.val;
this.head = this.head.next;
//如果只有一个节点,要将tail置空
if(this.head == null) {
this.tail = null;
}
this.usedSzie--;
return ret;
}
public int peek() {
if(this.head == null) {
throw new MyEmptyQueueException("当前队列为空");
}
return this.head.val;
}
public boolean empty() {
return this.head == null;
}
public int getUsedSzie() {
return this.usedSzie;
}
}
MyEmptyQueueException.java
public class MyEmptyQueueException extends RuntimeException{
public MyEmptyQueueException() {
}
public MyEmptyQueueException(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则表示队列为空。
- 数组下标循环的小技巧
- 往后走(offset 小于 array.length): index = (index + offset) % array.length
这里的意思是 , 长度为9的循环链表中 , 7下标位置 , 偏移4个位置 , 到了2位置
- 往前走(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系列方法更加合适。
代码示例 :
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
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());
}
}