В информатике двухсторонняя очередь (сокращенно deque , / dɛk / DEK [1] ) — это абстрактный тип данных , обобщающий очередь , в которой элементы могут добавляться или удаляться либо из начала (головы), либо из конца (хвоста). [2] Ее также часто называют списком, связанным «голова-хвост» , хотя на самом деле это относится к конкретной реализации структуры данных deque (см. ниже).
Deque иногда пишется dequeue , но такое использование, как правило, не рекомендуется в технической литературе или технических записях, поскольку dequeue также является глаголом, означающим «удалять из очереди». Тем не менее, несколько библиотек и некоторые авторы, такие как Aho , Hopcroft и Ullman в своем учебнике Data Structures and Algorithms , пишут его как dequeue . Джон Митчелл , автор Concepts in Programming Languages , также использует эту терминологию.
Это отличается от абстрактного типа данных очереди или списка «первым пришел — первым вышел» ( FIFO ), где элементы могут быть добавлены только в один конец и удалены с другого. Этот общий класс данных имеет несколько возможных подтипов:
Оба основных и наиболее распространенных типа списков в вычислениях, очереди и стеки, можно считать специализациями deques и реализовать с помощью deques. Deque — это структура данных, которая позволяет пользователям выполнять операции push и pop на обоих концах, обеспечивая гибкость в управлении порядком элементов.
Базовые операции на deque — enqueue и dequeue на обоих концах. Также обычно реализуются операции peek , которые возвращают значение на этом конце без его dequeue.
Названия различаются в зависимости от языка; основные реализации включают в себя:
Существует как минимум два распространенных способа эффективной реализации дека: с помощью модифицированного динамического массива или с помощью двусвязного списка .
Подход с динамическим массивом использует вариант динамического массива , который может расти с обоих концов, иногда называемый массивом deques . Эти массивы deques обладают всеми свойствами динамического массива, такими как произвольный доступ с постоянным временем , хорошая локальность ссылок и неэффективная вставка/удаление в середине, с добавлением амортизированной вставки/удаления с постоянным временем на обоих концах, а не только на одном конце. Три распространенных реализации включают:
Двусторонние очереди также могут быть реализованы как чисто функциональная структура данных . [3] : 115 Существуют две версии реализации. Первая из них, называемая « реально-временной deque », представлена ниже. Она позволяет очереди быть устойчивой с операциями за время O (1) в худшем случае, но требует ленивых списков с мемоизацией . Вторая версия, без ленивых списков и мемоизации, представлена в конце разделов. Ее амортизированное время составляет O (1), если не используется сохранение; но наихудшая временная сложность операции составляет O ( n ), где n — количество элементов в двусторонней очереди.
Напомним, что для списка lобозначает |l|его длину, которая NILпредставляет пустой список, а CONS(h, t)представляет список, голова которого hи хвост которого t. Функции drop(i, l)и take(i, l)возвращают список lбез его первых iэлементов, и первые iэлементы l, соответственно. Или, если |l| < i, они возвращают пустой список и lсоответственно.
Двусторонняя очередь представлена в виде шестерки (len_front, front, tail_front, len_rear, rear, tail_rear), где front— связанный список , содержащий начало очереди длины len_front. Аналогично rear— связанный список, представляющий собой обратную сторону конца очереди длины len_rear. Кроме того, гарантируется, что |front| ≤ 2|rear|+1и |rear| ≤ 2|front|+1— интуитивно это означает, что и начало, и конец содержат от трети минус один до двух третей плюс один из элементов. Наконец, tail_frontи tail_rearявляются хвостами frontи rear, они позволяют планировать момент, когда некоторые ленивые операции принудительно выполняются. Обратите внимание, что когда двусторонняя очередь содержит nэлементы в начале списка и nэлементы в конце списка, то инвариант неравенства остается удовлетворенным после iвставок и dудалений, когда (i+d) ≤ n/2. То есть, максимум n/2операций может произойти между каждой перебалансировкой.
Давайте сначала дадим реализацию различных операций, которые влияют на начало дека - cons, head и tail. Эти реализации не обязательно учитывают инвариант. Во второй раз мы объясним, как изменить дек, который не удовлетворяет инварианту, в тот, который ему удовлетворяет. Однако они используют инвариант, в том смысле, что если начало пусто, то в конце списка не более одного элемента. Операции, влияющие на конец списка, определяются аналогично симметрией.
пусто = ( 0 , NIL , NIL , 0 , NIL , NIL ) забавная вставка ' ( x , ( len_front , front , tail_front , len_rear , rear , tail_rear )) = ( len_front + 1 , CONS ( x , front ), drop ( 2 , tail_front ), len_rear , rear , drop ( 2 , tail_rear )) забавная голова ((_, CONS ( h , _), _, _, _, _)) = h забавная голова ((_, NIL , _, _, CONS ( h , NIL ), _)) = h забавный хвост ' (( len_front , CONS ( head_front , front ), tail_front , len_rear , rear , tail_rear )) = ( len_front - 1 , front , drop ( 2 , tail_front ), len_rear , rear , drop ( 2 , tail_rear )) забавный хвост ((_, NIL , _, _, CONS ( h , NIL ), _)) = пустоОсталось объяснить, как определить метод balance, который перебалансирует deque, если insert'или tailнарушил инвариант. Метод insertи tailможно определить, сначала применив insert'и tail', а затем применив balance.
fun balance ( q as ( len_front , front , tail_front , len_rear , rear , tail_rear )) = let floor_half_len = ( len_front + len_rear ) / 2 in let ceil_half_len = len_front + len_rear - floor_half_len in if len_front > 2 * len_rear + 1 then let val front' = take ( ceil_half_len , front ) val rear' = rotateDrop ( rear , floor_half_len , front ) in ( ceil_half_len , front ' , front ' , floor_half_len , rear ' , rear' ) else if len_front > 2 * len_rear + 1 then let val rear' = take ( floor_half_len , rear ) val front' = rotateDrop ( front , ceil_half_len , rear ) in ( ceil_half_len , front' , front' , floor_half_len , rear' , rear' ) else qгде rotateDrop(front, i, rear))возвращаем конкатенацию frontи drop(i, rear). Это front' = rotateDrop(front, ceil_half_len, rear)помещается в front'содержимое frontи содержимое , rearкоторое еще не находится в rear'. Поскольку удаление nэлементов занимает время, мы используем ленивость, чтобы гарантировать, что элементы удаляются по два, причем во время каждой операции выполняется два удаления . tail'insert'
fun rotateDrop ( front , i , rear ) = если i < 2 then rotateRev ( front , drop ( i , rear ), NIL ) иначе let CONS ( x , front' ) = front in CONS ( x , rotateDrop ( front' , j- 2 , drop ( 2 , rear )))где rotateRev(front, middle, rear)— функция, которая возвращает переднюю часть, затем середину, перевернутую, затем заднюю. Эта функция также определена с использованием лени, чтобы гарантировать, что ее можно вычислить пошагово, с одним шагом, выполняемым в течение каждого insert'и tail'и занимающим постоянное время. Эта функция использует инвариант, который |rear|-2|front|равен 2 или 3.
fun rotateRev ( NIL , rear , a ) = reverse ( back ) ++a fun rotateRev ( CONS ( x , front ), rear , a ) = CONS ( x , rotateRev ( front , drop ( 2 , rear ), reverse ( take ( 2 , rear )) ++a ))где ++— функция, объединяющая два списка.
Обратите внимание, что без ленивой части реализации это была бы неперсистентная реализация очереди за O (1) амортизированное время . В этом случае списки tail_frontи tail_rearможно было бы удалить из представления двухсторонней очереди.
Контейнеры Ada предоставляют универсальные пакеты 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 имеют встроенную поддержку как удаления (shift и pop), так и добавления (unshift и push) элементов на обоих концах.
В Python 2.4 появился collectionsмодуль с поддержкой объектов deque. Он реализован с использованием двусвязного списка подмассивов фиксированной длины.
Начиная с PHP 5.3, расширение PHP SPL содержит класс 'SplDoublyLinkedList', который может использоваться для реализации структур данных Deque. Раньше для создания структуры Deque приходилось использовать функции массива array_shift/unshift/pop/push.
Модуль Data.Sequence от GHC реализует эффективную функциональную структуру deque в Haskell . Реализация использует 2–3-пальцевые деревья, аннотированные размерами. Существуют и другие (быстрые) возможности реализовать чисто функциональные (следовательно, также постоянные ) двойные очереди (большинство из которых используют сильно ленивые вычисления ). [3] [4] Каплан и Тарьян были первыми, кто реализовал оптимальные конфлюэнтно постоянные катируемые deque. [5] Их реализация была строго чисто функциональной в том смысле, что она не использовала ленивые вычисления. Окасаки упростил структуру данных, используя ленивые вычисления с бутстрепированной структурой данных и ухудшив границы производительности от наихудшего случая до амортизированной. [6] Каплан, Окасаки и Тарьян создали более простую, не бутстрепированную, амортизированную версию, которая может быть реализована либо с использованием ленивых вычислений, либо более эффективно с использованием мутации в более широкой, но все еще ограниченной манере. [7] Михаеску и Тарьян создали более простую (но все еще очень сложную) строго чисто функциональную реализацию сцепляемых деков, а также гораздо более простую реализацию строго чисто функциональных несцепляемых деков, обе из которых имеют оптимальные границы в худшем случае. [8]
В состав Rust std::collectionsвходит VecDeque, который реализует двустороннюю очередь с использованием расширяемого кольцевого буфера.
_-_Google_Android_12_(cropped).png/1280px-Back_button_history_(Ecosia_browser_-_Google_Pixel_4a)_-_Google_Android_12_(cropped).png){kind=tracking}
Одним из примеров использования дека является алгоритм захвата работы . [9] Этот алгоритм реализует планирование задач для нескольких процессоров. Для каждого процессора поддерживается отдельная дека с потоками для выполнения. Для выполнения следующего потока процессор получает первый элемент из дека (используя операцию дека «удалить первый элемент»). Если текущий поток разветвляется, он помещается обратно в начало дека («вставить элемент спереди»), и выполняется новый поток. Когда один из процессоров завершает выполнение своих потоков (т. е. его дек пуст), он может «украсть» поток у другого процессора: он получает последний элемент из дека другого процессора («удалить последний элемент») и выполняет его. Алгоритм захвата работы используется библиотекой Intel Threading Building Blocks (TBB) для параллельного программирования.