Что такое Deque?

Sobes Copilot

Получайте ответы в реальном времени

Ответ от нейросети

sobes.tech AI

Deque (Double Ended Queue) — это линейная коллекция, которая поддерживает вставку и удаление элементов как с начала, так и с конца.

Основные характеристики:

Расширяет интерфейс Queue.
Позволяет использовать себя как стек (LIFO) или очередь (FIFO).
Предоставляет методы для работы с обоими концами: addFirst, addLast, removeFirst, removeLast, peekFirst, peekLast и др.

Основные реализации в Java:

ArrayDeque
LinkedList

Сравнение ArrayDeque и LinkedList в качестве Deque:

Характеристика	ArrayDeque	LinkedList
Внутренняя структура	Динамический массив	Двусвязный список
Производительность	Быстрая вставка/удаление с концов, последовательный доступ	Быстрая вставка/удаление с концов, медленный случайный доступ
Использование памяти	Эффективнее для примитивов, может требовать перераспределения	Больше накладных расходов на узлы, гибчее по размеру

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

// java
import java.util.ArrayDeque;
import java.util.Deque;

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

        // Добавление в начало
        deque.addFirst("Элемент 1");
        deque.addFirst("Элемент 2");

        // Добавление в конец
        deque.addLast("Элемент 3");

        System.out.println(deque); // Выведет: [Элемент 2, Элемент 1, Элемент 3]

        // Удаление из начала
        String first = deque.removeFirst();
        System.out.println("Удален из начала: " + first); // Выведет: Удален из начала: Элемент 2

        // Удаление из конца
        String last = deque.removeLast();
        System.out.println("Удален из конца: " + last);   // Выведет: Удален из конца: Элемент 3

        System.out.println(deque); // Выведет: [Элемент 1]
    }
}