Двусторонняя очередь

редактировать

В информатике - двусторонняя очередь (сокращенно deque, произносится колода) - это абстрактный тип данных, который обобщает очередь, для которой элементы могут быть добавлены или удалены либо спереди (голова), либо сзади (хвост). Его также часто называют связанным списком «голова-хвост», хотя правильно это относится к конкретной структуре данных реализации двухсторонней очереди (см. Ниже).

Содержание

1 Соглашения об именах
2 Различия и подтипы
3 Операции
4 Реализации
- 4.1 Чисто функциональная реализация
5 Поддержка языка
6 Сложность
7 Приложения
8 См. Также
9 Ссылки
10 Внешние ссылки

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

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

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

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

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

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

Операции

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

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

операцию	общее имя (я)	Ada	C ++	Java	Perl	PHP	Python	Ruby	Rust	JavaScript
вставить элемент сзади	inject, snoc, push	`Append`	`push_back`	`offerLast`	`push`	`array_push`	`append`	`push`	`push_back`	`push`
вставить элемент спереди	push, cons	`Prepend`	`push_front`	`offerFirst`	`unshift`	`array_unshift`	`appendleft`	`unshift`	`push_front`	`unshift`
удалить последний элемент	eject	`Delete_Last`	`pop_back`	`pollLast`	`pop`	`array_pop`	`pop`	`pop`	`pop_back`	`pop`
удалить первый элемент	pop	`Delete_First`	`pop_front`	`pollFirst`	`shift`	`array_shift`	`popleft`	`shift`	`pop_front`	`shift`
проверить последний элемент	peek	`Last_Element`	`назад`	`peekLast`	`$ array [-1]`	`end`	`[-1]`	`последний`	`задний`	`[.length - 1]`
проверить первый элемент		`First_Element`	`передний`	`peekFirst`	`$ a rray [0]`	`reset`	`[0]`	`first`	`front`	`[0]`

Реализации

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

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

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

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

Двусторонние очереди также могут быть реализованы как чисто функциональная структура данных. Существуют две версии реализации. Первый из них, называемый «двухсторонняя очередь в реальном времени», представлен ниже. Это позволяет очереди быть постоянным с операциями в $O (1) {\ displaystyle O (1)}$ $O (1)$ наихудшее время, но требует lazy списки с мемоизацией. Второй, без ленивых списков и мемоизации, представлен в конце разделов. Его амортизируемое время равно $O (1) {\ displaystyle O (1)}$ $O (1)$ , если постоянство не используется; но наихудшая сложность операции составляет $O (n) {\ displaystyle O (n)}$ $O (n)$ , где $n {\ displaystyle n}$ $n$ - число элементов в двусторонней очереди.

Напомним, что для списка l, | l |обозначает его длину, NILпредставляет пустой список, а CONS (h, t)представляет список, заголовок которого равен h, а конец - t. Функции drop (i, l)и take (i, l)возвращают список lбез его первых элементов i, и первые элементы iиз lсоответственно. Или, если | l | < i, они возвращают пустой список и lсоответственно.

Двусторонняя очередь представлена как шестерня lenf, f, sf, lenr, r, sr, где f- это связанный список, который содержит начало очереди длины lenf. Аналогично, r- это связанный список, который представляет собой обратную сторону задней части очереди длиной lenr. Кроме того, гарантируется, что | f | ≤ 2 | r | +1и | r | ≤ 2 | f | +1- интуитивно это означает, что ни передняя, ни задняя часть не содержат более трети списка плюс один элемент. Наконец, sfи srявляются хвостами fи r, они позволяют планировать момент, когда будут выполняться некоторые ленивые операции. Обратите внимание: когда двусторонняя очередь содержит nэлементов в переднем списке и nэлементов в заднем списке, то инвариант неравенства остается выполненным после iвставки и dудаления, когда (i + d) / 2 ≤ n. То есть между каждой перебалансировкой может происходить не более n / 2операций.

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

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

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

fun balance (q as (lenf, f, sf, lenr, r, sr)) = if lenf>2 * lenr + 1, тогда let val i = (left + lenr) div 2 val j = lenf + lenr - i val f '= take (i, f) val r' = rotateDrop (r, i, f) in (i, f ', f', j, r ', r') иначе если lenf>2 * lenr + 1, тогда пусть val j = (lenf + lenr) div 2 val i = lenf + lenr - j val r '= take (i, r) val f' = rotateDrop (f, i, r) in (i, f ', f', j, r ', r') else q

Обратите внимание, что без ленивой части реализации это была бы непостоянная реализация очереди в $O ( 1) {\ displaystyle O (1)}$ $O (1)$ амортизированное время. В этом случае списки sfи srмогут быть удалены из представления двусторонней очереди.

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

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

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

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

Прототип массива Javascript Массивы Perl имеют встроенную поддержку как для удаления (shift и pop ), так и для добавление элементов (unshift и push ) на обоих концах.

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

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

GHC Data.Sequence реализует эффективную функциональную структуру двухсторонней очереди в Haskell. Реализация использует 2–3 дерева пальцев, аннотированные размерами. Существуют и другие (быстрые) возможности для реализации чисто функциональных (таким образом, также постоянных ) двойных очередей (в большинстве случаев с использованием ленивых вычислений ). Каплан и Тарджан были первыми, кто реализовал оптимальные непрерывно постоянные цепные деки. Их реализация была строго функциональной в том смысле, что не использовала ленивую оценку. Okasaki упростил структуру данных, используя ленивую оценку с загрузочной структурой данных и снизив границы производительности с худшего случая до амортизированного. Каплан, Окасаки и Тарджан создали более простую, амортизированную версию без начальной загрузки, которая может быть реализована либо с использованием ленивого вычисления, либо более эффективно с использованием мутации в более широком, но все же ограниченном виде. Михэзау и Тарджан создали более простую (но все еще очень сложную) строго функциональную реализацию цепных дек, а также гораздо более простую реализацию строго функциональных некатенируемых дек, обе из которых имеют оптимальные границы наихудшего случая.

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

Сложность

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

Applications

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

См. Также

Ссылки

Внешние ссылки