Двусторонняя очередь - Double-ended queue

В Информатика, а двусторонняя очередь (сокращенно дек, произносится палуба^[1]) является абстрактный тип данных что обобщает очередь, для которых элементы могут быть добавлены или удалены либо спереди (голова), либо сзади (хвост).^[2] Его также часто называют связанный список "голова-хвост", хотя собственно это относится к конкретному структура данных выполнение двухсторонней очереди (см. ниже).

Соглашения об именах

Deque иногда пишется исключать из очереди, но такое использование обычно не рекомендуется в технической или технической литературе, потому что исключать из очереди также глагол, означающий «удалить из очереди». Тем не менее, несколько библиотеки и некоторые писатели, такие как Ахо, Хопкрофт, и Ульман в их учебнике Структуры данных и алгоритмы, по буквам исключать из очереди. Джон Митчелл, автор Концепции языков программирования, также использует эту терминологию.

Отличия и подтипы

Это отличается от абстрактного типа данных очереди или первым пришел-первым вышел список (ФИФО ), где элементы можно добавлять только с одного конца и удалять с другого. Этот общий класс данных имеет несколько возможных подтипов:

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

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

Операции

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

Имена в разных языках различаются; основные реализации включают:

операция	общее имя (а)	Ада	C ++	Ява	Perl	PHP	Python	Рубин	Ржавчина	JavaScript
вставить элемент сзади	вводить, снок, толкать	`Добавить`	`отталкивать`	`предложениеПоследнее`	`толкать`	`array_push`	`добавить`	`толкать`	`отталкивать`	`толкать`
вставить элемент спереди	толчок, минусы	`Подготовить`	`push_front`	`предложениеFirst`	`не сдвигать`	`array_unshift`	`добавление слева`	`не сдвигать`	`push_front`	`не сдвигать`
удалить последний элемент	выбросить	`Delete_Last`	`pop_back`	`опросПоследний`	`поп`	`array_pop`	`поп`	`поп`	`pop_back`	`поп`
удалить первый элемент	поп	`Delete_First`	`pop_front`	`pollFirst`	`сдвиг`	`array_shift`	`поплефт`	`сдвиг`	`pop_front`	`сдвиг`
изучить последний элемент	заглядывать	`Last_Element`	`назад`	`peekLast`	`$ array [-1]`	`конец`	`[-1]`	`последний`	`назад`	`[ .length - 1]`
изучить первый элемент		`Первый_элемент`	`передний`	`peekFirst`	`$ array [0]`	`перезагрузить`	`[0]`	`первый`	`передний`	`[0]`

Реализации

Существует как минимум два распространенных способа эффективной реализации двухсторонней очереди: с измененной динамический массив или с двусвязный список.

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

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

Чисто функциональная реализация

Двусторонние очереди также могут быть реализованы как чисто функциональная структура данных.^[3] Существуют две версии реализации. Первый, названный 'двухсторонняя очередь в реальном времени, представлен ниже. Это позволяет очереди быть настойчивый с операциями в $О (1)$ худшее время, но требует ленивый списки с мемоизация. Второй, без ленивых списков и мемоизации, представлен в конце разделов. Его амортизированный время - это $О (1)$ если настойчивость не используется; но наихудшая сложность операции $О (п)$ куда $п$ - количество элементов в двусторонней очереди.

Напомним, что для списка л, | l | обозначает его длину, что Ноль представляет собой пустой список и МИНУСЫ (ч, т) представляет собой список с заголовком час и чей хвост т. Функции капля (я, л) и возьми (я, л) вернуть список л без первого я элементы, а первый я элементы л, соответственно. Или если | l | <я, они возвращают пустой список и л соответственно.

Двусторонняя очередь представлена шестеркой. ленф, ф, нф, ленр, р, ср куда ж это связанный список который содержит переднюю часть очереди длины Lenf. По аналогии, р - это связанный список, который представляет собой обратную сторону задней части очереди длины Ленр. Кроме того, уверены, что | f | ≤ 2 | г | +1 и | г | ≤ 2 | f | +1 - интуитивно это означает, что ни передняя, ни задняя часть не содержат более трети списка плюс один элемент. Ну наконец то, нф и SR являются хвостами ж и из р, они позволяют запланировать момент принудительного выполнения некоторых ленивых операций. Обратите внимание: когда двусторонняя очередь содержит п элементы в переднем списке и п элементов в заднем списке, то инвариант неравенства остается выполненным после я вставки и d удаления, когда (я + г) / 2 ≤ п. То есть самое большее п / 2 операции могут происходить между каждой перебалансировкой.

