Обсуждение:Очередь

2012-03-14T14:07:10Z

178.178.29.65:

{{tick|ticked=1}} Добавить реализацию на двух стеках.
:Если уж добавлять, то нужно оформить, как и остальные реализации (к примеру, добавить "операции выполняются за <tex>O(1)</tex>" и плюсы/минусы).
:Хм. А почему медленнее-то? Не понятно.
:И, да, как я понимаю, в реализации на массивах O(1) амортизированное, а не истинное (из-за необходимости перевыделения памяти).
{{tick|ticked=1}} Ну, во-первых. В плюсах и минусах написан какой-то трешак местами. Примеры:
* Плюсы реализации на массиве могут повторяться как минусы реализации на списке, что не есть хорошо, я думаю.
* «размер очереди ограничен лишь объемом памяти» — корявая фраза. Размер очереди у нас в обоих случаях ничем не ограничен.
В общем, советую проверить и то, что неверно, выкинуть.
{{tick|ticked=1}} В минусы реализации на списке нужно добавить тот факт, что в таком варианте память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди на массиве.
{{tick|ticked=1}} Советую вообще дать прочитать этот конспект какому-нибудь хоть чуть-чуть шарящему человеку, дабы вычистить фактические ошибки (FIFO - не стратегия, а принцип) и ошибки согласования («Для реализации очереди на списке этого необходимо создать список»).
{{tick|ticked=1}} Стоит оформить ссылки в соответствии с требованиями ([[Обсуждение:Дискретная_математика_и_алгоритмы#.D0.92.D0.B8.D0.BA.D0.B8.D1.84.D0.B8.D0.BA.D0.B0.D1.86.D0.B8.D1.8F|пункт 9]], [[Обсуждение:Дискретная_математика_и_алгоритмы#.D0.98.D1.81.D1.82.D0.BE.D1.87.D0.BD.D0.B8.D0.BA.D0.B8|требования к оформлению источников]]).
{{tick|ticked=1}} Что такое «динамическое множество»?
{{tick|ticked=1}} В псевдокоде реализации на двух стеках в операции push второй if не нужен.

Очередь

2012-03-14T14:06:29Z

178.178.29.65:

== Определение ==
[[Файл: 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>n</tex> элементов, можно реализовать с помощью массива <tex>elements[1..n]</tex>. Она будет обладать следующими полями:
:<tex>head</tex> (голова очереди)
:<tex>tail</tex> (хвост очереди)
:<tex>size</tex> (размер очереди)

=== push ===
push(x)
elements[tail] = x
tail = (tail + 1) % elements.length
size++
=== pop ===
pop()
if !empty()
then x = elements[head]
head = (head + 1) % elements.length
size--
return x
=== empty ===
empty()
return size == 0
Каждая операция выполняется за амортизированную <tex>O(1)</tex>.

'''Плюсы:'''
:- прост в разработке
:- по сравнению с реализацией на списке, есть незначительная экономия памяти
'''Минусы:'''
:- количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива)
:- при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив

== Реализация на списке ==
Для данной реализации очереди необходимо создать список (<tex>list</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
[[Файл: Queue.png|thumb|right|230px]]
Каждая операция выполняется за время <tex>O(1)</tex>.

'''Минусы:'''
* Память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве

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

=== push ===
push(x)
leftStack.push(x)
=== pop ===
pop()
if rightStack.empty()
then while !leftStack.empty()
do rightStack.push(leftStack.pop)
return rightStack.pop()
Каждая операция выполняется за амортизированную <tex>O(1)</tex>.

'''Минусы:'''
* Много времени тратится на перекладывание элементов из одного стека в другой.

== См. также ==
* [[Стек]]

== Ссылки ==
* [http://ru.wikipedia.org/wiki/Очередь_(программирование) Википедия - Очередь (программирование)]
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262
* T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1, p. 262

[[Категория: Амортизационный анализ]]

Викиконспекты - Вклад участника [ru]

Обсуждение:Очередь

Очередь