Deque | Комплект 1 (Введение и приложения)

Deque или Double Ended Queue — это обобщенная версия структуры данных Queue, которая позволяет вставлять и удалять с обоих концов.

Операции на Deque:
В основном следующие четыре основные операции выполняются в очереди:

insertFront () : добавляет элемент в начало Deque.
insertLast () : добавляет элемент в задней части Deque.
deleteFront () : удаляет элемент из передней части Deque.
deleteLast () : удаляет элемент из задней части Deque.

В дополнение к вышеуказанным операциям также поддерживаются следующие операции
getFront () : получает передний элемент из очереди.
getRear () : получает последний элемент из очереди.
isEmpty () : проверяет, является ли Deque пустым или нет.
isFull () : проверяет, заполнен ли Deque или нет.

Приложения Deque:
Поскольку Deque поддерживает операции как со стеком, так и с очередями, его можно использовать как в обоих случаях. Структура данных Deque поддерживает вращение по часовой стрелке и против часовой стрелки за время O (1), что может быть полезно в определенных приложениях.
Кроме того, проблемы, когда элементы должны быть удалены и / или добавлены на обоих концах, могут быть эффективно решены с помощью Deque. Например, см. « Максимум всех подмассивов размера k». , 0-1 BFS и найдите первый круговой тур, который посещает все бензиновые насосы .

Смотрите вики-страницу для другого примера алгоритма планирования заданий A-Steal, где Deque используется, поскольку операция удаления требуется с обоих концов.

Языковая поддержка:
C ++ STL обеспечивает реализацию Deque как std :: deque, а Java обеспечивает интерфейс Deque . Смотрите это для более подробной информации.
Deque in Java
Deque in Python

Реализация:
Deque может быть реализован с использованием двусвязного списка или кругового массива. В обеих реализациях мы можем реализовать все операции за O (1) раз. Мы скоро будем обсуждать реализацию структуры Deque Data на C / C ++.

Реализация Deque с использованием кругового массива

Пожалуйста, напишите комментарии, если вы обнаружите, что приведенные выше коды / алгоритмы неверны, или найдете другие способы решения той же проблемы.

Рекомендуемые посты:

• deque :: front () и deque :: back () в C ++ STL
• deque :: pop_front () и deque :: pop_back () в C ++ STL
• deque :: emplace_front () и deque :: emplace_back () в C ++ STL
• deque :: clear () и deque :: erase () в C ++ STL
• deque :: empty () и deque :: size () в C ++ STL
• deque :: begin () и deque :: end в C ++ STL
• deque :: at () и deque :: swap () в C ++ STL
• Приложения приоритетной очереди
• Приложения структуры данных очереди
• deque get_allocator в C ++ STL
• deque :: push_front () в C ++ STL
• deque :: push_back () в C ++ STL
• Deque in Python
• deque :: operator = и deque :: operator [] в C ++ STL
• deque emplace в C ++ STL