В информатике очередь — это набор сущностей , которые поддерживаются в последовательности и могут быть изменены путем добавления сущностей на одном конце последовательности и удаления сущностей с другого конца последовательности. По соглашению, конец последовательности, в котором добавляются элементы, называется задней частью, хвостом или тылом очереди, а конец, в котором удаляются элементы, называется головой или фронтом очереди, аналогично словам, используемым, когда люди выстраиваются в очередь, чтобы дождаться товаров или услуг.
Операция добавления элемента в конец очереди называется enqueue , а операция удаления элемента из начала очереди называется dequeue . Другие операции также могут быть разрешены, часто включая операцию peek или front , которая возвращает значение следующего элемента, подлежащего удалению из очереди, не удаляя его из очереди.
Операции очереди делают ее структурой данных «первым пришел — первым вышел» (FIFO) . В структуре данных FIFO первый элемент, добавленный в очередь, будет первым удаленным. Это эквивалентно требованию, что после добавления нового элемента все элементы, которые были добавлены ранее, должны быть удалены до того, как новый элемент может быть удален. Очередь является примером линейной структуры данных или, более абстрактно, последовательной коллекции. Очереди распространены в компьютерных программах, где они реализованы как структуры данных, связанные с процедурами доступа, как абстрактная структура данных или в объектно-ориентированных языках как классы.
Очередь имеет два конца: верхний, который является единственной позицией, в которой может произойти операция push, и нижний, который является единственной позицией, в которой может произойти операция pop. Очередь может быть реализована как циклические буферы и связанные списки , или с использованием как указателя стека , так и указателя базы.
Очереди предоставляют услуги в области компьютерных наук , транспорта и исследования операций , где различные сущности, такие как данные, объекты, лица или события, хранятся и удерживаются для последующей обработки. В этих контекстах очередь выполняет функцию буфера . Другое применение очередей — реализация поиска в ширину .
Теоретически, одной из характеристик очереди является то, что она не имеет определенной емкости. Независимо от того, сколько элементов уже содержится, новый элемент всегда может быть добавлен. Она также может быть пустой, и в этом случае удаление элемента будет невозможно, пока новый элемент не будет добавлен снова.
Массивы фиксированной длины ограничены по емкости, но неверно, что элементы нужно копировать в начало очереди. Простой трюк с превращением массива в замкнутый круг и бесконечным перемещением головы и хвоста по этому кругу делает ненужным когда-либо перемещать элементы, хранящиеся в массиве. Если n — размер массива, то вычисление индексов по модулю n превратит массив в круг. Это по-прежнему концептуально самый простой способ построения очереди на языке высокого уровня , но, по общему признанию, он немного замедляет работу, поскольку индексы массива должны сравниваться с нулем и размером массива, что сопоставимо со временем, необходимым для проверки того, находится ли индекс массива за пределами, что делают некоторые языки, но это, безусловно, будет методом выбора для быстрой и грязной реализации или для любого языка высокого уровня, в котором нет синтаксиса указателей. Размер массива должен быть объявлен заранее, но некоторые реализации просто удваивают объявленный размер массива, когда происходит переполнение. Большинство современных языков с объектами или указателями могут реализовывать или поставляться с библиотеками для динамических списков. Такие структуры данных могут не указывать фиксированный предел емкости помимо ограничений памяти. Переполнение очереди происходит при попытке добавить элемент в полную очередь, а недополнение очереди происходит при попытке удалить элемент из пустой очереди.
Ограниченная очередь — это очередь, ограниченная фиксированным числом элементов. [1]
Существует несколько эффективных реализаций очередей FIFO. Эффективная реализация — это та, которая может выполнять операции — постановку в очередь и снятие с очереди — за время 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 :
класс Очередь { конструктор () { этот . элементы = []; } поставить в очередь ( элемент ) { this.items.push ( элемент ) ; } dequeue () { вернуть это . элементы . сдвиг (); } } Очереди также могут быть реализованы как чисто функциональная структура данных . [3] Существует две реализации. Первая из них достигает только на операцию в среднем . То есть, амортизированное время равно , но отдельные операции могут занять где n — количество элементов в очереди. Вторая реализация называется очередью реального времени [4] и позволяет очереди быть постоянной с операциями за время O(1) в худшем случае. Это более сложная реализация и требует ленивых списков с мемоизацией .
Данные этой очереди хранятся в двух односвязных списках с именами и . Список содержит переднюю часть очереди. Список содержит оставшиеся элементы (т. е. заднюю часть очереди) в обратном порядке . Его легко вставить в начало очереди, добавив узел в начало . И, если не пуст, его легко удалить из конца очереди, удалив узел в начале . Когда пуст, список переворачивается и присваивается , а затем голова удаляется.
Вставка («enqueue») всегда занимает время. Удаление («dequeue») занимает , когда список не пуст. Когда пуст, обратный процесс занимает , где — количество элементов в . Но можно сказать, что это амортизированное время, поскольку каждый элемент в должен был быть вставлен, и мы можем назначить постоянную стоимость для каждого элемента в обратном процессе, когда он был вставлен.
Очередь в реальном времени достигает времени для всех операций, без амортизации. Это обсуждение будет техническим, поэтому напомним, что для списка обозначает его длину, что NIL представляет пустой список и представляет список, голова которого h , а хвост t .
Структура данных, используемая для реализации наших очередей, состоит из трех односвязных списков , где f — начало очереди, а r — конец очереди в обратном порядке. Инвариант структуры заключается в том, что s — конец f без его первых элементов, то есть . Тогда хвост очереди почти и вставка элемента x в почти . Говорится почти, потому что в обоих этих результатах . Затем должна быть вызвана вспомогательная функция для удовлетворения инварианта. Необходимо рассмотреть два случая в зависимости от того, является ли список пустым, в этом случае , или нет. Формальное определение таково и где f следует за r в обратном порядке.
Давайте назовем функцию, которая возвращает f, за которой следует r, обращенной. Кроме того, предположим, что , поскольку это тот случай, когда эта функция вызывается. Точнее, мы определяем ленивую функцию , которая принимает в качестве входных данных три списка, такие что , и возвращает конкатенацию f , r обращенной и a . Тогда . Индуктивное определение поворота равно и . Его время выполнения равно , но, поскольку используется ленивая оценка, вычисление задерживается до тех пор, пока результаты не будут принудительно получены вычислением.
Список s в структуре данных имеет две цели. Этот список служит счетчиком для , действительно, если и только если s является пустым списком. Этот счетчик позволяет нам гарантировать, что задний список никогда не будет длиннее переднего списка. Более того, использование s , который является хвостом f , заставляет вычислять часть (ленивого) списка f во время каждой операции хвоста и вставки . Поэтому, когда , список f полностью принудительно выполняется. Если бы это было не так, внутреннее представление f могло бы быть некоторым добавлением добавления... добавления, и принудительное выполнение больше не было бы операцией постоянного времени.
В этой статье использованы материалы, находящиеся в открытом доступе, от Пола Э. Блэка. "Ограниченная очередь". Словарь алгоритмов и структур данных . NIST .
