143
правки
Изменения
Нет описания правки
== Определение ==
[[Файл: Fifo_new.png|right|150px]]
'''Очередь''' (англ. ''queue'') {{---}} это структура данных, добавление и удаление элементов в которой происходит путём операций <tex> \mathrm {push} </tex> и <tex> \mathrm {pop} </tex> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. ''first-in, first-out {{---}} FIFO''). У очереди имеется '''голова''' (англ. ''head'') и '''хвост''' (англ''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове.
* <tex> \mathrm {empty} </tex> {{---}} проверка очереди на наличие в ней элементов
* <tex> \mathrm {push} </tex> (запись в очередь) {{---}} операция вставки нового элемента.
== Реализация циклической очереди на массиве ==
Очередь, способную вместить не более <tex>n</tex> элементов, можно реализовать с помощью массива <tex>\mathrm{elements[0..\dots n-1]}</tex>. Она будет обладать следующими полями:* <tex>\mathrm{head}</tex> {{---}} голова очереди* <tex>\mathrm{tail}</tex> {{---}} хвост очереди
=== empty ===
=== List ===
* <code>ListItem(data : '''T''', next : '''ListItem''')</code> {{---}} конструктор
* <tex>\mathrm{x.value}</tex> {{---}} поле, в котором хранится значение элемента* <tex>\mathrm{x.next}</tex> {{---}} указатель на следующий элемент очереди
=== push ===
== Реализация на двух стеках ==
Очередь можно реализовать на двух [[Стек|стеках]] <tex>\mathrm{leftStack}</tex> и <tex>\mathrm{rightStack}</tex>. Один из стеков <tex>(\mathrm{leftStack)}</tex> будем использовать для операции <tex> \mathrm {push} </tex>, другой <tex>\mathrm{rightStack}</tex> для операции <tex> \mathrm {pop} </tex>. При этом, если при попытке извлечения элемента из <tex>\mathrm{rightStack}</tex> он оказался пустым, просто перенесем все элементы из <tex>\mathrm{leftStack}</tex> в него (при этом элементы в <tex>rightStack</tex> получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а <tex>\mathrm{leftStack}</tex> станет пустым).
* <tex> \mathrm {pushLeft} </tex> и <tex> \mathrm {pushRight} </tex> {{---}} функции, реализующие операцию <tex> \mathrm {push} </tex> для соответствующего стека;
* Эту реализацию несложно модифицировать для получения минимума в текущей очереди за <tex>O(1)</tex>.
'''Минусы:'''
* Если <tex>\mathrm{leftStack}</tex> не пуст, то операция <tex> \mathrm {pop} </tex> может выполняться <tex>O(n)</tex> времени, в отличии от других реализаций, где <tex> \mathrm {pop} </tex> всегда выполняется за <tex>O(1)</tex>.
== Реализация на шести стеках ==
* [[Персистентная очередь]]
== Ссылки Источники информации ==
* [[wikipedia:ru:Очередь_(программирование)|Википедия {{---}} Очередь (программирование)]]
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262
