Раздел 6. Коллекции в Java
Глава 4. Queue и Deque
Интерфейс Queue. Очередь как структура FIFO. Методы offer, poll, peek
Интерфейс Queue<E> — часть Java Collections Framework (JCF) из пакета java.util, предназначенная для хранения элементов, которые обрабатываются в определенном порядке. Queue моделирует очередь, где элементы добавляются в конец (tail) и извлекаются из начала (head). Основной принцип для большинства реализаций — FIFO, хотя есть исключения, например, приоритетные очереди.
Основные характеристики Queue:
FIFO (First-In-First-Out): Элементы обрабатываются в порядке добавления, как очередь в магазине.
Уникальность: Не гарантируется — дубликаты разрешены (зависит от реализации).
Порядок: Определен структурой (обычно порядок добавления или приоритет).
Big O: Зависит от реализации (O(1) для LinkedList, O(log n) для PriorityQueue).
Null элементы: Зависит от реализации (LinkedList позволяет, PriorityQueue — нет).
Где используется:
Очереди задач (например, обработка запросов в сервере).
Буферы (например, поток ввода-вывода).
Алгоритмы (например, обход графа в ширину — BFS).
Queue<E> расширяет Collection<E>, добавляя методы для работы с очередью.
Основные реализации:
LinkedList (как Queue), ArrayDeque и PriorityQueue.
FIFO: Принцип "первым вошел — первым вышел"
FIFO — это структура данных, где:
Элементы добавляются в конец очереди (enqueue).
Элементы извлекаются из начала (dequeue).
Аналогия: Люди в очереди в кассу — первый в очереди обслуживается первым.
Пример FIFO в жизни: Очередь сообщений в чате обрабатывается в порядке отправки.
Нюанс: PriorityQueue нарушает FIFO, сортируя по приоритету (рассмотрим в следующем уроке).
Основные методы Queue: offer, poll, peek
Queue предоставляет методы для работы с очередью, которые отличаются от add/remove Collection тем, как обрабатывают ограничения (например, заполненность).
offer(E e):
Описание: Добавляет элемент в конец очереди.
Возвращаемое значение: true, если добавлен; false, если очередь полная (для bounded очередей, например, с фиксированным размером).
Исключения: NullPointerException, если null в реализациях, не допускающих null (PriorityQueue).
Big O: O(1) для LinkedList/ArrayDeque, O(log n) для PriorityQueue (перестройка кучи).
poll():
Описание: Извлекает и удаляет элемент из начала очереди.
Возвращаемое значение: Элемент (E) или null, если очередь пуста.
Исключения: Нет (безопаснее, чем remove()).
Big O: O(1) для LinkedList/ArrayDeque, O(log n) для PriorityQueue.
peek():
Описание: Возвращает элемент из начала очереди без удаления.
Возвращаемое значение: Элемент (E) или null, если очередь пуста.
Исключения: Нет.
Big O: O(1) для всех реализаций.
Альтернативы (с исключениями):
add(E e): Как offer, но кидает IllegalStateException при переполнении.
remove(): Как poll, но кидает NoSuchElementException, если пусто.
element(): Как peek, но кидает NoSuchElementException, если пусто.
Нюанс: offer/poll/peek предпочтительнее для очередей, так как безопаснее.
#Java #для_новичков #beginner #Collections #Queue
Глава 4. Queue и Deque
Интерфейс Queue. Очередь как структура FIFO. Методы offer, poll, peek
Интерфейс Queue<E> — часть Java Collections Framework (JCF) из пакета java.util, предназначенная для хранения элементов, которые обрабатываются в определенном порядке. Queue моделирует очередь, где элементы добавляются в конец (tail) и извлекаются из начала (head). Основной принцип для большинства реализаций — FIFO, хотя есть исключения, например, приоритетные очереди.
Основные характеристики Queue:
FIFO (First-In-First-Out): Элементы обрабатываются в порядке добавления, как очередь в магазине.
Уникальность: Не гарантируется — дубликаты разрешены (зависит от реализации).
Порядок: Определен структурой (обычно порядок добавления или приоритет).
Big O: Зависит от реализации (O(1) для LinkedList, O(log n) для PriorityQueue).
Null элементы: Зависит от реализации (LinkedList позволяет, PriorityQueue — нет).
Где используется:
Очереди задач (например, обработка запросов в сервере).
Буферы (например, поток ввода-вывода).
Алгоритмы (например, обход графа в ширину — BFS).
Queue<E> расширяет Collection<E>, добавляя методы для работы с очередью.
Основные реализации:
LinkedList (как Queue), ArrayDeque и PriorityQueue.
FIFO: Принцип "первым вошел — первым вышел"
FIFO — это структура данных, где:
Элементы добавляются в конец очереди (enqueue).
Элементы извлекаются из начала (dequeue).
Аналогия: Люди в очереди в кассу — первый в очереди обслуживается первым.
Пример FIFO в жизни: Очередь сообщений в чате обрабатывается в порядке отправки.
Нюанс: PriorityQueue нарушает FIFO, сортируя по приоритету (рассмотрим в следующем уроке).
Основные методы Queue: offer, poll, peek
Queue предоставляет методы для работы с очередью, которые отличаются от add/remove Collection тем, как обрабатывают ограничения (например, заполненность).
offer(E e):
Описание: Добавляет элемент в конец очереди.
Возвращаемое значение: true, если добавлен; false, если очередь полная (для bounded очередей, например, с фиксированным размером).
Исключения: NullPointerException, если null в реализациях, не допускающих null (PriorityQueue).
Big O: O(1) для LinkedList/ArrayDeque, O(log n) для PriorityQueue (перестройка кучи).
poll():
Описание: Извлекает и удаляет элемент из начала очереди.
Возвращаемое значение: Элемент (E) или null, если очередь пуста.
Исключения: Нет (безопаснее, чем remove()).
Big O: O(1) для LinkedList/ArrayDeque, O(log n) для PriorityQueue.
peek():
Описание: Возвращает элемент из начала очереди без удаления.
Возвращаемое значение: Элемент (E) или null, если очередь пуста.
Исключения: Нет.
Big O: O(1) для всех реализаций.
Альтернативы (с исключениями):
add(E e): Как offer, но кидает IllegalStateException при переполнении.
remove(): Как poll, но кидает NoSuchElementException, если пусто.
element(): Как peek, но кидает NoSuchElementException, если пусто.
Нюанс: offer/poll/peek предпочтительнее для очередей, так как безопаснее.
#Java #для_новичков #beginner #Collections #Queue
👍2
Примеры использования методов
LinkedList как Queue (FIFO):
PriorityQueue (не FIFO, по приоритету):
Все нюансы методов
offer:
Для bounded очередей (с ограничением размера, например, ArrayBlockingQueue) возвращает false, если полная.
Null: LinkedList позволяет, PriorityQueue — NPE.
Custom объекты: Для PriorityQueue должны быть Comparable или нужен Comparator.
poll:
Безопасно для пустой очереди — просто null.
В PriorityQueue извлекает минимальный элемент (или по Comparator).
peek:
Не меняет очередь — только просмотр.
Null при пустой очереди, безопасно.
Ошибки:
NullPointerException: В PriorityQueue при null.
ClassCastException: В PriorityQueue, если элементы не Comparable.
ConcurrentModificationException: При модификации во время итерации (используйте poll вместо Iterator.remove()).
Thread-safety:
LinkedList, PriorityQueue не thread-safe. Используйте BlockingQueue (например, ArrayBlockingQueue) для многопоточности.
Collections.synchronizedCollection() — простой вариант синхронизации.
Производительность:
LinkedList: O(1) для всех методов (двусвязный список).
PriorityQueue: O(log n) для offer/poll (перестройка кучи), O(1) для peek.
ArrayDeque: O(1) для всех (рассмотрим в следующем уроке).
Полезные советы для новичков
Используйте offer/poll/peek: Безопаснее, чем add/remove/element.
LinkedList как Queue: Универсально для FIFO, но больше памяти, чем ArrayDeque.
Custom классы в PriorityQueue: Реализуйте Comparable или передайте Comparator.
Проверка пустоты: queue.isEmpty() перед poll/peek не нужна — null безопасен.
Итерация: For-each для чтения, но не модифицируйте очередь.
#Java #для_новичков #beginner #Collections #Queue
LinkedList как Queue (FIFO):
javaimport java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();
// Добавление
queue.offer("Задача 1");
queue.offer("Задача 2");
System.out.println(queue); // [Задача 1, Задача 2]
// Просмотр
System.out.println(queue.peek()); // Задача 1 (без удаления)
System.out.println(queue); // [Задача 1, Задача 2]
// Извлечение
String task = queue.poll(); // Задача 1
System.out.println(task); // Задача 1
System.out.println(queue); // [Задача 2]
// Пустая очередь
queue.poll(); // Задача 2
System.out.println(queue.poll()); // null (без исключения)
}
}
Вывод: Показывает FIFO — элементы извлекаются в порядке добавления, null при пустой очереди.
PriorityQueue (не FIFO, по приоритету):
javaimport java.util.PriorityQueue;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<Integer> queue = new PriorityQueue<>();
queue.offer(3);
queue.offer(1);
queue.offer(2);
System.out.println(queue); // [1, 3, 2] — минимальный в начале
System.out.println(queue.peek()); // 1
System.out.println(queue.poll()); // 1
System.out.println(queue); // [2, 3]
}
}
Нюанс: PriorityQueue сортирует по натуральному порядку (или Comparator), не FIFO.
Все нюансы методов
offer:
Для bounded очередей (с ограничением размера, например, ArrayBlockingQueue) возвращает false, если полная.
Null: LinkedList позволяет, PriorityQueue — NPE.
Custom объекты: Для PriorityQueue должны быть Comparable или нужен Comparator.
poll:
Безопасно для пустой очереди — просто null.
В PriorityQueue извлекает минимальный элемент (или по Comparator).
peek:
Не меняет очередь — только просмотр.
Null при пустой очереди, безопасно.
Ошибки:
NullPointerException: В PriorityQueue при null.
ClassCastException: В PriorityQueue, если элементы не Comparable.
ConcurrentModificationException: При модификации во время итерации (используйте poll вместо Iterator.remove()).
Thread-safety:
LinkedList, PriorityQueue не thread-safe. Используйте BlockingQueue (например, ArrayBlockingQueue) для многопоточности.
Collections.synchronizedCollection() — простой вариант синхронизации.
Производительность:
LinkedList: O(1) для всех методов (двусвязный список).
PriorityQueue: O(log n) для offer/poll (перестройка кучи), O(1) для peek.
ArrayDeque: O(1) для всех (рассмотрим в следующем уроке).
Полезные советы для новичков
Используйте offer/poll/peek: Безопаснее, чем add/remove/element.
LinkedList как Queue: Универсально для FIFO, но больше памяти, чем ArrayDeque.
Custom классы в PriorityQueue: Реализуйте Comparable или передайте Comparator.
Проверка пустоты: queue.isEmpty() перед poll/peek не нужна — null безопасен.
Итерация: For-each для чтения, но не модифицируйте очередь.
#Java #для_новичков #beginner #Collections #Queue
👍3
Что выведет код?
#Tasks
import java.util.*;
public class Task171025 {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.print(queue.peek() + " ");
System.out.print(queue.poll() + " ");
queue.offer(4);
System.out.print(queue.remove() + " ");
System.out.print(queue.element() + " ");
}
}
#Tasks
👍1
👍2
Вопрос с собеседований
Чем отличается JIT от AOT-компиляции?🤓
Ответ:
JIT компилирует байт-код в машинный во время выполнения.
AOT (Ahead-Of-Time) компилирует код заранее, до запуска (например, GraalVM native image).
JIT даёт гибкие оптимизации, AOT — более быстрое время старта и меньше зависимость от JVM.
#собеседование
Чем отличается JIT от AOT-компиляции?
Ответ:
JIT
AOT (Ahead-Of-Time) компилирует код заранее, до запуска (например, GraalVM native image).
JIT даёт гибкие оптимизации, AOT — более быстрое время старта и меньше зависимость от JVM.
#собеседование
Please open Telegram to view this post
VIEW IN TELEGRAM
👍4
История IT-технологий сегодня — 18 октября
ℹ️ Кто родился в этот день
Нир Шавит (англ. Nir Shavit, ивр. ניר שביט, род. 18 октября 1959) — израильский учёный в области информатики. Профессор факультета информатики в Тель-Авивском университете и профессор электротехники и информатики в Массачусетском технологическом институте.
Сантош Вемпала (родился 18 октября 1971 года) — выдающийся теоретик информатики, специалист по алгоритмам и случайным методам в оптимизации и геометрии; профессор Georgia Tech с большим числом влиятельных работ по алгоритмике.
🌐 Знаковые события
1963 — первый в истории полёт кошки (Фелисетт) в космическое пространство.
1967 — советский космический аппарат «Венера-4» успешно вошёл в атмосферу Венеры и начал её изучение.
#Biography #Birth_Date #Events #18Октября
Нир Шавит (англ. Nir Shavit, ивр. ניר שביט, род. 18 октября 1959) — израильский учёный в области информатики. Профессор факультета информатики в Тель-Авивском университете и профессор электротехники и информатики в Массачусетском технологическом институте.
Сантош Вемпала (родился 18 октября 1971 года) — выдающийся теоретик информатики, специалист по алгоритмам и случайным методам в оптимизации и геометрии; профессор Georgia Tech с большим числом влиятельных работ по алгоритмике.
1963 — первый в истории полёт кошки (Фелисетт) в космическое пространство.
1967 — советский космический аппарат «Венера-4» успешно вошёл в атмосферу Венеры и начал её изучение.
#Biography #Birth_Date #Events #18Октября
Please open Telegram to view this post
VIEW IN TELEGRAM
👍3
С 11.10 по 17.10
Предыдущий пост(с 04.10 по 10.10)
Воскресный мотивационный пост:
Чего ты тут забыл? 🧐
Запись встреч/видео:
gRPC и .proto
Обучающие статьи:
Реактивное программирование
Управление потоками в Reactor: Schedulers
Введение в Spring WebFlux
Java:
Коллекции в Java
Глава 3. Set — множества
Методы add, remove, contains
Практика: В «Библиотеке» создать коллекцию Set для хранения уникальных имён авторов. Добавлять автора при добавлении книги, проверять уникальность
Глава 4. Queue и Deque
Интерфейс Queue. Очередь как структура FIFO. Методы offer, poll, peek
Полезные статьи и видео:
Генерация HTTP клиентов для Spring Boot приложения по OpenAPI спецификации
Мастерство работы с Java Stream
Микросервисы: как это на самом деле работает
Как и всегда, задачи можно найти под тегом - #Tasks, вопросы с собеседований - #собеседование
Предыдущий пост(с 04.10 по 10.10)
Воскресный мотивационный пост:
Чего ты тут забыл? 🧐
Запись встреч/видео:
gRPC и .proto
Обучающие статьи:
Реактивное программирование
Управление потоками в Reactor: Schedulers
Введение в Spring WebFlux
Java:
Коллекции в Java
Глава 3. Set — множества
Методы add, remove, contains
Практика: В «Библиотеке» создать коллекцию Set для хранения уникальных имён авторов. Добавлять автора при добавлении книги, проверять уникальность
Глава 4. Queue и Deque
Интерфейс Queue. Очередь как структура FIFO. Методы offer, poll, peek
Полезные статьи и видео:
Генерация HTTP клиентов для Spring Boot приложения по OpenAPI спецификации
Мастерство работы с Java Stream
Микросервисы: как это на самом деле работает
Как и всегда, задачи можно найти под тегом - #Tasks, вопросы с собеседований - #собеседование
👍3
История IT-технологий сегодня — 19 октября
ℹ️ Кто родился в этот день
Джеймс Уэлдон Деммел-младший (родился 19 октября 1955 года) — американский математик и информатик, ведущий специалист по численным методам и линейной алгебре для высокопроизводительных вычислений; автор фундаментальных результатов и библиотек для линейной алгебры.
🌐 Знаковые события
2002 — восьмая решающая партия между россиянином Владимиром Крамником и компьютерной программой «Deep Fritz», проходившая в Манаме, Бахрейн, на 21 ходу завершилась вничью. Таким образом, ничьей завершился и сам матч.
2011 — Александр Йи и Сигэру Кондо рассчитали значение числа «Пи» с точностью в 10 трлн цифр после запятой.
#Biography #Birth_Date #Events #19Октября
Джеймс Уэлдон Деммел-младший (родился 19 октября 1955 года) — американский математик и информатик, ведущий специалист по численным методам и линейной алгебре для высокопроизводительных вычислений; автор фундаментальных результатов и библиотек для линейной алгебры.
2002 — восьмая решающая партия между россиянином Владимиром Крамником и компьютерной программой «Deep Fritz», проходившая в Манаме, Бахрейн, на 21 ходу завершилась вничью. Таким образом, ничьей завершился и сам матч.
2011 — Александр Йи и Сигэру Кондо рассчитали значение числа «Пи» с точностью в 10 трлн цифр после запятой.
#Biography #Birth_Date #Events #19Октября
Please open Telegram to view this post
VIEW IN TELEGRAM
👍4
Вам нравятся мотивационные статьи по воскресениям?
Anonymous Poll
58%
Да! Конечно) Жду каждое воскресение
21%
Нет, не интересно)
21%
Что за статьи?
🔥6