队列
文章结构
- 什么是队列
- 实现队列
- 顺序队列
- 链式队列
- 循环队列
- Java中的队列
1. 什么是队列
队列也是一种操作受限的数据结构，数据只能从一端进入，从另一端取出，数据遵循先进先出，后进后出的原则。
数组和队列的对比示意图
队列的应用非常的广泛，比如循环队列，阻塞队列，并发队列。他们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如说线程中，当没有空闲资源了的时候，我们就会用到各种队列来缓存提交的请求。
2. 实现队列
2.1 顺序队列
顺序队列使用数组来存储队列元素，要考虑的主要问题有
- 如何判断队列为空？
我们定义两个索引head和tail，head表示队头下标，tail表示队尾下标。当head==tail的时候，我们认为队列为空。
- 如何判断队列满了？
当tail== n（数组的大小）的时候，说明数组的尾部已经没有空间存储元素了，这时我们去看队头，如果head== 0，说明没有出队操作，队头也满了，此时整个队列就满了，所以队列满的条件是：tail== n&&head== 0
- 什么是数据搬移？
当tail已经到了队尾，但是head!=0，说明我们有一些元素出队了，队头有空元素，我们可以通过将后面的数据搬迁到前面来将空闲空间腾到队尾，以便继续存放入队元素
- 何时进行数据搬移？
如果我们在每次出队的时候搬迁的话，每次出队操作的时间复杂度将都是O(n)；我们可以将搬迁工作放到入队时，当队尾没有空闲空间了（tail== n）了，再做一次搬移操作。
顺序队列
顺序队列数据搬迁
代码实现
public class MyArrayQueue<E> {
private Object[] datas;
private int size;
private int head = 0;
private int tail = 0;
public MyArrayQueue(int capacity) {
datas = new Object[capacity];
size = capacity;
}
/**
* 入队
*
* @param e
* @return
*/
public boolean enqueue(E e) {
if (tail == size) {
//tail==size&&head==0表示队列已经满了，无法在插入元素
if (head == 0) {
return false;
} else {
//head>0,表示队列头部有空闲位置，可以通过数据搬迁，将空闲位置挪到队列尾部
System.arraycopy(datas, head, datas, 0,
tail - head);
tail = tail - head;
head = 0;
}
}
datas[tail] = e;
tail++;
return true;
}
/**
* 出队
*
* @return
*/
public E dequeue() throws Exception {
//队列为空
if (isEmpty()) {
throw new Exception("queue is empty");
}
//返回队列头部的元素，同时head向后移动一位
E item = (E) datas[head];
datas[head] = null;
head++;
return item;
}
/**
* 队列是否为空
*
* @return
*/
public boolean isEmpty() {
if (head == tail) {
return true;
} else {
return false;
}
}
}
完整代码和测试用例，请查看github之MyArrayQueue和MyArrayQueueTest
2.2 链式队列
链式队列使用链表来存储队列的元素，使用链表来存储队列，不需要考虑队列是否满了，数据搬迁的问题，只需要考虑队列是否为空就行
- 如何判断队列为空？
指向队列头部的指针如果为空，则队列为空
链式队列
代码实现
public class MyLinkedQueue<E> {
private Node<E> head;
private Node<E> tail;
/**
* 入队
*
* @param e
* @return
*/
public boolean enqueue(E e) {
Node<E> node = new Node<>(e);
if (tail == null) {
head = node;
tail = node;
} else {
tail.next = node;
tail = tail.next;
}
return true;
}
/**
* 出队
*
* @return
*/
public E dequeue() {
if (head == null) {
return null;
} else {
E e = head.item;
head = head.next;
if (head == null) {//head等于null，表示队列中的元素已经全部出队了，这时要将tail置空，避免tail一直引用元素，造成元素无法回收
tail = null;
}
return e;
}
}
private static class Node<E> {
E item;
Node<E> next;
public Node(E e) {
this.item = e;
}
}
}
完整代码和测试用例，请查看github之MyLinkedQueue和MyLinkedQueueTest
2.3 循环队列
循环队列使用数组来存储队列元素，当队列存储到数组尾部时，不是去移动数据，而是去检测数组头部是否有空元素，如果有，则将要存入的元素存储到数组的前面去，类似这样将数组循环使用。循环队列要考虑的问题
- 如何判断队列为空？
队列为空的条件，依然可以是head=tail
- tail到达数组尾部的时候，如何计算下一个存储位置的索引
tail = (tail+1)%n;同样的数组最后一个元素出栈时，head的计算也是：head=（head+1）%n;
- 如何判断队列满了？
循环队列会循环利用head移动之后空闲出来的空间,当所有空间都用完了的时候，tail==head，但是这个条件和队列为空的判断条件一样，我们不能再用这个条件来判断队列是否满了，所以只能牺牲一个空间，让队列留出一个空间不存放元素，这样队列为满的判断条件就是head==（tail+1）%n
循环队列示意图
循环队列队满的情况
代码实现
public class MyCircularQueue<E> {
private Object[] datas;
private int size;
private int head = 0;
private int tail = 0;
public MyCircularQueue(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("queue capacity must more than zero");
}
datas = new Object[capacity];
size = capacity;
}
/**
* 入队
*
* @param e
* @return
*/
public boolean enqueue(E e) {
if ((tail + 1) % size == head) {//表示队列已经满了
return false;
}
datas[tail] = e;
tail = (tail + 1) % size;
return true;
}
/**
* 出队
*
* @return
*/
public E dequeue() throws Exception {
//队列为空
if (isEmpty()) {
throw new Exception("queue is empty");
}
//返回队列头部的元素，同时head向后移动一位
E item = (E) datas[head];
datas[head] = null;
head = (head + 1) % size;
return item;
}
/**
* 队列是否为空
*
* @return
*/
public boolean isEmpty() {
if (head == tail) {
return true;
} else {
return false;
}
}
}
完整代码和测试用例，请查看github之MyCircularQueue和MyCircularQueueTest
3. Java中的队列
Java中内置了很多的队列，系统学习可以参考作者Java3y的 我用45张图将18种Queue，给你整得明明白白
说明
文中图片来源：极客时间，王争《数据结构与算法之美》
