В информатике двусторонняя очередь ( сокращенно deque , / d ɛ k / DEK [1] ) — это абстрактный тип данных , обобщающий очередь , для которой элементы могут добавляться или удаляться либо из передней (головной), либо из передней (головной) очереди. или назад (хвост). [2] Его также часто называют связным списком «голова-хвост» , хотя, собственно, это относится к конкретной реализации структуры данных двухсторонней очереди (см. ниже).
Deque иногда пишется dequeue , но такое использование обычно не рекомендуется в технической литературе или технических текстах, поскольку dequeue также является глаголом, означающим «удалить из очереди». Тем не менее, несколько библиотек и некоторые авторы, такие как Ахо , Хопкрофт и Ульман в своем учебнике «Структуры данных и алгоритмы» , называют это dequeue . Джон Митчелл , автор книги «Концепции языков программирования», также использует эту терминологию.
Это отличается от абстрактного типа данных очереди или списка «первым пришел — первым обслужен» ( FIFO ), где элементы можно добавлять только с одного конца и удалять с другого. Этот общий класс данных имеет несколько возможных подтипов:
Как базовые, так и наиболее распространенные типы списков в вычислениях, очереди и стеки можно считать специализацией деков и реализовать с их помощью. Дек — это структура данных, которая позволяет пользователям выполнять операции push и pop на обоих концах, обеспечивая гибкость в управлении порядком элементов.
Основными операциями с двухсторонней очередью являются постановка в очередь и удаление из очереди на обоих концах. Также обычно реализуются операции просмотра , которые возвращают значение на этом конце, не выводя его из очереди.
Имена различаются в зависимости от языка; основные реализации включают в себя:
Существует как минимум два распространенных способа эффективной реализации двухсторонней очереди: с помощью модифицированного динамического массива или с помощью двусвязного списка .
Подход динамического массива использует вариант динамического массива , который может расти с обоих концов, иногда называемый массивом 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между каждой ребалансировкой может произойти максимум операций.
Давайте сначала дадим реализацию различных операций, которые влияют на переднюю часть дека — минусы, голову и хвост. Эти реализации не обязательно учитывают инвариант. Во второй раз мы объясним, как изменить дек, который не удовлетворяет инварианту, в тот, который ему удовлетворяет. Однако они используют инвариант: если передняя часть пуста, то задняя часть содержит не более одного элемента. Операции, влияющие на конец списка, определяются аналогично симметрией.
пустой = ( 0 , NIL , NIL , 0 , NIL , NIL ) забавная вставка' ( x , ( len_front , front , Tail_front , len_rear , тыл , Tail_rear )) = ( len_front+ 1 , CONS ( x , front ), drop ( 2 , Tail_front ), len_rear , Rear , drop ( 2 , Tail_rear )) fun head ((_, CONS ( h , _), _, _, _, _)) = h fun head ((_, NIL , _, _) , CONS ( h , NIL ), _)) = h fun Tail' (( len_front , CONS ( head_front , front ), Tail_front , len_rear , тыл , Tail_rear )) = ( len_front - 1 , Front , падение ( 2 , Tail_front ) , len_rear , тыл , падение ( 2 , Tail_rear )) fun Tail' ((_, NIL , _, _, CONS ( h , NIL ), _)) = пустоОсталось объяснить, как определить метод balance, который перебалансирует дек, если инвариант нарушен insert'или нарушен. tailМетод insertи tailможно определить, сначала применив insert', tail'а затем применив balance.
fun Balance ( q as ( len_front , front , Tail_front , len_rear , Rear , Tail_rear ) ) = letfloor_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 задний' = RotateDrop ( rear , floor_half_len , front ) in ( ceil_half_len , front' , front' , floor_half_len , тыл' , тыл' ) иначе, если len_front > 2 *len_rear+ 1 , то пусть val тыл' = take ( floor_half_len , тыл ) val front' = RotateDrop ( фронт , ceil_half_len , тыл ) в ( ceil_half_len , front' , front' , Floor_half_len , тыл' , тыл' ) 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 , то RotateRev ( Front , Drop ( i , Rear ), NIL ) иначе пусть CONS ( x , Front' ) = Front в CONS ( x , RotateDrop ( Front' , j - 2 , падение ( 2 , зад )))где rotateRev(front, middle, rear)— функция, которая возвращает переднюю часть, за которой следует перевернутую середину, а затем заднюю часть. Эта функция также определена с использованием ленивости, чтобы гарантировать, что ее можно вычислить шаг за шагом, при этом каждый шаг выполняется по одному шагу insert'и tail'занимает постоянное время. Эта функция использует инвариант |rear|-2|front|2 или 3.
fun RotaRev ( NIL , задний , a ) = обратный ( задний ) ++a fun RotateRev ( CONS ( x , передний ), задний , a ) = CONS ( x , RotaRev ( передний , падение ( 2 , задний ), обратный ( взять ( 2 , сзади )) ++а ))где ++функция, объединяющая два списка.
Обратите внимание, что без ленивой части реализации это была бы непостоянная реализация очереди за 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вопреки своему названию, не поддерживает произвольный доступ.
Прототип Array в Javascript и массивы Perl имеют встроенную поддержку удаления (сдвига и извлечения) и добавления (сдвига и перемещения) элементов на обоих концах.
В Python 2.4 появился collectionsмодуль с поддержкой объектов deque. Он реализован с использованием двусвязного списка подмассивов фиксированной длины.
Начиная с PHP 5.3, расширение PHP SPL содержит класс SplDoublyLinkedList, который можно использовать для реализации структур данных Deque. Раньше для создания структуры Deque вместо этого приходилось использовать функции массива array_shift/unshift/pop/push.
Модуль Data.Sequence GHC реализует эффективную, функциональную структуру двухсторонних очередей в Haskell . В реализации используются 2–3-пальцевые деревья, аннотированные размерами. Существуют и другие (быстрые) возможности реализации чисто функциональных (таким образом, также постоянных ) двойных очередей (большинство из которых используют сильно ленивые вычисления ). [3] [4] Каплан и Тарьян были первыми, кто реализовал оптимальные сливающиеся постоянные цепные деки. [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) для параллельного программирования.