一、先进先出（FIFO）
队列是一种操作受限的线性表，只允许在队头进行删除操作，在队尾进行添加操作。向队尾添加元素叫做入队，从队头删除元素叫做出队。
适用场景：对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过队列来实现请求排队。比如，线程池、连接池、消息队列等。
二、队列的实现
队列可以用数组来实现，叫做顺序队列，也可以用链表来实现，叫做链式队列。
队列支持的操作：
- 入队（enqueue）
- 出队（dequeue）
- 队列空（isEmpty）
- 队列满（isFull）
- 元素数量（size）
2.1 数组实现（顺序队列）
/**
* 顺序队列
*
* @author Luwei
* @since 2023-09-23 15:01:26
*/
public class ArrayQueue<T> {
private Object[] items;
private int capacity = 0;
private int head = 0;
private int tail = 0;
/**
* 构造方法
*
* @param capacity 队列初始容量
*/
public ArrayQueue(int capacity) {
this.capacity = capacity;
items = new Object[capacity];
}
/**
* 默认构造方法，默认初始容量为 10
*/
public ArrayQueue() {
this(10);
}
/**
* 入队
*
* @param element 入队元素
* @return 入队是否成功
*/
public boolean enqueue(T element) {
if (tail == capacity) { // 队尾没有空间
if (head == 0) { // 队头也没有空间
return false;
}
System.arraycopy(items, head, items, 0, tail - head);
tail -= head;
head = 0;
}
items[tail] = element;
tail++;
return true;
}
/**
* 出队
*
* @return 队头元素，队空返回 null
*/
public T dequeue() {
if (head == tail) { // 队空
return null;
}
T element = (T) items[head];
head++;
return element;
}
/**
* 获取队列大小
*
* @return 队列元素数量
*/
public int size() {
return tail - head;
}
}2.2 链表实现（链式队列）
/**
* 链式队列
*
* @author Luwei
* @since 2023-09-23 17:19:38
*/
public class LinkedQueue<T> {
private Node<T> head;
private Node<T> tail;
private int size;
/**
* 构造方法，使用带头双向链表
*/
public LinkedQueue() {
size = 0;
head = new Node<>(null, null, null);
tail = head;
}
/**
* 入队
*
* @param element 入队元素
* @return 入队是否成功
*/
public boolean enqueue(T element) {
Node<T> newNode = new Node<>(tail, element, null);
tail.next = newNode;
tail = newNode;
size++;
return true;
}
/**
* 出队
*
* @return 队头元素，队空返回 null
*/
public T dequeue() {
if (size == 0) { // 队空
return null;
}
Node<T> tmp = head.next;
head.next = tmp.next;
if (tmp.next == null) { // 只剩最后1个元素
tail = head;
} else {
tmp.next.prev = head;
}
size--;
return tmp.item;
}
/**
* 获取队列大小
*
* @return 队列元素数量
*/
public int size() {
return size;
}
private static class Node<T> {
private Node<T> prev;
private T item;
private Node<T> next;
public Node(Node<T> prev, T item, Node<T> next) {
this.prev = prev;
this.item = item;
this.next = next;
}
}
}三、应用广泛的几种队列
3.1 循环队列
3.2 阻塞队列