Примеры использования методов
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
Раздел 6. Коллекции в Java
Глава 4. Queue и Deque
Реализации: PriorityQueue, LinkedList как очередь. Применение: обработка задач, хранение заявок
Интерфейс Queue<E> имеет несколько реализаций в JCF, каждая оптимизирована под разные сценарии. Сегодня фокус на PriorityQueue и LinkedList (как Queue). Эти реализации демонстрируют разнообразие: от строгого FIFO до приоритетной обработки.
LinkedList<E> как Queue
LinkedList — это двусвязный список (doubly-linked list), который реализует Queue<E> (а также List<E> и Deque<E>). Как очередь, она идеальна для FIFO: добавление в конец, извлечение из начала.
Особенности:
FIFO: Строго соблюдается порядок добавления.
Уникальность: Нет, дубликаты разрешены.
Null: Разрешен (LinkedList позволяет null элементы).
Big O: O(1) для offer (добавление в конец), poll (извлечение из начала), peek (просмотр начала). Contains — O(n), так как перебор списка.
Внутренняя работа: Каждый элемент — узел (node) с ссылками на prev и next. Добавление — создание узла и обновление ссылок. Извлечение — удаление первого узла и сдвиг ссылок.
Нюансы:
Эффективна для частых вставок/удалений в концах (O(1)), но медленная для середины (O(n)).
Память: Выше, чем у ArrayDeque (из-за ссылок на prev/next).
Thread-safety: Нет — для многопоточности используйте BlockingQueue.
Дополнительно: Как Deque, поддерживает добавление/извлечение с обоих концов (об этом в следующем уроке).
Когда использовать: Для простых FIFO-очередей с небольшим размером, или когда нужна универсальность (Queue + List).
Пример кода для LinkedList как Queue:
PriorityQueue<E>
PriorityQueue — это приоритетная очередь на основе кучи (binary heap, min-heap по умолчанию). Она не следует FIFO, а извлекает элементы по приоритету (минимальный первый для натуральных типов).
Особенности:
FIFO: Нет — приоритетный порядок (по Comparable или Comparator).
Уникальность: Нет, дубликаты разрешены.
Null: Не разрешен (NullPointerException).
Big O: O(log n) для offer (вставка в кучу), poll (извлечение минимума с перестройкой), peek — O(1). Contains — O(n), так как перебор.
Внутренняя работа: Хранит элементы в массиве как бинарную кучу. При добавлении/извлечении перестраивает кучу (heapify) для поддержания свойства: родитель <= дети. Приоритет определяется compareTo() или Comparator.
Нюансы:
Порядок итерации: Не гарантирован (куча не sorted list).
Comparator: Передайте при создании: new PriorityQueue<>((a, b) -> b - a) для max-heap.
Размер: Resizable, initial capacity 11.
Thread-safety: Нет — используйте PriorityBlockingQueue для потоков.
Custom объекты: Должны реализовывать Comparable<E> или предоставить Comparator, иначе ClassCastException.
Когда использовать: Для задач с приоритетами (например, планировщик задач, Dijkstra алгоритм).
#Java #для_новичков #beginner #Collections #PriorityQueue #LinkedList
Глава 4. Queue и Deque
Реализации: PriorityQueue, LinkedList как очередь. Применение: обработка задач, хранение заявок
Интерфейс Queue<E> имеет несколько реализаций в JCF, каждая оптимизирована под разные сценарии. Сегодня фокус на PriorityQueue и LinkedList (как Queue). Эти реализации демонстрируют разнообразие: от строгого FIFO до приоритетной обработки.
LinkedList<E> как Queue
LinkedList — это двусвязный список (doubly-linked list), который реализует Queue<E> (а также List<E> и Deque<E>). Как очередь, она идеальна для FIFO: добавление в конец, извлечение из начала.
Особенности:
FIFO: Строго соблюдается порядок добавления.
Уникальность: Нет, дубликаты разрешены.
Null: Разрешен (LinkedList позволяет null элементы).
Big O: O(1) для offer (добавление в конец), poll (извлечение из начала), peek (просмотр начала). Contains — O(n), так как перебор списка.
Внутренняя работа: Каждый элемент — узел (node) с ссылками на prev и next. Добавление — создание узла и обновление ссылок. Извлечение — удаление первого узла и сдвиг ссылок.
Нюансы:
Эффективна для частых вставок/удалений в концах (O(1)), но медленная для середины (O(n)).
Память: Выше, чем у ArrayDeque (из-за ссылок на prev/next).
Thread-safety: Нет — для многопоточности используйте BlockingQueue.
Дополнительно: Как Deque, поддерживает добавление/извлечение с обоих концов (об этом в следующем уроке).
Когда использовать: Для простых FIFO-очередей с небольшим размером, или когда нужна универсальность (Queue + List).
Пример кода для LinkedList как Queue:
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");
queue.offer("Задача 3");
System.out.println(queue); // [Задача 1, Задача 2, Задача 3] — FIFO порядок
System.out.println(queue.peek()); // Задача 1 (просмотр)
System.out.println(queue.poll()); // Задача 1 (извлечение)
System.out.println(queue); // [Задача 2, Задача 3]
queue.offer(null); // Разрешен null
System.out.println(queue.poll()); // Задача 2
}
}
Вывод: Показывает FIFO — элементы извлекаются в порядке добавления, null разрешен.
PriorityQueue<E>
PriorityQueue — это приоритетная очередь на основе кучи (binary heap, min-heap по умолчанию). Она не следует FIFO, а извлекает элементы по приоритету (минимальный первый для натуральных типов).
Особенности:
FIFO: Нет — приоритетный порядок (по Comparable или Comparator).
Уникальность: Нет, дубликаты разрешены.
Null: Не разрешен (NullPointerException).
Big O: O(log n) для offer (вставка в кучу), poll (извлечение минимума с перестройкой), peek — O(1). Contains — O(n), так как перебор.
Внутренняя работа: Хранит элементы в массиве как бинарную кучу. При добавлении/извлечении перестраивает кучу (heapify) для поддержания свойства: родитель <= дети. Приоритет определяется compareTo() или Comparator.
Нюансы:
Порядок итерации: Не гарантирован (куча не sorted list).
Comparator: Передайте при создании: new PriorityQueue<>((a, b) -> b - a) для max-heap.
Размер: Resizable, initial capacity 11.
Thread-safety: Нет — используйте PriorityBlockingQueue для потоков.
Custom объекты: Должны реализовывать Comparable<E> или предоставить Comparator, иначе ClassCastException.
Когда использовать: Для задач с приоритетами (например, планировщик задач, Dijkstra алгоритм).
#Java #для_новичков #beginner #Collections #PriorityQueue #LinkedList
👍2
Пример кода для PriorityQueue:
Применение очередей: Обработка задач, хранение заявок
Очереди идеальны для сценариев последовательной обработки.
Обработка задач (Task Processing):
Пример: Планировщик задач, где задачи добавляются в очередь и обрабатываются по порядку (FIFO с LinkedList) или по приоритету (PriorityQueue).
Нюанс: В многопоточных системах (например, Thread pool) используйте BlockingQueue для безопасного poll.
Пример кода (простой обработчик):
Хранение заявок (Request Storage):
Пример: Сервер хранит входящие заявки в очередь для последовательной обработки (например, HTTP requests).
С PriorityQueue: Заявки по срочности (high-priority first).
Нюанс: Для реальных систем используйте BlockingQueue (offer/poll с блокировкой при пустой/полной).
Пример кода (приоритетные заявки):
Полезные советы для новичков
LinkedList для простоты: Универсальна для FIFO, легко добавить Deque-функции.
PriorityQueue для приоритетов: Передавайте Comparator для custom порядка (например, max-heap).
Custom классы: Реализуйте Comparable для PriorityQueue, или используйте Comparator.
Пустая очередь: Проверяйте isEmpty() перед poll, или используйте null от poll.
Итерация: For-each для просмотра, но не модифицируйте.
#Java #для_новичков #beginner #Collections #PriorityQueue #LinkedList
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] — min в начале, но итерация не sorted
System.out.println(queue.peek()); // 1 (минимальный)
System.out.println(queue.poll()); // 1
System.out.println(queue); // [2, 3]
// Max-heap с Comparator
Queue<Integer> maxQueue = new PriorityQueue<>((a, b) -> b - a);
maxQueue.offer(3);
maxQueue.offer(1);
maxQueue.offer(2);
System.out.println(maxQueue.poll()); // 3 (максимальный)
// queue.offer(null); // NPE
}
}
Вывод: Элементы извлекаются по приоритету, не по порядку добавления.
Применение очередей: Обработка задач, хранение заявок
Очереди идеальны для сценариев последовательной обработки.
Обработка задач (Task Processing):
Пример: Планировщик задач, где задачи добавляются в очередь и обрабатываются по порядку (FIFO с LinkedList) или по приоритету (PriorityQueue).
Нюанс: В многопоточных системах (например, Thread pool) используйте BlockingQueue для безопасного poll.
Пример кода (простой обработчик):
javaimport java.util.LinkedList;
import java.util.Queue;
public class TaskProcessor {
private Queue<String> tasks = new LinkedList<>();
public void addTask(String task) {
tasks.offer(task);
}
public void processTasks() {
while (!tasks.isEmpty()) {
String task = tasks.poll();
System.out.println("Обработка: " + task);
}
}
}
public class Main {
public static void main(String[] args) {
TaskProcessor processor = new TaskProcessor();
processor.addTask("Задача 1");
processor.addTask("Задача 2");
processor.processTasks(); // Обработка: Задача 1\nОбработка: Задача 2
}
}
Вывод: Задачи обрабатываются FIFO.
Хранение заявок (Request Storage):
Пример: Сервер хранит входящие заявки в очередь для последовательной обработки (например, HTTP requests).
С PriorityQueue: Заявки по срочности (high-priority first).
Нюанс: Для реальных систем используйте BlockingQueue (offer/poll с блокировкой при пустой/полной).
Пример кода (приоритетные заявки):
javaimport java.util.PriorityQueue;
import java.util.Queue;
class Request implements Comparable<Request> {
private String name;
private int priority; // 1 - высокий, 10 - низкий
public Request(String name, int priority) {
this.name = name;
this.priority = priority;
}
@Override
public int compareTo(Request other) {
return Integer.compare(this.priority, other.priority); // Min-heap по приоритету
}
public String getName() {
return name;
}
}
public class Main {
public static void main(String[] args) {
Queue<Request> requests = new PriorityQueue<>();
requests.offer(new Request("Заявка A", 5));
requests.offer(new Request("Заявка B", 1)); // Высокий приоритет
requests.offer(new Request("Заявка C", 3));
while (!requests.isEmpty()) {
System.out.println("Обработка: " + requests.poll().getName()); // Заявка B, Заявка C, Заявка A
}
}
}
Вывод: Заявки обрабатываются по приоритету.
Полезные советы для новичков
LinkedList для простоты: Универсальна для FIFO, легко добавить Deque-функции.
PriorityQueue для приоритетов: Передавайте Comparator для custom порядка (например, max-heap).
Custom классы: Реализуйте Comparable для PriorityQueue, или используйте Comparator.
Пустая очередь: Проверяйте isEmpty() перед poll, или используйте null от poll.
Итерация: For-each для просмотра, но не модифицируйте.
#Java #для_новичков #beginner #Collections #PriorityQueue #LinkedList
👍1
Раздел 6. Коллекции в Java
Глава 4. Queue и Deque
Интерфейс Deque. Двусторонняя очередь (FIFO и LIFO). Реализации: ArrayDeque, LinkedList
Интерфейс Deque<E> — это расширение Queue из пакета java.util, который представляет двустороннюю очередь (double-ended queue). Deque позволяет добавлять, удалять и просматривать элементы как с начала (head), так и с конца (tail) очереди. Это делает Deque универсальной структурой, способной моделировать как обычную очередь (FIFO), так и стек (LIFO), а также комбинированные сценарии.
Ключевые особенности Deque
Двусторонний доступ: Операции с first (начало) и last (конец).
FIFO и LIFO:
FIFO: Добавляйте в конец (addLast), извлекайте из начала (removeFirst) — как стандартная очередь.
LIFO: Добавляйте в начало (addFirst), извлекайте из начала (removeFirst) — как стек.
Уникальность элементов: Не гарантируется — дубликаты разрешены (зависит от реализации).
Null элементы: Зависит от реализации (ArrayDeque позволяет, но не рекомендуется; LinkedList позволяет).
Big O: Зависит от реализации, но обычно O(1) для операций на концах.
Итерация: Поддерживает Iterator для перебора от начала к концу, и descendingIterator() для обратного порядка.
Deque расширяет Queue, добавляя методы для работы с концом. Основные реализации: ArrayDeque (на массиве) и LinkedList (на связном списке). Deque можно использовать как Queue или Stack (вместо устаревшего Stack класса).
Когда использовать Deque:
Для стеков (LIFO, например, undo/redo).
Для очередей с доступом к концу (например, sliding window в алгоритмах).
Для двусторонних операций (например, палиндромы, где проверка с обоих концов).
FIFO и LIFO в Deque: Двусторонняя очередь
Deque поддерживает два основных режима:
FIFO (First-In-First-Out): "Первым вошел — первым вышел".
Добавление: addLast(E e) или offerLast(E e).
Извлечение: removeFirst() или pollFirst().
Просмотр: getFirst() или peekFirst().
Аналогия: Очередь в банке — первый пришел, первый ушел.
LIFO (Last-In-First-Out): "Последним вошел — первым вышел".
Добавление: addFirst(E e) или offerFirst(E e).
Извлечение: removeFirst() или pollFirst().
Просмотр: getFirst() или peekFirst().
Аналогия: Стопка тарелок — последняя сверху первой берется.
Методы Deque (основные, аналогично Queue, но с first/last)
Добавление:
addFirst(E e)/addLast(E e): Добавляет или кидает исключение, если переполнено.
offerFirst(E e)/offerLast(E e): Добавляет, возвращает boolean (false, если переполнено).
Извлечение:
removeFirst()/removeLast(): Извлекает или кидает NoSuchElementException, если пусто.
pollFirst()/pollLast(): Извлекает или возвращает null, если пусто.
Просмотр:
getFirst()/getLast(): Возвращает или кидает NoSuchElementException, если пусто.
peekFirst()/peekLast(): Возвращает или null, если пусто.
Другие: size(), isEmpty(), clear(), iterator(), descendingIterator().
Нюанс: Методы Queue (offer, poll, peek) в Deque эквивалентны offerLast, pollFirst, peekFirst (для FIFO).
#Java #для_новичков #beginner #Collections #Deque #ArrayDeque #LinkedList
Глава 4. Queue и Deque
Интерфейс Deque. Двусторонняя очередь (FIFO и LIFO). Реализации: ArrayDeque, LinkedList
Интерфейс Deque<E> — это расширение Queue из пакета java.util, который представляет двустороннюю очередь (double-ended queue). Deque позволяет добавлять, удалять и просматривать элементы как с начала (head), так и с конца (tail) очереди. Это делает Deque универсальной структурой, способной моделировать как обычную очередь (FIFO), так и стек (LIFO), а также комбинированные сценарии.
Ключевые особенности Deque
Двусторонний доступ: Операции с first (начало) и last (конец).
FIFO и LIFO:
FIFO: Добавляйте в конец (addLast), извлекайте из начала (removeFirst) — как стандартная очередь.
LIFO: Добавляйте в начало (addFirst), извлекайте из начала (removeFirst) — как стек.
Уникальность элементов: Не гарантируется — дубликаты разрешены (зависит от реализации).
Null элементы: Зависит от реализации (ArrayDeque позволяет, но не рекомендуется; LinkedList позволяет).
Big O: Зависит от реализации, но обычно O(1) для операций на концах.
Итерация: Поддерживает Iterator для перебора от начала к концу, и descendingIterator() для обратного порядка.
Deque расширяет Queue, добавляя методы для работы с концом. Основные реализации: ArrayDeque (на массиве) и LinkedList (на связном списке). Deque можно использовать как Queue или Stack (вместо устаревшего Stack класса).
Когда использовать Deque:
Для стеков (LIFO, например, undo/redo).
Для очередей с доступом к концу (например, sliding window в алгоритмах).
Для двусторонних операций (например, палиндромы, где проверка с обоих концов).
FIFO и LIFO в Deque: Двусторонняя очередь
Deque поддерживает два основных режима:
FIFO (First-In-First-Out): "Первым вошел — первым вышел".
Добавление: addLast(E e) или offerLast(E e).
Извлечение: removeFirst() или pollFirst().
Просмотр: getFirst() или peekFirst().
Аналогия: Очередь в банке — первый пришел, первый ушел.
LIFO (Last-In-First-Out): "Последним вошел — первым вышел".
Добавление: addFirst(E e) или offerFirst(E e).
Извлечение: removeFirst() или pollFirst().
Просмотр: getFirst() или peekFirst().
Аналогия: Стопка тарелок — последняя сверху первой берется.
Методы Deque (основные, аналогично Queue, но с first/last)
Добавление:
addFirst(E e)/addLast(E e): Добавляет или кидает исключение, если переполнено.
offerFirst(E e)/offerLast(E e): Добавляет, возвращает boolean (false, если переполнено).
Извлечение:
removeFirst()/removeLast(): Извлекает или кидает NoSuchElementException, если пусто.
pollFirst()/pollLast(): Извлекает или возвращает null, если пусто.
Просмотр:
getFirst()/getLast(): Возвращает или кидает NoSuchElementException, если пусто.
peekFirst()/peekLast(): Возвращает или null, если пусто.
Другие: size(), isEmpty(), clear(), iterator(), descendingIterator().
Нюанс: Методы Queue (offer, poll, peek) в Deque эквивалентны offerLast, pollFirst, peekFirst (для FIFO).
#Java #для_новичков #beginner #Collections #Deque #ArrayDeque #LinkedList
👍3
Реализации Deque: ArrayDeque и LinkedList
ArrayDeque
Описание: ArrayDeque — эффективная реализация Deque на основе кругового массива (circular array), который resizable. Она оптимизирована для операций на концах и рекомендуется как стандартная Deque в Java.
Особенности:
FIFO/LIFO: Поддерживает оба.
Уникальность: Нет.
Null: Разрешен.
Big O: O(1) amortized для addFirst/addLast, removeFirst/removeLast, peek (постоянное время). Contains — O(n).
Внутренняя работа: Массив с head и tail индексами. При добавлении/удалении индексы циклически сдвигаются. При заполнении массив удваивается (resizing O(n) rarely).
Нюансы:
Память: Эффективнее LinkedList (нет ссылок на узлы).
Initial capacity: Конструктор с int для начального размера (default 16).
Thread-safety: Нет — используйте для single-thread.
Когда использовать: Для большинства Deque-задач (быстрее LinkedList для концов).
Ограничение: Не реализует List, нет доступа по индексу.
Пример кода для ArrayDeque:
LinkedList
Описание: LinkedList — двусвязный список, который реализует Deque (и Queue, List). Как Deque, она позволяет операции на обоих концах.
Особенности:
FIFO/LIFO: Поддерживает оба.
Уникальность: Нет.
Null: Разрешен.
Big O: O(1) для addFirst/addLast, removeFirst/removeLast, peek (ссылки на first/last узлы). Contains — O(n).
Внутренняя работа: Узлы с prev/next ссылками. Добавление — создание узла и обновление ссылок first/last. Удаление — сдвиг ссылок.
Нюансы:
Память: Выше, чем ArrayDeque (каждый узел — объект с ссылками).
Универсальность: Реализует List, так что доступ по индексу (но O(n)).
Thread-safety: Нет.
Когда использовать: Для Deque с дополнительными List-функциями или частых вставок в середину (но для концов ArrayDeque быстрее).
Ограничение: Медленнее ArrayDeque для больших размеров из-за overhead узлов.
Пример кода для LinkedList как Deque (аналогичен ArrayDeque):
Полезные советы для новичков
ArrayDeque по умолчанию: Для большинства Deque-задач — эффективнее.
LinkedList для универсальности: Если нужно List API (get(index)), используйте её.
FIFO vs LIFO: Выбирайте методы (First/Last) по нуждам.
Null: Избегайте, чтобы не путаться.
Итераторы: descendingIterator() для обратного перебора — полезно для LIFO.
#Java #для_новичков #beginner #Collections #Deque #ArrayDeque #LinkedList
ArrayDeque
Описание: ArrayDeque — эффективная реализация Deque на основе кругового массива (circular array), который resizable. Она оптимизирована для операций на концах и рекомендуется как стандартная Deque в Java.
Особенности:
FIFO/LIFO: Поддерживает оба.
Уникальность: Нет.
Null: Разрешен.
Big O: O(1) amortized для addFirst/addLast, removeFirst/removeLast, peek (постоянное время). Contains — O(n).
Внутренняя работа: Массив с head и tail индексами. При добавлении/удалении индексы циклически сдвигаются. При заполнении массив удваивается (resizing O(n) rarely).
Нюансы:
Память: Эффективнее LinkedList (нет ссылок на узлы).
Initial capacity: Конструктор с int для начального размера (default 16).
Thread-safety: Нет — используйте для single-thread.
Когда использовать: Для большинства Deque-задач (быстрее LinkedList для концов).
Ограничение: Не реализует List, нет доступа по индексу.
Пример кода для ArrayDeque:
import java.util.ArrayDeque;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
Deque<String> deque = new ArrayDeque<>();
// FIFO: Очередь
deque.offerLast("Элемент 1"); // Добавление в конец
deque.offerLast("Элемент 2");
System.out.println(deque.pollFirst()); // Элемент 1 (извлечение из начала)
System.out.println(deque.peekFirst()); // Элемент 2 (просмотр)
// LIFO: Стек
deque.offerFirst("Элемент 3"); // Добавление в начало
deque.offerFirst("Элемент 4");
System.out.println(deque.pollFirst()); // Элемент 4 (LIFO)
// Обратный итератор
for (String elem : deque.descendingIterator()) {
System.out.println(elem); // С конца к началу
}
}
}
Вывод: Показывает FIFO и LIFO, операции O(1).
LinkedList
Описание: LinkedList — двусвязный список, который реализует Deque (и Queue, List). Как Deque, она позволяет операции на обоих концах.
Особенности:
FIFO/LIFO: Поддерживает оба.
Уникальность: Нет.
Null: Разрешен.
Big O: O(1) для addFirst/addLast, removeFirst/removeLast, peek (ссылки на first/last узлы). Contains — O(n).
Внутренняя работа: Узлы с prev/next ссылками. Добавление — создание узла и обновление ссылок first/last. Удаление — сдвиг ссылок.
Нюансы:
Память: Выше, чем ArrayDeque (каждый узел — объект с ссылками).
Универсальность: Реализует List, так что доступ по индексу (но O(n)).
Thread-safety: Нет.
Когда использовать: Для Deque с дополнительными List-функциями или частых вставок в середину (но для концов ArrayDeque быстрее).
Ограничение: Медленнее ArrayDeque для больших размеров из-за overhead узлов.
Пример кода для LinkedList как Deque (аналогичен ArrayDeque):
import java.util.LinkedList;
import java.util.Deque;
public class Main {
public static void main(String[] args) {
Deque<String> deque = new LinkedList<>();
deque.addLast("Элемент 1");
deque.addLast("Элемент 2");
System.out.println(deque.removeFirst()); // Элемент 1
deque.addFirst("Элемент 3");
System.out.println(deque.removeFirst()); // Элемент 3 (LIFO)
}
}
Вывод: То же, что и ArrayDeque, но с List-возможностями.
Полезные советы для новичков
ArrayDeque по умолчанию: Для большинства Deque-задач — эффективнее.
LinkedList для универсальности: Если нужно List API (get(index)), используйте её.
FIFO vs LIFO: Выбирайте методы (First/Last) по нуждам.
Null: Избегайте, чтобы не путаться.
Итераторы: descendingIterator() для обратного перебора — полезно для LIFO.
#Java #для_новичков #beginner #Collections #Deque #ArrayDeque #LinkedList
👍2
Раздел 6. Коллекции в Java
Глава 4. Queue и Deque
Практика:
В «Библиотеке» добавить очередь читателей (Queue<String>) для книги. Когда книга возвращается — выдать её первому из очереди
Откройте проект «Библиотека»
Запустите IntelliJ IDEA и откройте существующий проект LibraryProject. Убедитесь, что классы Book и Library существуют: Book с полями title, author, year (и геттерами), Library с массивом книг, счетчиком bookCount, методом addBook и Set для авторов.
Импортируйте необходимые пакеты:
В файлах, где будете использовать Queue, убедитесь, что импортированы java.util.Queue и java.util.LinkedList (или ArrayDeque — выберите реализацию для FIFO). IDE подскажет, когда вы начнете писать код — используйте Ctrl+Enter для автодобавления импорта.
Выберите реализацию Queue:
Для этого задания используйте LinkedList<String> как Queue — она проста для FIFO и позволяет операции на концах. Альтернатива — ArrayDeque для большей эффективности, если хотите поэкспериментировать.
Обновление класса Book для очереди читателей
Поскольку очередь читателей относится к конкретной книге (кто ждет эту книгу), добавим её в класс Book.
Добавьте поле для Queue<String>:
Откройте файл Book.java.
Объявите приватное поле readerQueue типа Queue<String>, инициализированное как new LinkedList<> (или new ArrayDeque<>).
Это множество будет хранить имена читателей в порядке очереди (FIFO: первый добавленный — первый получит книгу).
Добавьте методы для работы с очередью
Создайте публичный метод addToQueue(String readerName), который:
Добавляет имя читателя в конец очереди с помощью offer (readerQueue.offer(readerName)).
Можно вывести сообщение, например, "Читатель [readerName] добавлен в очередь за книгой [title]".
Создайте публичный метод returnBook(), который моделирует возврат книги:
Проверяет, пуста ли очередь (readerQueue.isEmpty()).
Если пуста — выводит сообщение "Книга свободна, очередь пуста".
Если не пуста — извлекает первого читателя с помощью poll (String nextReader = readerQueue.poll();).
Выводит сообщение "Книга выдана следующему читателю: [nextReader]".
(Опционально: Если книга была занята, здесь можно обновить статус, но для простоты пока опустим).
Обновите конструктор Book:
В конструкторе Book убедитесь, что readerQueue инициализируется (если не сделали при объявлении поля).
Интеграция с классом Library
Теперь обновим Library, чтобы при добавлении книги учитывать очередь, но поскольку очередь в Book, Library будет работать с объектами Book.
Обновите метод addBook(Book book):
В методе addBook оставьте добавление в массив книг, но добавьте проверку: Если очередь читателей в книге не пуста (book.getReaderQueue().isEmpty() == false), выведите сообщение "Книга добавлена, но имеет очередь читателей".
(Это опционально, но поможет связать с практикой).
Добавьте метод для возврата книги
Создайте публичный метод returnBookByTitle(String title), который:
Ищет книгу в массиве по title (перебор с equals).
Если найдена — вызывает returnBook() на объекте Book.
Если не найдена — выводит сообщение "Книга не найдена".
Обновление класса Main для тестирования
Теперь протестируем новую функциональность в Main.
Создайте объекты и добавьте книги:
В методе main создайте объект Library.
Создайте объект Book (например, с title "Война и мир", author "Толстой", year 1869).
Вызовите addBook на Library.
Добавьте читателей в очередь:
Через объект Book вызовите addToQueue несколько раз с разными именами читателей (например, "Иван", "Мария", "Петр").
Вызовите returnBook() на Book — первый читатель ("Иван") должен получить книгу, остальные остаются в очереди.
Протестируйте возврат:
Вызовите returnBook() еще раз — следующий читатель ("Мария") получит.
Продолжите, пока очередь не опустеет — последний вызов вернет null или сообщение о пустоте.
#Java #для_новичков #beginner #Collections #Deque #ArrayDeque #LinkedList
Глава 4. Queue и Deque
Практика:
В «Библиотеке» добавить очередь читателей (Queue<String>) для книги. Когда книга возвращается — выдать её первому из очереди
Откройте проект «Библиотека»
Запустите IntelliJ IDEA и откройте существующий проект LibraryProject. Убедитесь, что классы Book и Library существуют: Book с полями title, author, year (и геттерами), Library с массивом книг, счетчиком bookCount, методом addBook и Set для авторов.
Импортируйте необходимые пакеты:
В файлах, где будете использовать Queue, убедитесь, что импортированы java.util.Queue и java.util.LinkedList (или ArrayDeque — выберите реализацию для FIFO). IDE подскажет, когда вы начнете писать код — используйте Ctrl+Enter для автодобавления импорта.
Выберите реализацию Queue:
Для этого задания используйте LinkedList<String> как Queue — она проста для FIFO и позволяет операции на концах. Альтернатива — ArrayDeque для большей эффективности, если хотите поэкспериментировать.
Обновление класса Book для очереди читателей
Поскольку очередь читателей относится к конкретной книге (кто ждет эту книгу), добавим её в класс Book.
Добавьте поле для Queue<String>:
Откройте файл Book.java.
Объявите приватное поле readerQueue типа Queue<String>, инициализированное как new LinkedList<> (или new ArrayDeque<>).
Это множество будет хранить имена читателей в порядке очереди (FIFO: первый добавленный — первый получит книгу).
Добавьте методы для работы с очередью
Создайте публичный метод addToQueue(String readerName), который:
Добавляет имя читателя в конец очереди с помощью offer (readerQueue.offer(readerName)).
Можно вывести сообщение, например, "Читатель [readerName] добавлен в очередь за книгой [title]".
Создайте публичный метод returnBook(), который моделирует возврат книги:
Проверяет, пуста ли очередь (readerQueue.isEmpty()).
Если пуста — выводит сообщение "Книга свободна, очередь пуста".
Если не пуста — извлекает первого читателя с помощью poll (String nextReader = readerQueue.poll();).
Выводит сообщение "Книга выдана следующему читателю: [nextReader]".
(Опционально: Если книга была занята, здесь можно обновить статус, но для простоты пока опустим).
Обновите конструктор Book:
В конструкторе Book убедитесь, что readerQueue инициализируется (если не сделали при объявлении поля).
Интеграция с классом Library
Теперь обновим Library, чтобы при добавлении книги учитывать очередь, но поскольку очередь в Book, Library будет работать с объектами Book.
Обновите метод addBook(Book book):
В методе addBook оставьте добавление в массив книг, но добавьте проверку: Если очередь читателей в книге не пуста (book.getReaderQueue().isEmpty() == false), выведите сообщение "Книга добавлена, но имеет очередь читателей".
(Это опционально, но поможет связать с практикой).
Добавьте метод для возврата книги
Создайте публичный метод returnBookByTitle(String title), который:
Ищет книгу в массиве по title (перебор с equals).
Если найдена — вызывает returnBook() на объекте Book.
Если не найдена — выводит сообщение "Книга не найдена".
Обновление класса Main для тестирования
Теперь протестируем новую функциональность в Main.
Создайте объекты и добавьте книги:
В методе main создайте объект Library.
Создайте объект Book (например, с title "Война и мир", author "Толстой", year 1869).
Вызовите addBook на Library.
Добавьте читателей в очередь:
Через объект Book вызовите addToQueue несколько раз с разными именами читателей (например, "Иван", "Мария", "Петр").
Вызовите returnBook() на Book — первый читатель ("Иван") должен получить книгу, остальные остаются в очереди.
Протестируйте возврат:
Вызовите returnBook() еще раз — следующий читатель ("Мария") получит.
Продолжите, пока очередь не опустеет — последний вызов вернет null или сообщение о пустоте.
#Java #для_новичков #beginner #Collections #Deque #ArrayDeque #LinkedList
👍1
Тестирование и отладка
После реализации протестируйте, чтобы убедиться в правильной работе очереди.
Запустите проект:
Правой кнопкой на Main.java → Run 'Main.main()'.
В консоли увидите сообщения о добавлении читателей и выдаче книги по порядку (FIFO: первый добавленный — первый получает).
Проверьте FIFO:
Убедитесь, что читатели выдаются в порядке добавления (offer в конец, poll из начала).
Попробуйте добавить null как читателя — проверьте поведение (LinkedList позволит).
Отладка:
Установите breakpoint в методе returnBook перед poll и после — шагайте (F8) и смотрите размер очереди (readerQueue.size()).
Если ошибки: NullPointerException (если очередь не инициализирована или книга не найдена) — добавьте проверки if (readerQueue != null && !readerQueue.isEmpty()).
ArrayIndexOutOfBoundsException в массиве книг — расширьте массив или используйте динамический список (позже заменим на List).
Эксперименты:
Измените реализацию Queue на ArrayDeque — проверьте, работает ли аналогично (да, но эффективнее по памяти).
Добавьте метод isQueueEmpty() в Book для проверки пустоты — используйте в Library для статистики.
Полезные советы для новичков
Инициализация Queue: Всегда инициализируйте в конструкторе Book (readerQueue = new LinkedList<>();), чтобы избежать NullPointerException.
Проверка возвращаемого: Poll возвращает null при пустой — используйте if (nextReader != null) для сообщений.
Расширение: Подумайте о статусе книги (boolean isAvailable) — при возврате устанавливайте true, при выдаче — false.
Массив книг: Пока используем массив, но заметьте ограничения — в следующих уроках заменим на List<Book>.
Thread-safety: Если проект вырастет, подумайте о ConcurrentLinkedQueue для многопоточности.
#Java #для_новичков #beginner #Collections #Deque #ArrayDeque #LinkedList
После реализации протестируйте, чтобы убедиться в правильной работе очереди.
Запустите проект:
Правой кнопкой на Main.java → Run 'Main.main()'.
В консоли увидите сообщения о добавлении читателей и выдаче книги по порядку (FIFO: первый добавленный — первый получает).
Проверьте FIFO:
Убедитесь, что читатели выдаются в порядке добавления (offer в конец, poll из начала).
Попробуйте добавить null как читателя — проверьте поведение (LinkedList позволит).
Отладка:
Установите breakpoint в методе returnBook перед poll и после — шагайте (F8) и смотрите размер очереди (readerQueue.size()).
Если ошибки: NullPointerException (если очередь не инициализирована или книга не найдена) — добавьте проверки if (readerQueue != null && !readerQueue.isEmpty()).
ArrayIndexOutOfBoundsException в массиве книг — расширьте массив или используйте динамический список (позже заменим на List).
Эксперименты:
Измените реализацию Queue на ArrayDeque — проверьте, работает ли аналогично (да, но эффективнее по памяти).
Добавьте метод isQueueEmpty() в Book для проверки пустоты — используйте в Library для статистики.
Полезные советы для новичков
Инициализация Queue: Всегда инициализируйте в конструкторе Book (readerQueue = new LinkedList<>();), чтобы избежать NullPointerException.
Проверка возвращаемого: Poll возвращает null при пустой — используйте if (nextReader != null) для сообщений.
Расширение: Подумайте о статусе книги (boolean isAvailable) — при возврате устанавливайте true, при выдаче — false.
Массив книг: Пока используем массив, но заметьте ограничения — в следующих уроках заменим на List<Book>.
Thread-safety: Если проект вырастет, подумайте о ConcurrentLinkedQueue для многопоточности.
#Java #для_новичков #beginner #Collections #Deque #ArrayDeque #LinkedList
👍1