Очередь (абстрактный тип данных)

Абстрактный тип данных

В информатике очередь — это совокупность объектов, которые поддерживаются в последовательности и могут быть изменены путем добавления объектов на одном конце последовательности и удаления объектов с другого конца последовательности. По соглашению, конец последовательности, в котором добавляются элементы, называется «задним», «хвостом» или «задней частью очереди», а конец, в котором элементы удаляются, называется «головой» или «передней частью очереди», аналогично словам, используемым, когда люди выстраиваются в очередь в ожидании товаров или услуг.

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

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

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

Реализация очереди

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

Массивы фиксированной длины ограничены по емкости, однако утверждение о том, что элементы необходимо копировать в начало очереди, неверно. Простой прием: превратить массив в замкнутый круг и позволить голове и хвосту бесконечно перемещаться по этому кругу, что делает ненужным перемещение элементов, хранящихся в массиве. Если n — размер массива, то вычисление индексов по модулю n превратит массив в круг. Это по-прежнему концептуально самый простой способ построения очереди на языке высокого уровня , но, по общему признанию, он немного замедляет работу, поскольку индексы массива необходимо сравнивать с нулем, а размер массива сравним со временем, затраченным на проверьте, выходит ли индекс массива за пределы, что делают некоторые языки, но этот метод, безусловно, будет предпочтительным методом для быстрой и грязной реализации или для любого языка высокого уровня, который не имеет синтаксиса указателей. Размер массива должен быть объявлен заранее, но некоторые реализации просто удваивают объявленный размер массива, когда происходит переполнение. Большинство современных языков с объектами или указателями могут реализовывать или иметь библиотеки для динамических списков. Такие структуры данных могут не указывать фиксированный предел емкости, кроме ограничений памяти. Переполнение очереди возникает при попытке добавить элемент в полную очередь, а опустошение очереди происходит при попытке удалить элемент из пустой очереди.

Ограниченная очередь — это очередь, ограниченная фиксированным количеством элементов. ^[1]

Существует несколько эффективных реализаций очередей FIFO. Эффективная реализация — это та, которая может выполнять операции — постановку в очередь и удаление из очереди — за время O(1) .

• Связанный список
  • Двусвязный список имеет O(1) операций вставки и удаления на обоих концах, поэтому это естественный выбор для очередей.
  • Обычный односвязный список имеет эффективную вставку и удаление только на одном конце. Однако небольшая модификация — сохранение указателя на последний узел в дополнение к первому — позволит реализовать эффективную очередь.
• Дек , реализованный с использованием модифицированного динамического массива

Очереди и языки программирования

Очереди могут быть реализованы как отдельный тип данных или могут рассматриваться как частный случай двусторонней очереди (deque) и не реализовываться отдельно. Например, Perl и Ruby позволяют помещать и извлекать массив с обоих концов, поэтому можно использовать функции push иshift для постановки и удаления списка из очереди (или, наоборот, можно использовать unshift и pop ), ^[2] хотя в некоторых случаях эти операции неэффективны.

Стандартная библиотека шаблонов C++ предоставляет queueшаблонный класс, который ограничен только операциями push/pop. Начиная с J2SE5.0, библиотека Java содержит Queueинтерфейс, определяющий операции с очередью; реализующие классы включают LinkedListи (начиная с J2SE 1.6) ArrayDeque. PHP имеет класс SplQueue и сторонние библиотеки, такие как beanstalk'd и Gearman .

Пример

Простая очередь, реализованная на JavaScript :

класс Queue { конструктор () { this . предметы = []; }         очередь ( элемент ) { это . предметы . нажать ( элемент ); }    dequeue () { вернуть это . предметы . сдвиг (); } }    

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

Очереди также могут быть реализованы как чисто функциональная структура данных . ^[3] Существует две реализации. Первый из них в среднем достигает только одной операции . То есть амортизированное время равно , но отдельные операции могут занимать где n — количество элементов в очереди. Вторая реализация называется очередью реального времени ^[4] и позволяет очереди сохранять постоянство операций за время наихудшего случая O(1). Это более сложная реализация и требует ленивых списков с мемоизацией . ${\displaystyle O(1)}$ ${\displaystyle O(1)}$ ${\displaystyle O(n)}$

Амортизированная очередь

Данные этой очереди хранятся в двух односвязных списках с именами и . Список содержит переднюю часть очереди. Список содержит оставшиеся элементы (то есть конец очереди) в обратном порядке . Его легко вставить в начало очереди, добавив узел в начале очереди . А если не пусто, его легко удалить из конца очереди, удалив узел во главе . Если значение пусто, список переворачивается и назначается , а затем удаляется глава . ${\displaystyle f}$ ${\displaystyle r}$ ${\displaystyle f}$ ${\displaystyle r}$ ${\displaystyle f}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle f}$ ${\displaystyle r}$ ${\displaystyle r}$

Вставка («постановка в очередь») всегда требует времени. Удаление («удаление из очереди») происходит , когда список не пуст. Когда пусто, обратный процесс принимает где количество элементов в . Но мы можем сказать, что это амортизированное время, потому что каждый элемент должен был быть вставлен, и мы можем назначить постоянную стоимость для каждого элемента в обратном направлении к тому моменту, когда он был вставлен. ${\displaystyle O(1)}$ ${\displaystyle O(1)}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle O(n)}$ ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle O(1)}$ ${\displaystyle f}$

Очередь в реальном времени

Очередь реального времени обеспечивает время для всех операций без амортизации. Это обсуждение будет техническим, поэтому помните, что для списка обозначает его длину, а NIL представляет пустой список и представляет список, голова которого равна h , а хвост — t . ${\displaystyle O(1)}$ ${\displaystyle l}$ ${\displaystyle |l|}$ ${\displaystyle \operatorname {CONS} (h,t)}$

