Очередь — различия между версиями

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

Версия 00:24, 14 марта 2012

Определение

Fifo new.png

Очередь (Queue)  — это динамическое множество, добавление и удаление элементов в котором происходит путём операций Push и Pop соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (first-in, first-out — FIFO). Очередь подобна, например, живой очередь в магазине за хлебом. У нее имеется голова (head) и хвост (tail). Когда элемент ставится в очередь, он занимает место в её хвосте, точно так же, как человек занимает очередь последним, чтобы купить хлеб. Из очереди всегда выводится элемент, который находится в её головной части аналогично тому, как человек, который ждал дольше всех, расплачивается за хлеб.

  • [math]push[/math] (запись в очередь) - операция вставки нового элемента.
  • [math]pop[/math] (снятие с очереди) - операция удаления нового элемента.
  • [math]empty[/math] - проверка очереди на наличие в ней элементов

Реализация на массиве

Очередь, способную вместить не более [math]n[/math] элементов, можно реализовать с помощью массива [math]elements[1..n][/math]. Она будет обладать следующими полями:

[math]head[/math] (голова очереди)
[math]tail[/math] (хвост очереди)
[math]size[/math] (размер очереди)

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

Каждая операция выполняется в течение времени [math]O(1)[/math].

Плюсы:

- прост в разработке
- по сравнению с реализацией на списке, есть незначительная экономия памяти

Минусы:

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

Реализация на списке

Для данной реализации очереди необходимо создать список ([math]list[/math]) и операции работы на созданном списке.

Реализация очереди на односвязном списке:

list

  • [math]x.value[/math] - поле, в котором хранится значение элемента
  • [math]x.next[/math] - указатель на следующий элемент очереди

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

Каждая операция выполняется в течение времени [math]O(1)[/math].

Минусы:

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

Реализация на двух стеках

Queue.png


См. также


Ссылки