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

Эта статья включает в себя список общих ссылок , но он остается в основном непроверенным, поскольку в нем отсутствуют соответствующие встроенные ссылки . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Январь 2014 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Представление очереди FIFO (first in, first out)

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

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

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

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

Реализация очереди [ править ]

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

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

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

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

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

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

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

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

Примеры [ править ]

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

класс  Queue  {  конструктор ()  {  это . items  =  new  Array ( 0 )  }  enqueue ( element )  {  this . предметы . push ( element )  }  dequeue ()  { это . предметы . shift ()  } }

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

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

Напомним, что для списка, обозначает его длину, что NIL представляет пустой список и представляет список, голова которого равна h, а хвост - t .${\ displaystyle l}$${\ displaystyle | l |}$${\ displaystyle \ operatorname {CONS} (h, t)}$

Очередь в реальном времени [ править ]

Структура данных, используемая для реализации наших очередей, состоит из трех связанных списков, где f - это начало очереди, r - конец очереди в обратном порядке. Инвариант структуры состоит в том, что s является задней частью f без первых элементов, то есть . Таким образом, конец очереди почти равен почти, а вставка элемента x в почти . Говорят почти, потому что в обоих этих результатах . Затем необходимо вызвать вспомогательную функцию, чтобы инвариант был удовлетворен. Необходимо рассмотреть два случая, в зависимости от того, пустой ли список, и в каком случае${\ 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 - пустой список. Этот счетчик позволяет нам гарантировать, что задний лист никогда не будет длиннее, чем передний лист. Кроме того, использование s , которое является хвостом f , заставляет вычислять часть (ленивого) списка f во время каждой операции хвоста и вставки . Следовательно, когда , список f полностью принудительный. Если бы это было не так, внутреннее представление f могло бы быть некоторым добавлением добавления ... добавления, и форсирование больше не было бы операцией с постоянным временем.${\displaystyle |f|-|r|}$${\displaystyle |f|=|r|}$${\displaystyle |f|=|r|}$

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

Обратите внимание, что без ленивой части реализации очередь в реальном времени была бы непостоянной реализацией очереди в амортизированном времени. В этом случае список s может быть заменен целым числом , и обратная функция будет вызываться, когда будет 0.${\displaystyle O(1)}$ ${\displaystyle |f|-|r|}$${\displaystyle s}$

См. Также [ править ]

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

Ссылки [ править ]

Общие ссылки [ править ]

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

Дальнейшее чтение [ править ]

• Дональд Кнут . Искусство программирования , Том 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 ++ , третье издание. Thomson Course Technology, 2005. ISBN 0-534-49182-0 . Глава 4: Стеки и очереди, стр. 137–169. 

Внешние ссылки [ править ]

Викискладе есть медиафайлы, связанные со структурой данных очереди .

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