队列,又称为伫列(queue),计算机科学中的一种抽象资料型别,是先进先出(FIFO, First-In-First-Out)的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。
队列顾名思义就是我们现实中的队列,用于顺序处理数据。它的 FIFO 的性质在对于顺序排列数据非常有用,高并发下可以用消息队列进行流量削峰,多线程下可以用全局的队列可以让数据变为同步处理。
队列的基本操作
操作 | API | 描述 |
---|---|---|
添加数据 | EnQueue |
新元素入队 |
移除数据 | DeQueue |
队首元素出队 |
查看队首 | Peek |
查看队首元素 |
一个基本的队列必须实现以上的 API,有的地方会写道最基本的操作是 EnQueue
和 DeQueue
,但这两个仅仅只是队列的数据操作,但我们对队列的所有操作并非一直都是数据读写操作。
Peek
操作是对队列的状态的描述之一,Peek
操作可以让我们知道队列是否为空,队首元素的状态,而队列的长度、队首之后的其他元素这些信息并不是我们必须关心的。
队列的实现
队列的实现分为两种:链表实现和顺序表实现
链表实现并不需要关心栈的容量,实现起来较为方便。顺序表实现由于在初始化队列的时候需要设定顺序表的长度,因此涉及到了判断是否队列满和是否扩容的操作;同时由于队列需要操作队首和队尾两个指针,因此在指针不段右移的时候最终会触底,前面已经出队的空间将会被浪费,因此我们对于队列的顺序实现,一般都采用循环队列的方式,即当队列触底发生时,将指针移回数组顶部。
先定义一个队列的虚基类,继承 Vector,设定好必需的 API:
public abstract class Vector<E> {
/**
* 容器当前元素数量
*/
protected int size = 0;
/**
* 判断该容器是否为空
*
* @return 为空则返回 true
*/
public synchronized boolean isEmpty() {
return this.size == 0;
}
/**
* 获取概况容器中元素的数量
*
* @return 元素的数量
*/
public synchronized int getSize() {
return this.size;
}
}
public abstract class Queue<E> extends Vector<E> {
/**
* 入队
*
* @param element 待入队元素
* @return 若成功入队返回 true
*/
public abstract boolean enQueue(E element);
/**
* 元素出队
*
* @return 元素
*/
public abstract E deQueue();
/**
* 获取栈顶部的元素
*
* @return 容器头部的元素
*/
public abstract E peek();
}
队列的顺序实现
/**
* 队列的链表实现
*
* @param <E> 元素类型
*/
public class LinkedListQueue<E> extends Queue<E> {
SingleLinkedListNode<E> head;
SingleLinkedListNode<E> tail;
public LinkedListQueue() {
this.head = null;
this.tail = null;
}
@Override
public synchronized boolean enQueue(E element) {
SingleLinkedListNode<E> node = new SingleLinkedListNode<>(element, null);
if (isEmpty()) {
this.head = node;
} else {
this.tail.next = node;
}
this.tail = node;
this.size += 1;
return true;
}
@Override
public E deQueue() {
if (isEmpty())
return null;
SingleLinkedListNode<E> firstNode = this.head;
this.head = firstNode.next;
if (this.size == 1) {
this.tail = null;
}
this.size -= 1;
return firstNode.data;
}
@Override
public E peek() {
if (isEmpty())
return null;
return this.head.data;
}
}
队列的链表实现
/**
* 队列的顺序实现 - 循环队列实现
* @param <E>
*/
public class ArrayQueue<E> extends Queue<E> {
private int factor = 1;
private int capacity;
private boolean isExtendible = true;
private Object[] elements;
/**
* 头指针应如果和尾指针相同,表示空队列
*/
private int head = 0;
private int tail = 0;
public ArrayQueue(int capacity) {
this.capacity = capacity;
this.elements = new Object[capacity];
}
public ArrayQueue(int capacity, int factor) {
this.factor = factor;
this.capacity = capacity;
this.elements = new Object[capacity];
}
public ArrayQueue(int capacity, boolean isExtendible, int factor) {
this.capacity = capacity;
this.isExtendible = isExtendible;
this.factor = isExtendible ? factor : 1;
this.elements = new Object[capacity];
}
@Override
public boolean enQueue(E element) {
return this.isExtendible ? enQueueWithExtension(element) : enQueueWithoutExtension(element);
}
/**
* 入队操作,容量不足则进行扩容操作
*
* @param element 待入队元素
* @return 若成功入队,则返回 true
*/
private boolean enQueueWithExtension(E element) {
ensureCapacity();
this.elements[this.tail] = element;
this.tail = (this.tail + 1) % this.capacity;
this.size += 1;
return true;
}
/**
* 入队操作,容量不足不允许入队
*
* @param element 待入队元素
* @return 若成功入队,则返回 true
*/
private boolean enQueueWithoutExtension(E element) {
if (this.size == this.capacity)
return false;
this.elements[this.tail] = element;
this.tail = (this.tail + 1) % this.capacity;
this.size += 1;
return true;
}
@Override
@SuppressWarnings("unchecked")
public E deQueue() {
if (isEmpty())
return null;
int idx = this.head;
this.head = (this.head + 1) % this.capacity;
this.size -= 1;
return (E) this.elements[idx];
}
@Override
@SuppressWarnings("unchecked")
public E peek() {
if (isEmpty())
return null;
return (E) this.elements[this.head];
}
private void ensureCapacity() {
if (this.size + 1 <= this.capacity * this.factor)
return;
/* 如果是正序的,则直接扩容 */
if (this.head < this.tail) {
this.capacity += 1;
this.elements = Arrays.copyOf(this.elements, this.capacity);
return;
}
/* 如果是循环的,重新排列元素 */
Object[] newElements = new Object[this.capacity + 1];
System.arraycopy(this.elements, this.head, newElements, 0, this.capacity - this.head);
System.arraycopy(this.elements, 0, newElements, this.capacity - this.head, this.tail);
this.head = 0;
this.tail = this.size;
this.capacity += 1;
this.elements = newElements;
}
}