Материал: 7 - Презентация - Дженерики, Абстрактные типы данных, Стек, Очередь
Центрдистанционногообучения
Очереди
41
online.mirea.ru
Центрдистанционногообучения
АТД Очередь
•АТД Очередь (Queue) хранит произвольные объекты
•Вставки и удаления происходят после по очереди вслед за первым, по схеме FIFO ( First inFirst out)
•Элементы вставляются в конец очереди, а удаляются сначала
•Основные операции над очередью:
•enqueue(object): вставка элемента в конец очереди
•object dequeue(): удаляем и возвращаем элемент в передней части очереди, т. е,. с ее начала
•Вспомогательные операции для очереди:
•object front(): возвращает
начальный элемент, не удаляя его
•integer size():возвращает
количество элементов в очереди
•boolean isEmpty(): пуста ли очередь?
•Исключения
•попытка выполнения
операции dequeue() на пустой очереди выбрасывает
EmptyQueueException
42 online.mirea.ru
Центрдистанционногообучения
Пример работы очереди
Operation |
|
Output |
Q |
|
|
enqueue(5) |
– |
(5) |
|
|
|
enqueue(3) |
– |
(5, 3) |
|
|
|
dequeue() |
5 |
(3) |
|
|
|
enqueue(7) |
– |
(3, 7) |
|
|
|
dequeue() |
3 |
(7) |
|
|
|
front() |
7 |
(7) |
|
|
|
dequeue() |
7 |
() |
|
|
|
dequeue() |
“error” |
() |
|
|
|
isEmpty() |
true |
() |
|
|
|
enqueue(9) |
– |
(9) |
|
|
|
enqueue(7) |
– |
(9, 7) |
|
|
|
size() |
2 |
(9, 7) |
|
|
|
enqueue(3) |
– |
(9, 7, 3) |
|
|
|
enqueue(5) |
– |
(9, 7, 3, |
5) |
43 |
online.mirea.ru |
dequeue() |
9 |
(7, 3, 5) |
|
||
|
|
|
Центрдистанционногообучения
Применение очередей
•Непосредственное применение
•Листы ожидания, бюрократические процедуры
•Доступ к разделяемым ресурсам (например, принтер)
•Мультипрограммирование
•Косвенное применение
•Вспомогательная структура данных для алгоритмов
•Как компонент других структур данных
44 online.mirea.ru
Центрдистанционногообучения
Очередь на основе массива
•Используем массив размера N по кругу
•Две переменные отслеживают начало и конец очереди
f |
индекс начала |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
r |
индекс последнего элемента |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
Далее индекса r массив пустой |
|
|||||||||||||||||||||||||||||||||||
• нормальная конфигурация |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
Q |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 1 2 |
|
|
f |
|
|
|
|
|
|
|
|
r |
|
|||||||||||||||||||||
|
|
|
|
Развернутая конфигурация |
|
|||||||||||||||||||||||||||||||
|
Q |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
0 |
1 2 |
|
|
r |
|
|
|
f |
|
|||||||||||||||||||||||||
45 online.mirea.ru