13
правок
Изменения
м
Поправка грамматики.
== Определение ==
[[Файл: Fifo_new.png|right|150px]]
'''Очередь''' (англ. ''queue'') {{---}} это структура данных, добавление и удаление элементов в которой происходит путём операций <tex> \mathtt{push} </tex> и <tex> \mathtt{pop} </tex> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. ''first-in, first-out {{---}} FIFO''). У очереди имеется '''голова''' (англ. ''head'') и '''хвост''' (англ. ''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове. Очередь поддерживает следующие операции:
* <tex> \mathtt{empty} </tex> {{---}} проверка очереди на наличие в ней элементов,
* <tex> \mathtt {push} </tex> (запись в очередь) {{---}} операция вставки нового элемента,
=== push ===
'''function''' push(x : '''T'''):
'''if''' (size() != n) elements[tail] = x tail = (tail + 1) % n
=== pop ===
'''T''' pop():
'''if''' (empty())
'''return null'''
x = elements[head]
head = (head + 1) % n
=== size ===
'''int''' size(s : '''stack<T>''')
'''if''' head > tail
'''return''' n - head + tail
=== pop ===
'''T''' pop():
'''if''' '''not''' rigthStackrightStack.empty()
'''return''' popRight()
'''else'''
* эту реализацию несложно модифицировать для получения минимума в текущей очереди за <tex>O(1)</tex>.
'''Минусы:'''
* если <tex>\mathtt{leftStack}</tex> не пуст, то операция <tex> \mathtt{pop} </tex> может выполняться <tex>O(n)</tex> времени, в отличии отличие от других реализаций, где <tex> \mathtt{pop} </tex> всегда выполняется за <tex>O(1)</tex>.
== Реализация на шести стеках ==
