Изменения

'''Очередь''' (англ. ''queue'')  {{---}} это структура данных, добавление и удаление элементов в которой происходит путём операций <mathtex> \mathrm {push} </mathtex> и <mathtex> \mathrm {pop} </mathtex> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (''first-in, first-out {{---}} FIFO''). У очереди имеется '''голова''' (''head'') и '''хвост''' (''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове.*<mathtex> \mathrm {push} </mathtex> (запись в очередь) {{---}} операция вставки нового элемента.*<mathtex> \mathrm {pop} </mathtex> (снятие с очереди) {{---}} операция удаления нового элемента.*<mathtex> \mathrm {empty} </mathtex> {{---}} проверка очереди на наличие в ней элементов

Очередь можно реализовать на двух [[Стек|стеках]] <tex>leftStack</tex> и <tex>rightStack</tex>. Один из стеков <tex>(leftStack)</tex> будем использовать для операции <mathtex> \mathrm {push} </mathtex>, другой для операции <mathtex> \mathrm {pop} </mathtex>. При этом, если при попытке извлечения элемента из <tex>rightStack</tex> он оказался пустым, просто перенесем все элементы из <tex>leftStack</tex> в него (при этом элементы в <tex>rightStack</tex> получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а <tex>leftStack</tex> станет пустым).

* <mathtex> \mathrm {pushLeft} </mathtex> и <mathtex> \mathrm {pushRight} </mathtex> {{---}} функции, реализующие операцию <tex>\mathrm {push} </tex> для соответствующего стека; * <mathtex> \mathrm {popLeft} </mathtex> и <mathtex> \mathrm {popRight} </mathtex> {{---}} аналогично операции <mathtex> \mathrm {pop} </mathtex>.

При выполнении операции <mathtex> \mathrm {push} </mathtex> будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию <mathtex> \mathrm {pop} </mathtex> из первого стека, третью во второй стек на финальный <mathtex> \mathrm {pop} </mathtex>. Тогда для операций <mathtex> \mathrm {pop} </mathtex> учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции <mathtex> \mathrm {push} </mathtex>.

* Если <tex>leftStack</tex> не пуст, то операция <mathtex> \mathrm {pop} </mathtex> может выполняться <tex>O(n)</tex> времени, в отличии от других реализаций, где <mathtex> \mathrm {pop} </mathtex> всегда выполняется за <tex>O(1)</tex>