Интуитивно, вставка элемента Икс перед двойной очередью ленф, ф, нф, ленр, ср ведет почти к двойной очереди lenf + 1, CONS (x, f), drop (2, sf), lenr, r, drop (2, sr), начало и конец двусторонней очереди lenf, CONS (x, f), sf, lenr, r, sr находятся Икс и почти lenf-1, f, drop (2, sf), lenr, r, drop (2, sr) соответственно, а голова и хвост lenf, NIL, NIL, lenr, CONS (x, NIL), drop (2, sr) находятся Икс и 0, NIL, NIL, 0, NIL, NIL соответственно. Функция вставки элемента в заднюю часть или удаления последнего элемента двусторонней очереди аналогична описанной выше функции, которая имеет дело с передней частью двусторонней очереди. Говорят почти потому что после вставки и после применения хвост, инвариант | г | ≤ 2 | f | +1 может больше не быть удовлетворенным. В этом случае требуется перебалансировать двустороннюю очередь.

Во избежание операции с ${displaystyle O (n)}$ затрат, алгоритм использует лень с мемоизацией и заставляет частично выполнить ребалансировку во время следующего (| l | + | r |) / 2 операций, то есть до следующей перебалансировки. Для создания расписания требуются некоторые вспомогательные ленивые функции. Функция rotateRev (е, г, а) возвращает список ж, а затем список р, а затем список а. В этой функции требуется, чтобы | г | -2 | ж | равно 2 или 3. Эта функция определяется по индукции как rotateRev (NIL, r, a) = reverse (r ++ a) где ++ - операция конкатенации, а по rotateRev (CONS (x, f), r, a) = CONS (x, rotateRev (f, drop (2, r), reverse (возьмите (2, r)) ++ a)). rotateRev (f, r, NIL) возвращает список ж за которым следует список р наоборот. Функция rotateDrop (f, j, r) который возвращается ж с последующим (р без jпервый элемент) также требуется, чтобы j <| f |. Это определяется rotateDrop (f, 0, r) == rotateRev (f, r, NIL), rotateDrop (f, 1, r) == rotateRev (f, drop (1, r), NIL) и rotateDrop (CONS (x, f), j, r) == CONS (x, rotateDrop (f, j-2), drop (2, r)).

Теперь функцию балансировки можно определить с помощью

весело баланс(q в качестве (Lenf, ж, нф, Ленр, р, SR)) =  если Lenf > 2* ленр +1 тогда    позволять вал я = (left + lenr) div 2        вал j = Lenf + Ленр - я        вал f ' = брать(я, ж)        вал р' = rotateDrop(р, я, ж)    в (я, f ', f ', j, р', р')  еще если Lenf > 2* ленр +1 тогда    позволять вал j = (ленф + ленр) div 2        вал я = Lenf + Ленр - j        вал р' = брать(я, р)        вал f ' = rotateDrop(ж, я, р)    в (я, f ', f ', j, р', р')  еще q

Обратите внимание, что без ленивой части реализации это была бы непостоянная реализация очереди в $О (1)$ амортизированное время. В этом случае списки нф и SR может быть удален из представления двусторонней очереди.

Языковая поддержка

Ада контейнеры предоставляют общие пакеты Ada.Containers.Vectors и Ada.Containers.Doubly_Linked_Lists, для реализаций динамического массива и связанного списка соответственно.

C ++ Стандартная библиотека шаблонов предоставляет шаблоны классов std :: deque и std :: listдля реализации нескольких массивов и связанных списков соответственно.

Начиная с Java 6, Java Collections Framework предоставляет новый Deque интерфейс, обеспечивающий возможность вставки и удаления на обоих концах. Это реализуется такими классами, как ArrayDeque (также новинка в Java 6) и LinkedList, предоставляя реализации динамического массива и связанного списка соответственно. Тем не менее ArrayDeque, вопреки своему названию, не поддерживает произвольный доступ.

Javascript Прототип массива & Perl массивы имеют встроенную поддержку для удаления (сдвиг и поп ) и добавив (не сдвигать и толкать ) элементов на обоих концах.

Python 2.4 представил коллекции модуль с поддержкой объекты deque. Он реализован с использованием двусвязного списка подмассивов фиксированной длины.

Начиная с PHP 5.3, расширение SPL PHP содержит класс SplDoublyLinkedList, который можно использовать для реализации структур данных Deque. Ранее для создания структуры Deque вместо этого приходилось использовать функции массива array_shift / unshift / pop / push.

