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

«Деке» перенаправляется сюда. Не путать с удалением из очереди, операцией очереди .

Не путать с двусторонней приоритетной очередью .

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

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

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

Различия и подтипы

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

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

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

Операции

UML class diagram of a double-ended queue

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

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

операция	общее имя (имена)	Есть	С++	Ява	Перл	PHP	Питон	Руби	Ржавчина	JavaScript
вставить элемент сзади	вводить, нюхать, толкать	Append	push_back	offerLast	push	array_push	append	push	push_back	push
вставить элемент спереди	толчок, минусы	Prepend	push_front	offerFirst	unshift	array_unshift	appendleft	unshift	push_front	unshift
удалить последний элемент	выбрасывать	Delete_Last	pop_back	pollLast	pop	array_pop	pop	pop	pop_back	pop
удалить первый элемент	поп	Delete_First	pop_front	pollFirst	shift	array_shift	popleft	shift	pop_front	shift
проверить последний элемент	заглянуть	Last_Element	back	peekLast	$array[-1]	end	<obj>[-1]	last	back	<obj>.at(-1)
изучить первый элемент		First_Element	front	peekFirst	$array[0]	reset	<obj>[0]	first	front	<obj>[0]

Реализации

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

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

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

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

Двусторонние очереди также можно реализовать как чисто функциональную структуру данных . Существуют две версии реализации. Первый из них, называемый « 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 операции могут происходить между каждой ребалансировкой.

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

empty = (0, NIL, NIL, 0, NIL, NIL)
fun insert'(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))
fun head((_, CONS(h, _), _, _, _, _)) = h
fun head((_, NIL, _, _, CONS(h, NIL), _)) = h
fun tail'((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))
fun tail'((_, NIL, _, _, CONS(h, NIL), _)) = empty

Осталось объяснить, как определить метод balance это перебалансирует дек, если 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 элементы берут $O(n)$ время мы используем ленивость, чтобы гарантировать, что элементы отбрасываются по два, причем два отбрасывания выполняются в течение каждого tail' и каждый insert' операция.

fun rotateDrop(front, i, rear) =
  if i < 2 then rotateRev(front, drop(i, rear), NIL)
  else 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(rear)++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 Прототип Array и массивы Perl имеют встроенную поддержку удаления ( shift и pop ) и добавления ( unshift и push ) элементов на обоих концах.

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

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

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

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

Сложность

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

Приложения

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

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

См. также

• Трубка
• Приоритетная очередь

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

• Типобезопасная реализация дека с открытым исходным кодом в Comprehensive C Archive Network
• Документация SGI STL: deque<T, Alloc>
• Проект кода: углубленное исследование контейнера STL Deque
• Реализация Deque на C. Архивировано 6 марта 2014 г. на Wayback Machine.
• Реализация VBScript стека, очереди, дека и красно-черного дерева.
• Множественные реализации необъединяемых деков в Haskell