338
правок
Изменения
м
Операция вставки нового элемента называется <tex>push</tex> (запись в очередь), а операция удаления - <tex>pop</tex> (снятие с очереди), <tex>empty</tex> - проверка очереди на наличие в ней элементов. Очередь, способную вместить не более <tex>n</tex> элементов, можно реализовать с помощью массива <tex>elements[1..n]</tex>. Очередь Она будет обладать следующими полями:
Нет описания правки
== Определение ==
[[Файл: Fifo_new.png|thumb|right|150px|Очердь]]
'''Очередь''' (''Queue'') — это динамическое множество, добавление и удаление элементов в котором происходит путём операций ''Push'' и ''Pop'' соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (''first-in, first-out — FIFO''). Очередь подобна, например, живой очередь в магазине за хлебом. У нее имеется '''голова''' (''head'') и '''хвост''' (''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте, точно так же, как человек занимает очередь последним, чтобы купить хлеб. Из очереди всегда выводится элемент, который находится в её головной части аналогично тому, как человек, который ждал дольше всех, расплачивается за хлеб.
*<tex>push</tex> (запись в очередь) - операция вставки нового элемента.
*<tex>pop</tex> (снятие с очереди) - операция удаления нового элемента.
*<tex>empty</tex> - проверка очереди на наличие в ней элементов
== Реализация на массиве ==
:<tex>head</tex> (голова очереди)
:<tex>tail</tex> (хвост очереди)
== Реализация на списке ==
Для данной реализации очереди необходимо создать список (<tex>list</tex>) и операции работы на созданном списке. Добавление новых элементов будет происходить посредством операции <tex>push</tex>, чтобы изъять элемент из очереди будем использовать <tex>pop</tex>, для проверки очереди на наличие в ней элементов используем <tex>empty</tex>.
Реализация очереди на односвязном списке:
'''Минусы:'''
*память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве
== Реализация на двух стеках ==
[[Файл: Queue.png|thumb|right|250px]]
== См. также ==
