Очередь — различия между версиями
Adel (обсуждение | вклад) (→size) |
м (rollbackEdits.php mass rollback) |
||
(не показано 19 промежуточных версий 7 участников) | |||
Строка 1: | Строка 1: | ||
== Определение == | == Определение == | ||
[[Файл: Fifo_new.png|right|150px]] | [[Файл: Fifo_new.png|right|150px]] | ||
− | '''Очередь''' (англ. ''queue'') {{---}} это структура данных, добавление и удаление элементов в которой происходит путём операций <tex> \ | + | '''Очередь''' (англ. ''queue'') {{---}} это структура данных, добавление и удаление элементов в которой происходит путём операций <tex> \mathtt{push} </tex> и <tex> \mathtt{pop} </tex> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. ''first-in, first-out {{---}} FIFO''). У очереди имеется '''голова''' (англ. ''head'') и '''хвост''' (англ. ''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове. Очередь поддерживает следующие операции: |
− | * <tex> \ | + | * <tex> \mathtt{empty} </tex> {{---}} проверка очереди на наличие в ней элементов, |
− | * <tex> \ | + | * <tex> \mathtt {push} </tex> (запись в очередь) {{---}} операция вставки нового элемента, |
− | * <tex> \ | + | * <tex> \mathtt{pop} </tex> (снятие с очереди) {{---}} операция удаления нового элемента, |
− | * <tex> \ | + | * <tex> \mathtt{size} </tex> {{---}} операция получения количества элементов в очереди. |
== Реализация циклической очереди на массиве == | == Реализация циклической очереди на массиве == | ||
− | Очередь, способную вместить не более <tex>n</tex> элементов, можно реализовать с помощью массива <tex>elements[0 | + | Очередь, способную вместить не более <tex>\mathtt{n}</tex> элементов, можно реализовать с помощью массива <tex>\mathtt{elements[0\dots n-1]}</tex>. Она будет обладать следующими полями: |
− | * <tex>head</tex> {{---}} голова очереди | + | * <tex>\mathtt{head}</tex> {{---}} голова очереди, |
− | * <tex>tail</tex> {{---}} хвост очереди | + | * <tex>\mathtt{tail}</tex> {{---}} хвост очереди. |
=== empty === | === empty === | ||
Строка 18: | Строка 18: | ||
=== push === | === push === | ||
'''function''' push(x : '''T'''): | '''function''' push(x : '''T'''): | ||
− | elements[tail] = x | + | '''if''' (size() != n) |
− | + | elements[tail] = x | |
+ | tail = (tail + 1) % n | ||
=== pop === | === pop === | ||
'''T''' pop(): | '''T''' pop(): | ||
+ | '''if''' (empty()) | ||
+ | '''return null''' | ||
x = elements[head] | x = elements[head] | ||
head = (head + 1) % n | head = (head + 1) % n | ||
Строка 28: | Строка 31: | ||
=== size === | === size === | ||
− | '''int''' size( | + | '''int''' size() |
'''if''' head > tail | '''if''' head > tail | ||
'''return''' n - head + tail | '''return''' n - head + tail | ||
'''else''' | '''else''' | ||
'''return''' tail - head | '''return''' tail - head | ||
− | Из-за того что нам не нужно | + | Из-за того что нам не нужно снова выделять память, каждая операция выполняется за <tex>O(1)</tex> времени. |
'''Плюсы:''' | '''Плюсы:''' | ||
− | * | + | * проста в разработке, |
− | * | + | * по сравнению с реализацией на списке есть незначительная экономия памяти. |
'''Минусы:''' | '''Минусы:''' | ||
− | * | + | * количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива), |
− | * | + | * при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив. |
== Реализация на списке == | == Реализация на списке == | ||
Строка 47: | Строка 50: | ||
Реализация очереди на односвязном списке: | Реализация очереди на односвязном списке: | ||
=== List === | === List === | ||
− | * <code>ListItem(data : '''T''', next : '''ListItem''')</code> {{---}} конструктор | + | * <code>ListItem(data : '''T''', next : '''ListItem''')</code> {{---}} конструктор, |
− | * <tex>x.value</tex> {{---}} поле, в котором хранится значение элемента | + | * <tex>\mathtt{x.value}</tex> {{---}} поле, в котором хранится значение элемента, |
− | * <tex>x.next</tex> {{---}} указатель на следующий элемент очереди | + | * <tex>\mathtt{x.next}</tex> {{---}} указатель на следующий элемент очереди. |
=== push === | === push === | ||
Строка 74: | Строка 77: | ||
'''Плюсы:''' | '''Плюсы:''' | ||
− | * | + | * каждая операция выполняется за время <tex>O(1)</tex>. |
'''Минусы:''' | '''Минусы:''' | ||
− | * | + | * память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве. |
== Реализация на двух стеках == | == Реализация на двух стеках == | ||
− | Очередь можно реализовать на двух [[Стек|стеках]] <tex>leftStack</tex> и <tex>rightStack</tex>. | + | Очередь можно реализовать на двух [[Стек|стеках]] <tex>\mathtt{leftStack}</tex> и <tex>\mathtt{rightStack}</tex>. Поступим следующим образом: <tex>\mathtt{leftStack}</tex> будем использовать для операции <tex> \mathtt {push} </tex>, <tex>\mathtt{rightStack}</tex> для операции <tex> \mathtt{pop} </tex>. При этом, если при попытке извлечения элемента из <tex>\mathtt{rightStack}</tex> он оказался пустым, просто перенесем все элементы из <tex>\mathtt{leftStack}</tex> в него (при этом элементы в <tex>\mathtt{rightStack}</tex> получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а <tex>\mathtt{leftStack}</tex> станет пустым). |
− | * <tex> \ | + | * <tex> \mathtt{pushLeft} </tex> и <tex> \mathtt{pushRight} </tex> {{---}} функции, реализующие операцию <tex> \mathtt{push} </tex> для соответствующего стека, |
− | * <tex> \ | + | * <tex> \mathtt{popLeft} </tex> и <tex> \mathtt{popRight} </tex> {{---}} аналогично операции <tex> \mathtt {pop} </tex>. |
=== push === | === push === | ||
Строка 89: | Строка 92: | ||
=== pop === | === pop === | ||
'''T''' pop(): | '''T''' pop(): | ||
− | '''if''' '''not''' | + | '''if''' '''not''' rightStack.empty() |
'''return''' popRight() | '''return''' popRight() | ||
'''else''' | '''else''' | ||
Строка 96: | Строка 99: | ||
'''return''' popRight() | '''return''' popRight() | ||
− | При выполнении операции <tex> \ | + | При выполнении операции <tex> \mathtt{push} </tex> будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию <tex> \mathtt{pop} </tex> из первого стека, третью во второй стек на финальный <tex> \mathtt{pop} </tex>. Тогда для операций <tex> \mathtt{pop} </tex> учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции <tex> \mathtt{push} </tex>. |
Таким образом, для каждой операции требуется <tex>O(1)</tex> монет, а значит, амортизационная стоимость операций <tex>O(1)</tex>. | Таким образом, для каждой операции требуется <tex>O(1)</tex> монет, а значит, амортизационная стоимость операций <tex>O(1)</tex>. | ||
'''Плюсы:''' | '''Плюсы:''' | ||
− | * | + | * эту реализацию несложно модифицировать для получения минимума в текущей очереди за <tex>O(1)</tex>. |
'''Минусы:''' | '''Минусы:''' | ||
− | * | + | * если <tex>\mathtt{leftStack}</tex> не пуст, то операция <tex> \mathtt{pop} </tex> может выполняться <tex>O(n)</tex> времени, в отличие от других реализаций, где <tex> \mathtt{pop} </tex> всегда выполняется за <tex>O(1)</tex>. |
== Реализация на шести стеках == | == Реализация на шести стеках == | ||
Строка 113: | Строка 116: | ||
=== Отличия от других реализаций === | === Отличия от других реализаций === | ||
− | '''Плюсы''' | + | '''Плюсы:''' |
− | * <tex>O(1)</tex> реального времени на операцию | + | * <tex>O(1)</tex> реального времени на операцию, |
− | * | + | * возможность дальнейшего улучшения до [[Персистентная очередь|персистентной очереди]], если использовать [[Персистентный стек|персистентные стеки]]. |
− | '''Минусы''' | + | '''Минусы:''' |
− | * | + | * дольше в среднем выполняются операции, |
− | * | + | * больше расход памяти, |
− | * | + | * большая сложность реализации. |
== См. также == | == См. также == | ||
Строка 126: | Строка 129: | ||
* [[Персистентная очередь]] | * [[Персистентная очередь]] | ||
− | == | + | == Источники информации == |
* [[wikipedia:ru:Очередь_(программирование)|Википедия {{---}} Очередь (программирование)]] | * [[wikipedia:ru:Очередь_(программирование)|Википедия {{---}} Очередь (программирование)]] | ||
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262 | * Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262 |
Текущая версия на 19:21, 4 сентября 2022
Содержание
Определение
Очередь (англ. queue) — это структура данных, добавление и удаление элементов в которой происходит путём операций
и соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. first-in, first-out — FIFO). У очереди имеется голова (англ. head) и хвост (англ. tail). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове. Очередь поддерживает следующие операции:- — проверка очереди на наличие в ней элементов,
- (запись в очередь) — операция вставки нового элемента,
- (снятие с очереди) — операция удаления нового элемента,
- — операция получения количества элементов в очереди.
Реализация циклической очереди на массиве
Очередь, способную вместить не более
элементов, можно реализовать с помощью массива . Она будет обладать следующими полями:- — голова очереди,
- — хвост очереди.
empty
boolean empty(): return head == tail
push
function push(x : T): if (size() != n) elements[tail] = x tail = (tail + 1) % n
pop
T pop(): if (empty()) return null x = elements[head] head = (head + 1) % n return x
size
int size() if head > tail return n - head + tail else return tail - head
Из-за того что нам не нужно снова выделять память, каждая операция выполняется за
времени.Плюсы:
- проста в разработке,
- по сравнению с реализацией на списке есть незначительная экономия памяти.
Минусы:
- количество элементов в очереди ограничено размером массива (исправляется написанием функции расширения массива),
- при переполнении очереди требуется перевыделение памяти и копирование всех элементов в новый массив.
Реализация на списке
Для данной реализации очереди необходимо создать список и операции работы на созданном списке.
Реализация очереди на односвязном списке:
List
-
ListItem(data : T, next : ListItem)
— конструктор, - — поле, в котором хранится значение элемента,
- — указатель на следующий элемент очереди.
push
function push(x : T): element = tail tail = ListItem(x, NULL) if size == 0 head = tail else element.next = tail size++
pop
T pop(): size-- element = head head = head.next return element
empty
boolean empty(): return head == tail
Плюсы:
- каждая операция выполняется за время .
Минусы:
- память фрагментируется гораздо сильнее и последовательная итерация по такой очереди может быть ощутимо медленнее, нежели итерация по очереди реализованной на массиве.
Реализация на двух стеках
Очередь можно реализовать на двух стеках и . Поступим следующим образом: будем использовать для операции , для операции . При этом, если при попытке извлечения элемента из он оказался пустым, просто перенесем все элементы из в него (при этом элементы в получатся уже в обратном порядке, что нам и нужно для извлечения элементов, а станет пустым).
- и — функции, реализующие операцию для соответствующего стека,
- и — аналогично операции .
push
function push(x : T): pushLeft(x)
pop
T pop(): if not rightStack.empty() return popRight() else while not leftStack.empty() pushRight(popLeft()) return popRight()
При выполнении операции
будем использовать три монеты: одну для самой операции, вторую в качестве резерва на операцию из первого стека, третью во второй стек на финальный . Тогда для операций учётную стоимость можно принять равной нулю и использовать для операции монеты, оставшиеся после операции .Таким образом, для каждой операции требуется
монет, а значит, амортизационная стоимость операций .Плюсы:
- эту реализацию несложно модифицировать для получения минимума в текущей очереди за .
Минусы:
- если не пуст, то операция может выполняться времени, в отличие от других реализаций, где всегда выполняется за .
Реализация на шести стеках
Одним из минусов реализации на двух стеках является то, что в худшем случае мы тратим
времени на операцию. Если распределить время, необходимое для перемещения элементов из одного стека в другой, по операциям, мы получим очередь без худших случаев с истинного времени на операцию.Подробное описание в статье Персистентная очередь.
Отличия от других реализаций
Плюсы:
- реального времени на операцию,
- возможность дальнейшего улучшения до персистентной очереди, если использовать персистентные стеки.
Минусы:
- дольше в среднем выполняются операции,
- больше расход памяти,
- большая сложность реализации.
См. также
Источники информации
- Википедия — Очередь (программирование)
- Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10.1, стр. 262
- T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1, p. 262
- Hood R., Melville R. Real Time Queue Operations in Pure LISP. — Cornell University, 1980