ArrayDeque, внутреннее устройство, особенности и преимущества

ArrayDeque — это реализация двусторонней очереди (deque) на основе массивов, предоставляемая в пакете java.util. Она представляет собой гибкую структуру данных, которая поддерживает вставку и удаление элементов с обеих сторон с амортизированным постоянным временем.

import java.util.ArrayDeque;

public class ArrayDequeExample {
    public static void main(String[] args) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();

        deque.addFirst(1);
        deque.addLast(2);
        deque.addFirst(3);
        deque.addLast(4);

        while (!deque.isEmpty()) {
            System.out.println(deque.pollFirst());
        }
    }
}

В этом примере элементы вставляются и извлекаются с обеих сторон очереди, демонстрируя гибкость ArrayDeque.


Внутреннее устройство ArrayDeque

ArrayDeque основана на циклическом массиве, который расширяется по мере необходимости. Это позволяет поддерживать эффективное использование памяти и быструю вставку и удаление элементов с обеих сторон очереди.

public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable {
    private transient E[] elements;
    private transient int head;
    private transient int tail;

    public ArrayDeque() {
        elements = (E[]) new Object[16];
    }

    public ArrayDeque(int initialCapacity) {
        elements = (E[]) new Object[initialCapacity];
    }

    // Основные методы: addFirst, addLast, pollFirst, pollLast, etc.
}

Особенности и преимущества

Циклический массив: Использование циклического массива позволяет избежать необходимости перемещения элементов при вставке и удалении с обеих сторон.
Амортизированное постоянное время: Вставка и удаление элементов с обеих сторон выполняются в амортизированное постоянное время O(1), за исключением случаев расширения массива.
Отсутствие блокировок: ArrayDeque не синхронизирована, что делает её быстрее по сравнению с синхронизированными структурами данных, такими как LinkedBlockingDeque.
Гибкость: Поддержка операций вставки и удаления с обеих сторон очереди предоставляет большую гибкость в использовании.

Преимущества использования ArrayDeque

Производительность: ArrayDeque обеспечивает более высокую производительность по сравнению с LinkedList для операций вставки и удаления элементов с обеих сторон.
Гибкость: Она поддерживает как стековые (push, pop), так и очередные (offer, poll) операции, что делает её универсальной для различных задач.
Эффективное использование памяти: Благодаря циклическому массиву ArrayDeque эффективно использует память, минимизируя количество операций по перемещению элементов.

import java.util.ArrayDeque;

public class ArrayDequeExample {
    public static void main(String[] args) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();

        // Добавление элементов
        deque.addFirst(1);
        deque.addLast(2);
        deque.addFirst(3);
        deque.addLast(4);

        // Извлечение элементов
        System.out.println(deque.pollFirst()); // 3
        System.out.println(deque.pollLast());  // 4
        System.out.println(deque.pollFirst()); // 1
        System.out.println(deque.pollLast());  // 2
    }
}

В этом примере демонстрируются основные операции вставки и извлечения элементов с обеих сторон очереди.

Ссылки на полезные статьи (спасибо авторам за проделанную работу) :
https://www.baeldung.com/java-array-deque
https://metanit.com/java/tutorial/5.7.php

#Java #Training #Medium #ArrayDeque

Основные методы ArrayDeque и их применение

Основные методы ArrayDeque:

addFirst(E e):
Добавляет элемент в начало очереди. Если очередь заполнена, увеличивает её размер.

ArrayDeque<Integer> deque = new ArrayDeque<>();
deque.addFirst(10);
deque.addFirst(20);
System.out.println(deque); // [20, 10]

addLast(E e):
Добавляет элемент в конец очереди. Если очередь заполнена, увеличивает её размер.

deque.addLast(30);
System.out.println(deque); // [20, 10, 30]

offerFirst(E e):
Предлагает добавить элемент в начало очереди. Возвращает true, если элемент был добавлен успешно.

deque.offerFirst(40);
System.out.println(deque); // [40, 20, 10, 30]

offerLast(E e):
Предлагает добавить элемент в конец очереди. Возвращает true, если элемент был добавлен успешно.

deque.offerLast(50);
System.out.println(deque); // [40, 20, 10, 30, 50]

pollFirst():
Возвращает и удаляет первый элемент из очереди. Возвращает null, если очередь пуста.

Integer first = deque.pollFirst();
System.out.println(first); // 40
System.out.println(deque); // [20, 10, 30, 50]

pollLast():
Возвращает и удаляет последний элемент из очереди. Возвращает null, если очередь пуста.

Integer last = deque.pollLast();
System.out.println(last); // 50
System.out.println(deque); // [20, 10, 30]

peekFirst():
Возвращает первый элемент из очереди, не удаляя его. Возвращает null, если очередь пуста.

Integer peekFirst = deque.peekFirst();
System.out.println(peekFirst); // 20

peekLast():
Возвращает последний элемент из очереди, не удаляя его. Возвращает null, если очередь пуста.

Integer peekLast = deque.peekLast();
System.out.println(peekLast); // 30

push(E e):
Вставляет элемент на вершину стека. Эквивалентен методу addFirst(E e).

deque.push(60);
System.out.println(deque); // [60, 20, 10, 30]

pop():
Возвращает и удаляет элемент с вершины стека. Эквивалентен методу pollFirst().

Integer pop = deque.pop();
System.out.println(pop); // 60
System.out.println(deque); // [20, 10, 30]

Примеры использования ArrayDeque

Реализация стека с использованием ArrayDeque:

import java.util.ArrayDeque;

public class StackExample {
    public static void main(String[] args) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        stack.push(1);
        stack.push(2);
        stack.push(3);

        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

Реализация очереди с использованием ArrayDeque:

import java.util.ArrayDeque;

public class QueueExample {
    public static void main(String[] args) {
        ArrayDeque<Integer> queue = new ArrayDeque<>();

        queue.addLast(1);
        queue.addLast(2);
        queue.addLast(3);

        while (!queue.isEmpty()) {
            System.out.println(queue.pollFirst());
        }
    }
}

Реализация двусторонней очереди с использованием ArrayDeque:

import java.util.ArrayDeque;

public class DequeExample {
    public static void main(String[] args) {
        ArrayDeque<Integer> deque = new ArrayDeque<>();

        deque.addFirst(1);
        deque.addLast(2);
        deque.addFirst(3);
        deque.addLast(4);

        while (!deque.isEmpty()) {
            System.out.println(deque.pollFirst());
        }
    }
}

#Java #Training #Medium #ArrayDeque

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

Реализации 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

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

Тестирование и отладка

После реализации протестируйте, чтобы убедиться в правильной работе очереди.

Запустите проект:
Правой кнопкой на 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