Что такое Deque

`Deque` (Double Ended Queue) — это тип данных, представляющий собой двустороннюю очередь. Это интерфейс, расположенный в пакете `java.util`. Он поддерживает вставку и удаление элементов как с начала, так и с конца очереди, что делает его более универсальным по сравнению с обычной очередью (`Queue`), которая работает по принципу FIFO (First-In-First-Out).

Основные особенности и методы:

  1. Двусторонность: Позволяет добавлять и удалять элементы с обоих концов.
  2. Универсальность: Может использоваться как стек (LIFO - Last-In-First-Out) или как очередь (FIFO).
  3. Методы для работы с началом очереди:
  • `addFirst(e)`: Добавляет элемент в начало очереди.
  • `offerFirst(e)`: Добавляет элемент в начало очереди; возвращает `true`, если элемент был добавлен, иначе `false`.
  • `removeFirst()`: Удаляет и возвращает первый элемент очереди.
  • `pollFirst()`: Удаляет и возвращает первый элемент очереди; возвращает `null`, если очередь пуста.
  • `getFirst()`: Возвращает первый элемент очереди без его удаления.
  • `peekFirst()`: Возвращает первый элемент очереди без его удаления; возвращает `null`, если очередь пуста.

4. Методы для работы с концом очереди:

  •  `addLast(e)`: Добавляет элемент в конец очереди.
  • `offerLast(e)`: Добавляет элемент в конец очереди; возвращает `true`, если элемент был добавлен, иначе `false`.
  • `removeLast()`: Удаляет и возвращает последний элемент очереди.
  • `pollLast()`: Удаляет и возвращает последний элемент очереди; возвращает `null`, если очередь пуста.
  • `getLast()`: Возвращает последний элемент очереди без его удаления.
  • `peekLast()`: Возвращает последний элемент очереди без его удаления; возвращает `null`, если очередь пуста.

Реализации:

  • `ArrayDeque`: Реализация `Deque`, основанная на динамическом массиве. Она обеспечивает высокую производительность для большинства операций и не имеет ограничений на емкость.
  • `LinkedList`: Кроме того, что `LinkedList` реализует интерфейс `List`, он также реализует интерфейс `Deque`. Это связанный список, поддерживающий все операции двусторонней очереди.

Пример:

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("1");
deque.addLast("2");
System.out.println(deque.getFirst()); // Выведет "1"
System.out.println(deque.getLast()); // Выведет "2"

`Deque` предлагает гибкость в выборе подхода к управлению коллекцией элементов, делая его подходящим для различных сценариев использования, включая реализацию стеков и очередей.

March 7, 2024, easyoffer

Примеры ответов: