Редактирование: Очередь
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
== Определение == | == Определение == | ||
[[Файл: Fifo_new.png|right|150px]] | [[Файл: 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> - проверка очереди на наличие в ней элементов |
− | * < | ||
− | == Реализация | + | == Реализация на массиве == |
− | Очередь, способную вместить не более <tex> | + | Очередь, способную вместить не более <tex>n</tex> элементов, можно реализовать с помощью массива <tex>elements[1..n]</tex>. Она будет обладать следующими полями: |
− | * <tex> | + | * <tex>head</tex> (голова очереди) |
− | * <tex> | + | * <tex>tail</tex> (хвост очереди) |
− | + | * <tex>size</tex> (размер очереди) | |
− | |||
− | |||
− | |||
=== push === | === push === | ||
− | '''function''' push(x | + | '''function''' push(x): |
− | + | elements[tail] = x | |
− | + | tail = (tail + 1) % elements.length | |
− | + | size++ | |
=== pop === | === pop === | ||
− | ''' | + | '''function''' pop(): |
− | '''if''' | + | '''if''' !empty() |
− | + | x = elements[head] | |
− | + | head = (head + 1) % elements.length | |
− | + | size-- | |
− | + | '''return''' x | |
− | === | + | === empty === |
− | ''' | + | '''function''' empty(): |
− | + | '''return''' size == 0 | |
− | + | Из-за того что нам не нужно перевыделять память, каждая операция выполняется за <tex>O(1)</tex> времени. | |
− | |||
− | |||
− | Из-за того что нам не нужно | ||
'''Плюсы:''' | '''Плюсы:''' | ||
− | * | + | * прост в разработке |
− | * по сравнению с реализацией на списке есть незначительная экономия памяти | + | * по сравнению с реализацией на списке, есть незначительная экономия памяти |
'''Минусы:''' | '''Минусы:''' | ||
− | * количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива) | + | * количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива) |
− | * при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив | + | * при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив |
== Реализация на списке == | == Реализация на списке == | ||
− | Для данной реализации очереди необходимо создать | + | Для данной реализации очереди необходимо создать список (<tex>list</tex>) и операции работы на созданном списке. |
Реализация очереди на односвязном списке: | Реализация очереди на односвязном списке: | ||
− | === | + | === list === |
− | + | * <tex>x.value</tex> - поле, в котором хранится значение элемента | |
− | * <tex> | + | * <tex>x.next</tex> - указатель на следующий элемент очереди |
− | * <tex> | ||
=== push === | === push === | ||
− | '''function''' push(x | + | '''function''' push(x): |
element = tail | element = tail | ||
− | tail = | + | tail = new list(x, NULL) |
'''if''' size == 0 | '''if''' size == 0 | ||
head = tail | head = tail | ||
Строка 65: | Строка 57: | ||
=== pop === | === pop === | ||
− | ''' | + | '''function''' pop(): |
− | + | '''if''' empty() | |
+ | '''return''' | ||
element = head | element = head | ||
head = head.next | head = head.next | ||
+ | size-- | ||
'''return''' element | '''return''' element | ||
=== empty === | === empty === | ||
− | ''' | + | '''function''' empty(): |
− | '''return''' | + | '''return''' size == 0 |
[[Файл: Queue.png|right|230px]] | [[Файл: Queue.png|right|230px]] | ||
+ | Каждая операция выполняется за время <tex>O(1)</tex>. | ||
− | |||
− | |||
'''Минусы:''' | '''Минусы:''' | ||
− | * | + | * Память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве |
== Реализация на двух стеках == | == Реализация на двух стеках == | ||
− | Очередь можно реализовать на двух [[Стек|стеках]] <tex> | + | Очередь можно реализовать на двух [[Стек|стеках]] <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 === | === push === | ||
− | '''function''' push(x | + | '''function''' push(x): |
pushLeft(x) | pushLeft(x) | ||
=== pop === | === pop === | ||
− | ''' | + | '''function''' pop(): |
− | '''if''' | + | '''if''' !rigthStack.empty() |
'''return''' popRight() | '''return''' popRight() | ||
'''else''' | '''else''' | ||
− | '''while''' | + | '''while''' !leftStack.empty() |
pushRight(popLeft()) | pushRight(popLeft()) | ||
'''return''' popRight() | '''return''' popRight() | ||
− | При выполнении операции < | + | При выполнении операции <math> \mathrm {push} </math> будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию <math> \mathrm {pop} </math> из первого стека, третью во второй стек на финальный <math> \mathrm {pop} </math>. Тогда для операций <math> \mathrm {pop} </math> учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции <math> \mathrm {push} </math>. |
Таким образом, для каждой операции требуется <tex>O(1)</tex> монет, а значит, амортизационная стоимость операций <tex>O(1)</tex>. | Таким образом, для каждой операции требуется <tex>O(1)</tex> монет, а значит, амортизационная стоимость операций <tex>O(1)</tex>. | ||
− | |||
− | |||
'''Минусы:''' | '''Минусы:''' | ||
− | * | + | * Если <tex>leftStack</tex> не пуст, то операция <math> \mathrm {pop} </math> может выполняться <tex>O(n)</tex> времени, в отличии от других реализаций, где <math> \mathrm {pop} </math> всегда выполняется за <tex>O(1)</tex> |
== Реализация на шести стеках == | == Реализация на шести стеках == | ||
Строка 116: | Строка 107: | ||
=== Отличия от других реализаций === | === Отличия от других реализаций === | ||
− | '''Плюсы | + | '''Плюсы''': |
− | * <tex>O(1)</tex> реального времени на операцию | + | * <tex>O(1)</tex> реального времени на операцию. |
− | * | + | * Возможность дальнейшего улучшения до [[Персистентная очередь|персистентной очереди]], если использовать [[Персистентный стек|персистентные стеки]]. |
− | '''Минусы | + | '''Минусы''': |
− | * | + | * Дольше в среднем выполняются операции. |
− | * | + | * Больше расход памяти. |
− | * | + | * Большая сложность реализации. |
== См. также == | == См. также == | ||
Строка 129: | Строка 120: | ||
* [[Персистентная очередь]] | * [[Персистентная очередь]] | ||
− | == | + | == Ссылки == |
* [[wikipedia:ru:Очередь_(программирование)|Википедия {{---}} Очередь (программирование)]] | * [[wikipedia:ru:Очередь_(программирование)|Википедия {{---}} Очередь (программирование)]] | ||
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262 | * Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262 |