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
0.00 (0%) 0 votes