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

Очередь
Представление очереди FIFO (первым пришел — первым обслужен).
Временная сложность в обозначении большого О Операция Средний Худший случай Поиск На ​ ) На ​ ) Вставлять О(1) О(1) Удалить О(1) О(1) Пространственная сложность Космос На ​ ) На ​ )

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

класс   Queue   { 
     конструктор  ()   { 
         this  .   предметы   =   []; 
      } 

     очередь  (  элемент  )   { 
         это  .   предметы  .   нажать  (  элемент  ); 
      } 

     dequeue  ()   { 
         верните   это  .   предметы  .   сдвиг  (); 
      } 
 } 

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

Очереди также могут быть реализованы как чисто функциональная структура данных . Есть две реализации. Первый достигает только $O(1)$ за операцию в среднем . То есть амортизированное время $O(1)$, но отдельные операции могут занять $O(n)$где n — количество элементов в очереди. Вторая реализация называется очередью реального времени. и это позволяет очереди быть постоянной с операциями за время наихудшего случая O (1). Это более сложная реализация и требует ленивых списков с мемоизацией .

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

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

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

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

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

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

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

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

См. также

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

Ссылки

Общие ссылки

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

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

• Дональд Кнут . Искусство компьютерного программирования , Том 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 стека, очереди, дека и красно-черного дерева.