Изменения

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

Очередь, способную вместить не более <tex>n</tex> элементов, можно реализовать с помощью массива <tex>\mathrmmathtt{elements[0\dots n-1]}</tex>. Она будет обладать следующими полями:* <tex>\mathrmmathtt{head}</tex> {{---}} голова очереди* <tex>\mathrmmathtt{tail}</tex> {{---}} хвост очереди

* <tex>\mathrmmathtt{x.value}</tex> {{---}} поле, в котором хранится значение элемента* <tex>\mathrmmathtt{x.next}</tex> {{---}} указатель на следующий элемент очереди

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

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

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

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