Структура данных, используемая для реализации наших очередей, состоит из трех односвязных списков , где f — начало очереди, а r — конец очереди в обратном порядке. Инвариант структуры состоит в том, что s — это задняя часть f без первых элементов, то есть . Тогда хвост очереди будет почти , и вставка элемента x будет почти . Это сказано почти, потому что в обоих этих результатах . Затем необходимо вызвать вспомогательную функцию , чтобы инвариант был удовлетворен. Необходимо рассмотреть два случая, в зависимости от того, является ли список пустым (в этом случае ) или нет. Формальное определение: и где f, за которым следует r, перевернуто. ${\displaystyle (f,r,s)}$ ${\displaystyle |r|}$ ${\displaystyle |s|=|f|-|r|}$ ${\displaystyle (\operatorname {CONS} (x,f),r,s)}$ ${\displaystyle (f,r,s)}$ ${\displaystyle (f,r,s)}$ ${\displaystyle (f,\operatorname {CONS} (x,r),s)}$ ${\displaystyle |s|=|f|-|r|+1}$ ${\displaystyle aux}$ ${\displaystyle s}$ ${\displaystyle |r|=|f|+1}$ ${\displaystyle \operatorname {aux} (f,r,\operatorname {Cons} (\_,s))=(f,r,s)}$ ${\displaystyle \operatorname {aux} (f,r,{\text{NIL}})=(f',{\text{NIL}},f')}$ ${\displaystyle f'}$

Давайте вызовем функцию, которая возвращает f, за которым следует r , в обратном порядке. Кроме того, предположим, что , поскольку это тот случай, когда вызывается эта функция. Точнее, мы определяем ленивую функцию , которая принимает на вход три списка такие , что и возвращает конкатенацию f , r, обращенного вспять, и a . Затем . Индуктивное определение вращения — это и . Время его выполнения равно , но, поскольку используется отложенное вычисление, вычисление задерживается до тех пор, пока результаты не будут получены в результате вычислений. ${\displaystyle \operatorname {reverse} (f,r)}$ ${\displaystyle |r|=|f|+1}$ ${\displaystyle \operatorname {rotate} (f,r,a)}$ ${\displaystyle |r|=|f|+1}$ ${\displaystyle \operatorname {reverse} (f,r)=\operatorname {rotate} (f,r,{\text{NIL}})}$ ${\displaystyle \operatorname {rotate} ({\text{NIL}},\operatorname {Cons} (y,{\text{NIL}}),a)=\operatorname {Cons} (y,a)}$ ${\displaystyle \operatorname {rotate} (\operatorname {CONS} (x,f),\operatorname {CONS} (y,r),a)=\operatorname {Cons} (x,\operatorname {rotate} (f,r,\operatorname {CONS} (y,a)))}$ ${\displaystyle O(r)}$

Список в структуре данных имеет две цели. Этот список действительно служит счетчиком для , тогда и только тогда , когда s — пустой список. Этот счетчик позволяет нам гарантировать, что задний список никогда не будет длиннее переднего. Кроме того, использование s , который является хвостом f , приводит к принудительному вычислению части (ленивого) списка f во время каждой операции хвоста и вставки . Следовательно, при , список f является полностью форсированным. Если бы это было не так, внутреннее представление f могло бы быть некоторым добавлением или добавлением... или добавлением, и форсирование больше не было бы операцией с постоянным временем. ${\displaystyle |f|-|r|}$ ${\displaystyle |f|=|r|}$ ${\displaystyle |f|=|r|}$

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

• Портал компьютерного программирования

• Круговой буфер
• Двусторонняя очередь (deque)
• Приоритетная очередь
• Теория массового обслуживания
• Стек (абстрактный тип данных) – «противоположность» очереди: LIFO (Last In First Out)

Рекомендации

1. «Очередь (платформа Java SE 7)» . Документы.oracle.com. 26 марта 2014 г. Проверено 22 мая 2014 г.
2. «Массив (Ruby 3.1)» . 25 декабря 2021 г. Проверено 11 мая 2022 г.
3. Окасаки, Крис. «Чисто функциональные структуры данных» (PDF) .
4. Худ, Роберт; Мелвилл, Роберт (ноябрь 1981 г.). «Операции с очередью в реальном времени на чистом Лиспе». Письма об обработке информации . 13 (2): 50–54. дои : 10.1016/0020-0190(81)90030-2. hdl : 1813/6273 .

Общие ссылки

•  Эта статья включает общедоступные материалы Пола Э. Блэка. «Ограниченная очередь». Словарь алгоритмов и структур данных . НИСТ .

дальнейшее чтение

• Дональд Кнут . Искусство компьютерного программирования , Том 1: Фундаментальные алгоритмы , Третье издание. Аддисон-Уэсли, 1997. ISBN 0-201-89683-4 . Раздел 2.2.1: Стеки, очереди и удаление из очередей, стр. 238–243. 
• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 10.1: Стеки и очереди, стр. 200–204. 
• Уильям Форд, Уильям Топп. Структуры данных с C++ и STL , второе издание. Прентис Холл, 2002. ISBN 0-13-085850-1 . Глава 8: Очереди и очереди с приоритетом, стр. 386–390. 
• Адам Дроздек. Структуры данных и алгоритмы в C++ , третье издание. Технология курса Томсона, 2005. ISBN 0-534-49182-0 . Глава 4: Стеки и очереди, стр. 137–169. 

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

• Краткое руководство по STL
• Реализация VBScript стека, очереди, дека и красно-черного дерева.