Эта статья была включена вGitHub.com/VIP камень/Али…Алгоритм Иллюстрированная серия.
Урок из предыдущей статьи »В этой статье подробно объясняется «очередь», 3 способа поставить очередь вручную!》Мы знаем, что очередь (Queue) — это очередь в порядке очереди (FIFO), и мы можем использовать массивы, связанные списки и списки для реализации пользовательских очередей, а затем в этой статье мы будем систематически изучать, как реализуется официальная очередь.
В Java много очередей, например:ArrayBlockingQueue,LinkedBlockingQueue,PriorityQueue,DelayQueue,SynchronousQueueПодождите, так что они делают? Как это классифицируется?
На самом деле, эти очереди в Java можно классифицировать по разным измерениям, например, их можно классифицировать на блокирующие и неблокирующие, а также их можно классифицировать на ограниченные и неограниченные.В этой статье будут классифицироваться функции очередей, такие как : очередь с приоритетом, обычная очередь, двусторонняя очередь, очередь с задержкой и т. д.
Хотя основное внимание в этой статье уделяется функциональной интерпретации очередей, другие категории также являются важными понятиями в Java, поэтому давайте сначала рассмотрим их.
Блокирующие и неблокирующие очереди
Блокирующая очередь (Blocking Queue) обеспечивает возможность блокировкиputиtakeметоды, они связаны с временнымиofferиpollэквивалентны. Если очередь заполненаputМетод будет блокироваться до тех пор, пока не освободится место перед вставкой элемента; если очередь пуста, тоtakeМетод также блокируется до тех пор, пока элемент не будет доступен. Когда очередь никогда не заполняется,putМетоды иtakeметод никогда не будет блокироваться.
Мы можем узнать, является ли эта очередь блокирующей очередью, по имени очереди, а блокирующая очередь содержитBlockingQueueКлючевые слова, такие как следующие:
- ArrayBlockingQueue
- LinkedBlockingQueue
- PriorityBlockingQueue
- .......
Демонстрация функции блокировки очереди
Далее давайте продемонстрируем, что происходит, когда емкость очереди блокировки заполнена.Пример кода выглядит следующим образом:
import java.util.Date;
import java.util.concurrent.ArrayBlockingQueue;
public class BlockingTest {
public static void main(String[] args) throws InterruptedException {
// 创建一个长度为 5 的阻塞队列
ArrayBlockingQueue q1 = new ArrayBlockingQueue(5);
// 新创建一个线程执行入列
new Thread(() -> {
// 循环 10 次
for (int i = 0; i < 10; i++) {
try {
q1.put(i);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(new Date() + " | ArrayBlockingQueue Size:" + q1.size());
}
System.out.println(new Date() + " | For End.");
}).start();
// 新创建一个线程执行出列
new Thread(() -> {
for (int i = 0; i < 5; i++) {
try {
// 休眠 1S
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
if (!q1.isEmpty()) {
try {
q1.take(); // 出列
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}).start();
}
}
Результат выполнения приведенного выше кода выглядит следующим образом:
Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:1
Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:2
Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:3
Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:4
Mon Oct 19 20:16:12 CST 2020 | ArrayBlockingQueue Size:5
Mon Oct 19 20:16:13 CST 2020 | ArrayBlockingQueue Size:5
Mon Oct 19 20:16:14 CST 2020 | ArrayBlockingQueue Size:5
Mon Oct 19 20:16:15 CST 2020 | ArrayBlockingQueue Size:5
Mon Oct 19 20:16:16 CST 2020 | ArrayBlockingQueue Size:5
Mon Oct 19 20:16:17 CST 2020 | ArrayBlockingQueue Size:5
Mon Oct 19 20:16:17 CST 2020 | For End.
Из вышеприведенных результатов видно, что приArrayBlockingQueueКогда очередь заполнится, он войдет в блок, а когда элемент будет удален из очереди через 1 секунду, в очередь будет добавлен новый элемент.
неблокирующая очередь
Неблокирующая очередь также является обычной очередью, и ее имя не содержитBlockingQueueключевое слово, и оно не будет содержатьput иtakeметод, когда очередь заполнена, если в очереди есть новые элементы, ошибка будет возвращена напрямую, и она не будет блокироваться в ожидании добавления элементов, как показано на следующем рисунке:Типичное представление неблокирующей очереди:
ConcurrentLinkedQueue иPriorityQueue.
Ограниченная очередь и неограниченная очередь
ограниченная очередь: Относится к очереди фиксированного размера, например к очереди фиксированного размера.ArrayBlockingQueue, или размер 0SynchronousQueue.
неограниченная очередь: относится к очереди с не установленным фиксированным размером, но на самом деле, если фиксированный размер не установлен, есть значение по умолчанию, но значение по умолчанию — Integer.MAX_VALUE, конечно, такой большой емкости в действительности не будет use (больше, чем Integer.MAX_VALUE ), поэтому с точки зрения пользователя это эквивалентно «неограниченному».
Сортировать по функциям
Далее в центре внимания этой статьи.Давайте разделим очередь по функциям.Ее можно разделить на: нормальную очередь,приоритетную очередь,двойную очередь,отложенную очередь,другие очереди и т.д.Рассмотрим их отдельно.
1. Обычная очередь
Обычная очередь (Queue) — это базовая очередь, реализующая принцип «первым пришел — первым обслужен», напримерArrayBlockingQueue иLinkedBlockingQueue,вArrayBlockingQueueЭто обычная очередь, реализованная с помощью массива, как показано на следующем рисунке:
и
LinkedBlockingQueueЭто обычная очередь, реализованная с использованием связанного списка, как показано на следующем рисунке:
Общий метод
Общие методы в обычных очередях следующие:
- offer(): добавить элемент, если очередь заполнена, вернуть false напрямую, если очередь не заполнена, вставить его напрямую и вернуть true;
- poll(): удалить и вернуть элемент head очереди и вернуть null, когда очередь пуста;
- add(): добавить элемент, этот метод является простой инкапсуляцией метода предложения, если очередь заполнена, генерируется исключение IllegalStateException;
- remove(): удалить непосредственно головной элемент;
- put(): добавить элементы, если очередь заполнена, она заблокируется в ожидании вставки;
- take(): удалить и вернуть головной элемент очереди, когда очередь пуста, он заблокирует ожидание;
- peek(): запросит головной элемент очереди, но не удалит его;
- element(): Простая инкапсуляция метода просмотра. Если элемент в начале очереди существует, он будет извлечен, а не удален. Если он не существует, будет выброшено исключение NoSuchElementException.
Уведомление:Как правило, методы offer() и poll() используются вместе, методы блокировки put() и take() используются вместе, методы add() и remove() используются вместе, а offer() и poll() обычно используются вместе. используется в программах методом, поэтому эти два метода более дружелюбны и не будут сообщать об ошибках.
Далее мы используемLinkedBlockingQueueНапример, чтобы продемонстрировать использование обычной очереди:
import java.util.concurrent.LinkedBlockingQueue;
static class LinkedBlockingQueueTest {
public static void main(String[] args) {
LinkedBlockingQueue queue = new LinkedBlockingQueue();
queue.offer("Hello");
queue.offer("Java");
queue.offer("中文社群");
while (!queue.isEmpty()) {
System.out.println(queue.poll());
}
}
}
Результат выполнения приведенного выше кода выглядит следующим образом:
Hello
Java
китайское сообщество
2. Двусторонняя очередь
Двусторонняя очередь (Deque) относится к структуре данных, в которой начало и конец очереди могут быть поставлены в очередь и удалены из очереди одновременно, как показано на следующем рисунке:Далее давайте продемонстрируем двустороннюю очередь
LinkedBlockingDequeиспользование:
import java.util.concurrent.LinkedBlockingDeque;
/**
* 双端队列示例
*/
static class LinkedBlockingDequeTest {
public static void main(String[] args) {
// 创建一个双端队列
LinkedBlockingDeque deque = new LinkedBlockingDeque();
deque.offer("offer"); // 插入首个元素
deque.offerFirst("offerFirst"); // 队头插入元素
deque.offerLast("offerLast"); // 队尾插入元素
while (!deque.isEmpty()) {
// 从头遍历打印
System.out.println(deque.poll());
}
}
}
Результат выполнения приведенного выше кода выглядит следующим образом:
offerFirst
offer
offerLast
3. Приоритетная очередь
Очередь с приоритетом (PriorityQueue) — это особый вид очереди, это не очередь «первым пришел — первым вышел», а элементы с высоким приоритетом первыми выходят из очереди.
Очередь с приоритетами реализована в соответствии с бинарной кучей Структура данных бинарной кучи показана на следующем рисунке:** Существует два типа двоичных куч: максимальная куча и минимальная куча. **Выше показана максимальная куча,В максимальной куче значение любого родительского узла больше или равно значению его левого и правого дочерних узлов.
Поскольку очередь с приоритетом реализована на основе двоичной кучи, она может сначала удалить из очереди элементы с лучшим приоритетом.
Далее давайте продемонстрируем использование приоритетных очередей:
import java.util.PriorityQueue;
public class PriorityQueueTest {
// 自定义的实体类
static class Viper {
private int id; // id
private String name; // 名称
private int level; // 等级
public Viper(int id, String name, int level) {
this.id = id;
this.name = name;
this.level = level;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getLevel() {
return level;
}
public void setLevel(int level) {
this.level = level;
}
}
public static void main(String[] args) {
PriorityQueue queue = new PriorityQueue(10, new Comparator<Viper>() {
@Override
public int compare(Viper v1, Viper v2) {
// 设置优先级规则（倒序，等级越高权限越大）
return v2.getLevel() - v1.getLevel();
}
});
// 构建实体类
Viper v1 = new Viper(1, "Java", 1);
Viper v2 = new Viper(2, "MySQL", 5);
Viper v3 = new Viper(3, "Redis", 3);
// 入列
queue.offer(v1);
queue.offer(v2);
queue.offer(v3);
while (!queue.isEmpty()) {
// 遍历名称
Viper item = (Viper) queue.poll();
System.out.println("Name：" + item.getName() +
" Level：" + item.getLevel());
}
}
}
Результат выполнения приведенного выше кода выглядит следующим образом:
Имя: MySQL Уровень: 5
Имя: Redis Уровень: 3
Название: Java Уровень: 1
Из вышеприведенных результатов видно, чтоУдаление приоритетной очереди не учитывает порядок входа, всегда следует, что элемент с более высоким приоритетом удаляется из очереди первым.
4. Очередь задержки
Очередь с задержкой (DelayQueue) основана на очереди с приоритетомPriorityQueueРеализованный, он может рассматриваться как приоритетная очередь со временем в качестве единицы измерения, когда элемент, поставленный в очередь, достигает заданного времени задержки, он может быть исключен из очереди.
Давайте продемонстрируем использование очередей задержки:
import lombok.Getter;
import lombok.Setter;
import java.text.DateFormat;
import java.util.Date;
import java.util.concurrent.DelayQueue;
import java.util.concurrent.Delayed;
import java.util.concurrent.TimeUnit;
public class CustomDelayQueue {
// 延迟消息队列
private static DelayQueue delayQueue = new DelayQueue();
public static void main(String[] args) throws InterruptedException {
producer(); // 调用生产者
consumer(); // 调用消费者
}
// 生产者
public static void producer() {
// 添加消息
delayQueue.put(new MyDelay(1000, "消息1"));
delayQueue.put(new MyDelay(3000, "消息2"));
}
// 消费者
public static void consumer() throws InterruptedException {
System.out.println("开始执行时间：" +
DateFormat.getDateTimeInstance().format(new Date()));
while (!delayQueue.isEmpty()) {
System.out.println(delayQueue.take());
}
System.out.println("结束执行时间：" +
DateFormat.getDateTimeInstance().format(new Date()));
}
static class MyDelay implements Delayed {
// 延迟截止时间（单位：毫秒）
long delayTime = System.currentTimeMillis();
// 借助 lombok 实现
@Getter
@Setter
private String msg;
/**
* 初始化
* @param delayTime 设置延迟执行时间
* @param msg 执行的消息
*/
public MyDelay(long delayTime, String msg) {
this.delayTime = (this.delayTime + delayTime);
this.msg = msg;
}
// 获取剩余时间
@Override
public long getDelay(TimeUnit unit) {
return unit.convert(delayTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
}
// 队列里元素的排序依据
@Override
public int compareTo(Delayed o) {
if (this.getDelay(TimeUnit.MILLISECONDS) > o.getDelay(TimeUnit.MILLISECONDS)) {
return 1;
} else if (this.getDelay(TimeUnit.MILLISECONDS) < o.getDelay(TimeUnit.MILLISECONDS)) {
return -1;
} else {
return 0;
}
}
@Override
public String toString() {
return this.msg;
}
}
}
Результат выполнения приведенного выше кода выглядит следующим образом:
Время начала выполнения: 2020-10-20 20:17:28
сообщение 1
сообщение 2
Время окончания исполнения: 20.10.2020 20:17:31
Из приведенного выше времени окончания выполнения и времени начала выполнения видно, что как сообщение 1, так и сообщение 2 обычно реализуют функцию отложенного выполнения.
5. Другие очереди
В очереди Java есть специальная очередьSynchronousQueue, особенность в том, что внутри нет контейнера, каждый разput()После добавления данных (добавления данных) необходимо дождаться, пока другой поток возьмет данные, прежде чем снова добавлять данные.Пример его использования следующий:
import java.util.concurrent.SynchronousQueue;
public class SynchronousQueueTest {
public static void main(String[] args) {
SynchronousQueue queue = new SynchronousQueue();
// 入队
new Thread(() -> {
for (int i = 0; i < 3; i++) {
try {
System.out.println(new Date() + "，元素入队");
queue.put("Data " + i);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}).start();
// 出队
new Thread(() -> {
while (true) {
try {
Thread.sleep(1000);
System.out.println(new Date() + "，元素出队：" + queue.take());
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}).start();
}
}
Результат выполнения приведенного выше кода выглядит следующим образом:
Пн, 19 октября, 21:00:21 CST 2020, Элементы поставлены в очередь
Пн, 19 октября, 21:00:22 CST 2020, элементы удалены из очереди: данные 0
Mon Октябрь 19 21:00:22 CST 2020, Элементы вводятся
Пн, 19 октября, 21:00:23 CST 2020, элементы удалены из очереди: данные 1
Пн, 19 октября, 21:00:23 CST 2020, Элементы поставлены в очередь
Пн, 19 октября, 21:00:24 CST 2020, элементы удалены из очереди: данные 2
Из приведенных выше результатов видно, что когда элемент ставится в очередь, новый элемент может быть снова поставлен в очередь только после того, как другой поток удалит этот элемент из очереди.
Суммировать
В этой статье рассказывается о пяти видах очередей в Java: обычные очереди, двусторонние очереди, очереди с приоритетом, очереди с задержкой и другие очереди. Типичным представителем обычной очереди являетсяArrayBlockingQueueиLinkedBlockingQueue, представитель двусторонней очередиLinkedBlockingDeque, приоритетная очередь представленаPriorityQueue, представитель очереди задержкиDelayQueue, и, наконец, поговорим о других очередях без контейнеров внутриSynchronousQueue.
Благосостояние в конце статьи: Поиск общедоступной учетной записи «Китайское сообщество Java», чтобы отправить «интервью», чтобы получить последние материалы интервью.