Очередь (абстрактный тип данных) - Queue (abstract data type)

Очередь
Сложность времени в нотация большой O
Алгоритм Средний Худший случай Космос O (п) O (п) Поиск O (п) O (п) Вставлять О (1) О (1) Удалить О (1) О (1)

Представление ФИФО (первый пришел, первый ушел) очередь

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

учебный класс Очередь {    конструктор()     {        это.Предметы = новый Множество(0)    }    ставить в очередь(элемент)       {        это.Предметы.толкать(элемент)    }    исключать из очереди()     {        это.Предметы.сдвиг()    }}

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

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

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

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

Структура данных, используемая для реализации наших очередей, состоит из трех связанные списки ${displaystyle (f,r,s)}$ куда ж это начало очереди, р это конец очереди в обратном порядке. Инвариант конструкции таков, что 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,{ ext{NIL}})=(f',{ ext{NIL}},f')}$ куда ${displaystyle f'}$ является ж с последующим р наоборот.

Позвоните нам ${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,{ ext{NIL}})}$Индуктивное определение поворота: ${displaystyle operatorname {rotate} ({ ext{NIL}},operatorname {Cons} (y,{ ext{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 в структуре данных имеет две цели. Этот список служит счетчиком для ${displaystyle |f|-|r|}$, в самом деле, ${displaystyle |f|=|r|}$ если и только если s это пустой список. Этот счетчик позволяет нам гарантировать, что задний лист никогда не будет длиннее, чем передний лист. Кроме того, используя s, который является хвостом ж, принудительно вычисляет часть (ленивого) списка ж во время каждого хвост и вставлять операция. Следовательно, когда ${displaystyle |f|=|r|}$, список ж полностью принудительно. Если бы это было не так, внутреннее представление ж может быть добавлением из ... из добавления, и форсирование больше не будет операцией с постоянным временем.

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

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

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

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

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

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

1. «Очередь (Java Platform SE 7)». Docs.oracle.com. 2014-03-26. Получено 2014-05-22.
2. Окасаки, Крис. «Чисто функциональные структуры данных» (PDF).
3. Худ, Роберт; Мелвилл, Роберт (ноябрь 1981). «Операции с очередями в реальном времени в чистом Лиспе». Письма об обработке информации. 13 (2). HDL:1813/6273.

Общие ссылки

• Эта статья включает материалы общественного достояния от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 ++, Третье издание. Технология курса Томсона, 2005. ISBN  0-534-49182-0. Глава 4: Стеки и очереди, стр. 137–169.

внешняя ссылка

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