338
правок
Изменения
Нет описания правки
return size == 0
Каждая операция выполняется в течение времени <tex>O(1)</tex>.
'''Плюсы:'''
:- прост в разработке
:- по сравнению с реализацией на списке, есть незначительная экономия памяти
'''Минусы:'''
:- количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива)
:- при его переполнении требуется перевыделение памяти и копирование всех элементов в новый массив
== Реализация на списке ==
Для реализации очереди на списке этого необходимо создать список (<tex>list</tex>) и операции работы очереди на созданном списке. Добавление новых элементов будет происходить посредством операции <tex>push</tex>, чтобы изъять элемент из очереди будем использовать <tex>pop</tex>, для проверки очереди на наличие в ней элементов используем <tex>empty</tex>.
Реализация очереди на односвязном списке:
=== list ===
* <tex>x.value</tex> - поле, в котором хранится значение элемента
* <tex>x.next</tex> - указатель на следующий элемент очереди
=== push ===
push(x)
el = tail
tail.value = x
tail.next = null
if (size == 0)
then head = tail
else el.next = tail
size++
=== pop ===
pop()
if (!empty())
then x = head.value
head = head.next
size--
return x
=== empty ===
empty()
return size == 0
== См. также ==
== Ссылки ==
* [http://ru.wikipedia.org/wiki/Очередь_(программирование)Очередь]