GHC с Данные. Последовательность модуль реализует эффективную, функциональную структуру двухсторонней очереди в Haskell. Реализация использует 2-3 пальца дерева аннотированы размерами. Есть и другие (быстрые) возможности для реализации чисто функциональных (таким образом, настойчивый ) двойные очереди (большинство из них сильно ленивая оценка ).^[3]^[4] Каплан и Тарджан были первыми, кто реализовал оптимальные непрерывно постоянные цепные деки.^[5] Их реализация была строго функциональной в том смысле, что в ней не использовались ленивые вычисления. Okasaki упростил структуру данных, используя ленивую оценку с загрузочной структурой данных и снизив границы производительности с худшего случая до амортизированного. Каплан, Окасаки и Тарджан создали более простую, амортизированную версию без начальной загрузки, которая может быть реализована либо с использованием ленивого вычисления, либо более эффективно с использованием мутации в более широком, но все же ограниченном виде. Михэзау и Тарджан создали более простую (но все еще очень сложную) строго функциональную реализацию подключаемых дек, а также гораздо более простую реализацию строго функциональных некатенируемых дек, оба из которых имеют оптимальные границы наихудшего случая.

Ржавчины std :: коллекции включает VecDeque который реализует двустороннюю очередь с использованием растущего кольцевого буфера.

Сложность

В реализации двусвязного списка и при отсутствии накладных расходов на выделение / освобождение временная сложность всех двухсторонних операций О (1). Кроме того, временная сложность вставки или удаления посередине с учетом итератора составляет O (1); однако временная сложность произвольного доступа по индексу составляет O (n).
В растущем массиве амортизированный временная сложность всех двухсторонних операций составляет О (1). Кроме того, временная сложность произвольного доступа по индексу составляет O (1); но временная сложность вставки или удаления в середине На).

Приложения

Одним из примеров использования двухсторонней очереди является алгоритм кражи работы.^[6] Этот алгоритм реализует планирование задач для нескольких процессоров. Для каждого процессора поддерживается отдельная двухсторонняя очередь с выполняемыми потоками. Чтобы выполнить следующий поток, процессор получает первый элемент из двухсторонней очереди (используя операцию двухсторонней очереди «удалить первый элемент»). Если текущий поток разветвляется, он помещается обратно в начало двухсторонней очереди («вставить элемент вперед») и выполняется новый поток. Когда один из процессоров завершает выполнение своих собственных потоков (т.е. его двухсторонняя очередь пуста), он может «украсть» поток у другого процессора: он получает последний элемент из двухсторонней очереди другого процессора («удаляет последний элемент») и выполняет Это. Алгоритм кражи работы используется библиотекой Intel Threading Building Blocks (TBB) для параллельного программирования.

Смотрите также

внешняя ссылка

[1] Джесси Либерти; Сиддхартха Рао; Брэдли Джонс. C ++ за час в день, Sams научитесь самостоятельно, Издание шестое. Самс Паблишинг, 2009. ISBN 0-672-32941-7. Урок 18: Классы динамических массивов STL, стр. 486.

[2] Дональд Кнут. Искусство программирования, Том 1: Фундаментальные алгоритмы, Третье издание. Аддисон-Уэсли, 1997. ISBN 0-201-89683-4. Раздел 2.2.1: Стеки, очереди и дек, стр. 238–243.

[functional-3] а ^б Окасаки, Крис (сентябрь 1996 г.). Чисто функциональные структуры данных (PDF) (Кандидатская диссертация). Университет Карнеги Меллон. CMU-CS-96-177.

[4] Адам Л. Бухсбаум и Роберт Э. Тарджан. Конфлюентно постоянные декы посредством начальной загрузки структуры данных. Journal of Algorithms, 18 (3): 513–547, май 1995 г. (стр. 58, 101, 125).

[5] Хаим Каплан и Роберт Э. Тарьян. Чисто функциональные представления связанных отсортированных списков. В симпозиуме ACM по теории вычислений, страницы 202–211, май 1996 г. (стр. 4, 82, 84, 124)

[jacm-6] Блюмофе, Роберт Д.; Лейзерсон, Чарльз Э. (1999). «Планирование многопоточных вычислений путем кражи работы» (PDF). J ACM. 46 (5): 720–748. Дои:10.1145/324133.324234.

[1]

[2]

[3]

[4]

[5]

[6]

Примечательный структуры данных
Типы	Коллекция Контейнер
Абстрактный	Ассоциативный массив Multimap Список Куча Очередь Двусторонняя очередь Приоритетная очередь Двусторонняя приоритетная очередь Набор Multiset Непересекающееся множество
Массивы	Битовый массив Круглый буфер Динамический массив Хеш-таблица Дерево хешированных массивов Разреженная матрица
Связано	Список ассоциаций Связанный список Пропустить список Развернутый связанный список Связанный список XOR
Деревья	B-дерево Дерево двоичного поиска Дерево AA AVL дерево Красно-черное дерево Самобалансирующееся дерево Splay tree Куча Двоичная куча Биномиальная куча Куча Фибоначчи R-дерево R * дерево R + дерево R-дерево Гильберта Trie Хеш-дерево
Графики	Диаграмма двоичного решения Направленный ациклический граф Направленный ациклический граф слов
Список структур данных