215
правок
Изменения
Нет описания правки
== Определение ==
[[Файл: Fifo_new.png|right|150px]]
'''Очередь''' (''Queue'') — {{---}} это структура данных, добавление и удаление элементов в которой происходит путём операций <math> \mathrm {push} </math> и <math> \mathrm {pop} </math> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (''first-in, first-out — {{---}} FIFO''). У очереди имеется '''голова''' (''head'') и '''хвост''' (''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове.*<math> \mathrm {push} </math> (запись в очередь) {{- --}} операция вставки нового элемента.*<math> \mathrm {pop} </math> (снятие с очереди) {{--- }} операция удаления нового элемента.*<math> \mathrm {empty} </math> {{--- }} проверка очереди на наличие в ней элементов
== Реализация на массиве ==
Реализация очереди на односвязном списке:
=== list ===
* <tex>x.value</tex> {{- --}} поле, в котором хранится значение элемента* <tex>x.next</tex> {{--- }} указатель на следующий элемент очереди
=== push ===
Очередь можно реализовать на двух [[Стек|стеках]] <tex>leftStack</tex> и <tex>rightStack</tex>. Один из стеков <tex>(leftStack)</tex> будем использовать для операции <math> \mathrm {push} </math>, другой для операции <math> \mathrm {pop} </math>. При этом, если при попытке извлечения элемента из <tex>rightStack</tex> он оказался пустым, просто перенесем все элементы из <tex>leftStack</tex> в него (при этом элементы в <tex>rightStack</tex> получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а <tex>leftStack</tex> станет пустым).
* <math> \mathrm {pushLeft} </math> и <math> \mathrm {pushRight} </math> {{--- }} функции, реализующие операцию <tex>push</tex> для соответствующего стека; * <math> \mathrm {popLeft} </math> и <math> \mathrm {popRight} </math> {{--- }} аналогично операции <math> \mathrm {pop} </math>.
=== push ===
