Java for Beginner

Раздел 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:

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

👍1

49 views08:58

Java for Beginner

Пример кода для PriorityQueue:

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

55 views08:58

About

Blog

Apps

Platform