Введение в Queue
Queue — это интерфейс в Java, представляющий коллекцию, предназначенную для хранения элементов в порядке, поддерживающем принципы FIFO (First-In-First-Out). Элементы добавляются в конец очереди и извлекаются из начала. Queue является частью коллекций Java и находится в пакете java.util.
Реализации Queue
Существует несколько реализаций интерфейса Queue в Java:
LinkedList: Класс LinkedList реализует интерфейс Queue и предоставляет эффективные операции вставки и удаления с обоих концов списка.
PriorityQueue: Класс PriorityQueue реализует интерфейс Queue и предоставляет приоритетную очередь, в которой элементы упорядочены на основе их естественного порядка или на основе предоставленного компаратора.
ArrayDeque: Класс ArrayDeque реализует интерфейс Deque (двусторонняя очередь) и может использоваться как Queue.
Основные операции:
Добавление элементов:
add(E e): Добавляет элемент в конец очереди. Выбрасывает исключение IllegalStateException, если очередь ограничена и заполнена.
offer(E e): Добавляет элемент в конец очереди. Возвращает false, если очередь ограничена и заполнена.
Удаление элементов:
remove(): Удаляет и возвращает элемент из начала очереди. Выбрасывает исключение NoSuchElementException, если очередь пуста.
poll(): Удаляет и возвращает элемент из начала очереди. Возвращает null, если очередь пуста.
Просмотр элементов:
element(): Возвращает, но не удаляет, элемент из начала очереди. Выбрасывает исключение NoSuchElementException, если очередь пуста.
peek(): Возвращает, но не удаляет, элемент из начала очереди. Возвращает null, если очередь пуста.
Пример использования Queue
#Java #Training #Collections #Queue
Queue — это интерфейс в Java, представляющий коллекцию, предназначенную для хранения элементов в порядке, поддерживающем принципы FIFO (First-In-First-Out). Элементы добавляются в конец очереди и извлекаются из начала. Queue является частью коллекций Java и находится в пакете java.util.
Реализации Queue
Существует несколько реализаций интерфейса Queue в Java:
LinkedList: Класс LinkedList реализует интерфейс Queue и предоставляет эффективные операции вставки и удаления с обоих концов списка.
Queue<String> queue = new LinkedList<>();
PriorityQueue: Класс PriorityQueue реализует интерфейс Queue и предоставляет приоритетную очередь, в которой элементы упорядочены на основе их естественного порядка или на основе предоставленного компаратора.
Queue<String> priorityQueue = new PriorityQueue<>();
ArrayDeque: Класс ArrayDeque реализует интерфейс Deque (двусторонняя очередь) и может использоваться как Queue.
Queue<String> arrayDeque = new ArrayDeque<>();
Основные операции:
Добавление элементов:
add(E e): Добавляет элемент в конец очереди. Выбрасывает исключение IllegalStateException, если очередь ограничена и заполнена.
queue.add("Element");offer(E e): Добавляет элемент в конец очереди. Возвращает false, если очередь ограничена и заполнена.
queue.offer("Element");Удаление элементов:
remove(): Удаляет и возвращает элемент из начала очереди. Выбрасывает исключение NoSuchElementException, если очередь пуста.
String element = queue.remove();
poll(): Удаляет и возвращает элемент из начала очереди. Возвращает null, если очередь пуста.
String element = queue.poll();
Просмотр элементов:
element(): Возвращает, но не удаляет, элемент из начала очереди. Выбрасывает исключение NoSuchElementException, если очередь пуста.
String element = queue.element();
peek(): Возвращает, но не удаляет, элемент из начала очереди. Возвращает null, если очередь пуста.
String element = queue.peek();
Пример использования Queue
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();
// Добавление элементов
queue.add("Element 1");
queue.offer("Element 2");
// Просмотр элемента
System.out.println("Peek: " + queue.peek());
// Удаление элементов
System.out.println("Removed: " + queue.remove());
System.out.println("Polled: " + queue.poll());
// Попытка просмотра/удаления из пустой очереди
System.out.println("Peek from empty queue: " + queue.peek());
System.out.println("Poll from empty queue: " + queue.poll());
}
}
#Java #Training #Collections #Queue
Раздел 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