- 队列是一种只允许在一端进行插入,另一端进行删除先进先出的线性表
- 和栈有相似之处(只许在一端插入删除,先进后出),可以进行对比的理解和记忆
关于队列来说,一般有以下规定
- 队尾(
rear
): 只能从队尾添加
元素, 一般叫做enQueue
, 入队 - 队头(
front
): 只能从队头移除
元素, 一般叫做deQueue
, 出队
- 队尾(
- 同样的,可以通过动态数组或双向链表来实现队列(推荐双向链表,因为队主要是在头尾进行操作,使用没有优化过的动态数组的话时间复杂度可能会比较高)
常用的队列分为以下几类
- 普通队列
- 双端队列
- 循环队列
- 循环双端队列
循环队列和循环双端队列使用并不多,但是可以学到新的思路以及动态数组的一些优化方法
队列
接口设计
- 队列(Queue)除了基本的
size
、isEmpty
、clear
等方法,主要就是入队(enQueue
)和出队(deQueue
)操作了
public class Queue<E> {
// 使用双向链表实现队列
private List<E> list = new DoubleLinkedList<>();
// 元素的数量
public int size();
// 是否为空
public boolean isEmpty();
// 入队
public void enQueue(E element);
// 出队
public E deQueue();
// 获取队列的头元素
public E front();
// 清空队列
public void clear();
}
代码实现
实现思路和栈很相似,将(双向)链表作为队的成员变量,调用链表的方法实现队列
package top.hellocode.Queue;
import java.util.LinkedList;
import java.util.List;
/**
* @author HelloCode
* @site https://www.hellocode.top
* @date 2022年05月25日 20:14
*/
public class Queue<E> {
// 使用双向链表实现队列
private List<E> list = new LinkedList<>();
// 元素的数量
public int size(){
return list.size();
}
// 是否为空
public boolean isEmpty(){
return list.isEmpty();
}
// 入队
public void enQueue(E element){
list.add(element); // 链表默认添加到队尾
}
// 出队
public E deQueue(){
return list.remove(0); // 删除表头元素并返回
}
// 获取队列的头元素
public E front(){
return list.get(0);
}
// 清空队列
public void clear(){
list.clear();
}
}
双端队列
- 双端队列(Deque)主要操作和队列一样,就是入队和出队
- 不过通过名字也可以看出来,双端队列是在队头队尾都能够添加和删除
- 整体实现思路还是一样,只不过部分地方小改即可
接口设计
public class Deque<E> {
private List<E> list = new DoubleLinkedList<>();
// 元素的数量
public int size();
// 队列是否为空
public boolean isEmpty();
// 从队尾入队
public void enQueueRear(E element);
// 从队头出队
public E deQueueFront();
// 从队头入队
public void enQueueFront(E element);
// 从队尾出队
public E deQueueRear();
// 获取队列的头元素
public E front();
// 获取队列的尾元素
public E rear();
// 清空队列
public void clear();
}
代码实现
package top.hellocode.Queue;
import top.hellocode.List.LinkedList;
import top.hellocode.List.List;
/**
* @author HelloCode
* @site https://www.hellocode.top
* @date 2022年05月25日 20:20
*/
public class Deque<E> {
private List<E> list = new LinkedList<>();
// 元素的数量
public int size() {
return list.size();
}
// 队列是否为空
public boolean isEmpty() {
return list.isEmpty();
}
// 从队尾入队
public void enQueueRear(E element) {
list.add(element); // 链表默认添加到表尾
}
// 从队头出队
public E deQueueFront() {
return list.remove(0); // 删除表头元素并返回
}
// 从队头入队
public void enQueueFront(E element) {
list.add(0, element); // 添加元素到链表表头
}
// 从队尾出队
public E deQueueRear() {
return list.remove(list.size() - 1); // 移除链表表尾元素并返回
}
// 获取队列的头元素
public E front() {
return list.get(0);
}
// 获取队列的尾元素
public E rear() {
return list.get(list.size() - 1);
}
// 清空队列
public void clear(){
list.clear();
}
}
循环队列
- 循环队列使用数组实现,是对动态数组的优化,具体优化方案可以查看【动态数组】一文中最后的优化说明部分
- 这里加入了front指针,用来记录队列的队头位置
这里只有队头指针front,并没有队尾指针rear,是因为队尾可以通过front + size - 1
计算出来,没必要浪费多余的空间来记录队尾
接口设计
public class CircleQueue<E> {
// 记录第0个元素的索引
private int front;
// 当前队列存储的元素个数
private int size;
// 用来存储元素的数组
private E[] elements;
// 当前队列存储的元素数量
public int size();
// 当前队列是否为空
public boolean isEmpty();
// 入队
public void enQueue(E element);
// 出队
public E deQueue();
// 查看索引为0的元素
public E front();
}
代码实现
- 使用数组实现循环队列,主要操作就是入队和出队操作,这里需要扩容,和动态数组的扩容类似
- 除了出入队操作,还需要注意循环队列中元素索引位置的计算以及front指针的控制
构造方法
public class CircleQueue<E> {
// 记录第0个元素的索引
private int front;
// 当前队列存储的元素个数
private int size;
// 用来存储元素的容器
private E[] elements;
private static final int DEFAULT_CAPACITY = 10; // 数组默认容量
public CircleQueue(){ // 构造方法,使用默认容量为数组开辟空间
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
}
使用数组作为容器,构造方法中为数组开辟空间,默认容量为10
入队
- 入队时,涉及到索引计算问题,因为是循环队列(环形)
- 入队是从队尾入队,因此每次需要计算出队尾在数组中的索引
- 和动态数组一样,为了使容量能够动态增加,在入队时,我们需要判断是否需要自动扩容,不了解的话可以参考【动态数组】一文
自动扩容
- 和之前一样,我们还是开辟一个指定倍数的新数组,将元素移进新数组,改变elements的指向,释放旧数组内存
- 和之前不同的是,我们在移动元素时,有可能不是按照原数组中的顺序,而是从front指向的元素开始
- 例如,上图移动到新数组后0索引开始元素依次为:
44,55,66
,而不是66,44,55
- 我们在移动完数组后,需要将front重置(指向0索引)
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length; // 旧容量
if(oldCapacity >= capacity) return; // 不需要扩容就返回
// 计算新容量
int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为1.5倍,不理解这个算法可以查看动态数组文章
E[] newElements = (E[]) new Object[newCapacity]; // 创建新数组
for (int i = 0; i < size; i++) { // 移动元素
newElements[i] = elements[index(i)];
}
elements = newElements;
// 重置front
front = 0;
}
索引计算
- 计算公式:
(front + index) % elements.length
在运算中,加减效率肯定高于乘除、取模运算,因此,除了上面的计算公式,针对本题,我们可以有下面的优化思路
预期入队索引
=第0个元素索引
+当前队列元素个数
- 如果
预期入队索引
大于等于数组长度
,实际入队索引
=预期入队索引
-数组长度
- 如果
预期入队索引
小于数组长度
,实际入队索引
=预期入队索引
- 通过上面的优化思路,就把取模运算转化为了基本的加减运算,提高了执行效率
// 索引计算
private int index(int index) {
// return (front + index) % elements.length;
// 下面两行代码只是为了优化 % 的运算,效果和上方代码类似
index += front;
return index - (index >= elements.length ? elements.length : 0);
}
入队
// 入队
public void enQueue(E element) {
// 扩容
ensureCapacity(size + 1);
elements[index(size)] = element;
size++; // size自增
}
出队
- 在循环队列中,因为有front指针,那么每次出队就是将front位置的元素置空
- 并且将front指针后移(在末尾时又重新指向0索引处)
- size--
// 出队
public E deQueue() {
// 获取出队元素
E frontElement = elements[front];
// 将front位置元素置空
elements[front] = null;
// 更新front
front = index(1);
size--;
return frontElement;
}
完整代码
package top.hellocode.Queue;
/**
* @author HelloCode
* @site https://www.hellocode.top
* @date 2022年05月25日 20:26
*/
public class CircleQueue<E> {
// 记录第0个元素的索引
private int front;
// 当前队列存储的元素个数
private int size;
// 用来存储元素的容器
private E[] elements;
private static final int DEFAULT_CAPACITY = 10; // 数组默认容量
public CircleQueue() { // 构造方法,使用默认容量为数组开辟空间
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
// 当前队列存储的元素数量
public int size() {
return size;
}
// 当前队列是否为空
public boolean isEmpty() {
return size == 0;
}
// 入队
public void enQueue(E element) {
// 扩容
ensureCapacity(size + 1);
elements[index(size)] = element;
size++; // size自增
}
// 自动扩容
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length; // 旧容量
if(oldCapacity >= capacity) return; // 不需要扩容就返回
// 计算新容量
int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为1.5倍,不理解这个算法可以查看动态数组文章
E[] newElements = (E[]) new Object[newCapacity]; // 创建新数组
for (int i = 0; i < size; i++) { // 移动元素
newElements[i] = elements[index(i)];
}
elements = newElements;
// 重置front
front = 0;
}
// 索引计算
private int index(int index) {
// return (front + index) % elements.length;
// 下面两行代码只是为了优化 % 的运算,效果和上方代码类似
index += front;
return index - (index >= elements.length ? elements.length : 0);
}
// 出队
public E deQueue() {
// 获取出队元素
E frontElement = elements[front];
// 将front位置元素置空
elements[front] = null;
// 更新front
front = index(1);
size--;
return frontElement;
}
// 查看索引为0的元素
public E front() {
return elements[front];
}
// 清空
public void clear(){
for (int i = 0; i < size; i++){
elements[i] = null;
}
front = 0;
}
}
循环双端队列
- 循环双端队列就是两端都可以插入和删除的循环队列
- 队头出队、队尾入队以及其他的基本操作都和循环队列一致
- 需要添加的就是从队头入队、队尾出队
接口设计
public class CircleDeque<E> {
// 存储队头(首元素)元素的下标
private int front;
private int size;
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;
public CircleDeque() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
// 元素的数量
public int size();
// 队列是否为空
public boolean isEmpty();
// 从队尾入队
public void enQueueRear(E element);
// 从队头出队
public E deQueueFront();
// 从队头入队
public void enQueueFront(E element);
// 从队尾出队
public E deQueueRear();
// 获取队列的头元素
public E front();
// 获取队列的尾元素
public E rear();
}
代码实现
- 入队时仍然可以像循环队列一样,定义一个index方法查找索引
- 因为在队头入队,可以理解为给-1位置添加元素
- 当index为负数时,在循环队列中的索引就应该是
index + elements.length
- 因此对比循环队列中的index方法,需要改进一下,使其支持循环双端队列的索引计算
// 索引计算
private int index(int index) {
// return (front + index) % elements.length;
// 下面两行代码只是为了优化 % 的运算,效果和上方代码类似
index += front;
if(index < 0) return index + elements.length;
return index - (index >= elements.length ? elements.length : 0);
}
从队头入队时,因为改变了队头位置,所以需要更新front
同理,从队尾出队时,因为没改变队头位置,所以不需要更新front
package top.hellocode.Queue;
/**
* @author HelloCode
* @site https://www.hellocode.top
* @date 2022年05月25日 20:27
*/
public class CircleDeque<E> {
// 存储队头(首元素)元素的下标
private int front;
private int size;
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;
public CircleDeque() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
// 元素的数量
public int size(){
return size;
}
// 队列是否为空
public boolean isEmpty(){
return size == 0;
}
// 从队尾入队
public void enQueueRear(E element){
ensureCapacity(size + 1);
elements[index(size)] = element;
size++;
}
// 从队头出队
public E deQueueFront(){
E frontElement = elements[front];
elements[front] = null;
front = index(1);
size--;
return frontElement;
}
// 从队头入队
public void enQueueFront(E element){
ensureCapacity(size + 1);
front = index(-1);
elements[front] = element;
size++;
}
// 从队尾出队
public E deQueueRear(){
E rearElement = elements[size - 1];
elements[size - 1] = null;
size--;
return rearElement;
}
// 获取队列的头元素
public E front(){
return elements[index(size - 1)];
}
// 获取队列的尾元素
public E rear(){
return elements[index(front)];
}
// 索引计算
private int index(int index) {
// return (front + index) % elements.length;
// 下面两行代码只是为了优化 % 的运算,效果和上方代码类似
index += front;
if(index < 0) return index + elements.length;
return index - (index >= elements.length ? elements.length : 0);
}
// 自动扩容
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length; // 旧容量
if(oldCapacity >= capacity) return; // 不需要扩容就返回
// 计算新容量
int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为1.5倍,不理解这个算法可以查看动态数组文章
E[] newElements = (E[]) new Object[newCapacity]; // 创建新数组
for (int i = 0; i < size; i++) { // 移动元素
newElements[i] = elements[index(i)];
}
elements = newElements;
// 重置front
front = 0;
}
}
整体上和循环队列类似,只需要注意一下出入队操作和index索引计算方法即可