Материал: 7 - Презентация - Дженерики, Абстрактные типы данных, Стек, Очередь
Центрдистанционногообучения
Операции над очередью (1/3)
• Мы используем |
Algorithm size() |
|
{ return (N - f + r) mod N;} |
||
оператор деления по |
||
|
||
модулю (остаток от |
Algorithm isEmpty() |
|
целочисленного |
||
деления) |
{ return (f = r); } |
|
|
|
Q
0 1 2 |
f |
r |
Q
0 1 2 |
r |
f |
46 online.mirea.ru
Центрдистанционногообучения
Операции над очередью (2/3)
•Операция включения в очередь генерирут исключение, если очередь заполнена, то есть массив полон
•Это исключение зависит от конкретной реализации
Algorithm enqueue(o) { if ( size() = N - 1)
throw FullQueueException; else
{ Q[r] = o;
r = (r + 1) mod N ;
}
}
Q
0 1 2 |
f |
r |
Q
0 1 2 |
r |
f |
47 online.mirea.ru
Центрдистанционногообучения
Операции над очередью (3/3)
•Операция исключения из очереди генерирует исключение, если очередь пуста
•Это исключение указывается в AТД очереди
Algorithm dequeue() { if ( isEmpty() )
throw EmptyQueueException else
{ o = Q[f];
f = (f + 1) mod N; return o;
}
}
Q
0 1 2 |
f |
r |
Q
0 1 2 |
r |
f |
48 online.mirea.ru
Центрдистанционногообучения
Интерфейс очереди в Java
•В Java есть Интерфейс,
соответствующий АТД нашей очереди
•Требуется определение класса
•EmptyQueueException
•Нет соответствующего встроенного класса Java
public interface Queue {
public int size();
public boolean isEmpty();
public Object front() throws
EmptyQueueException;
public void enqueue(Object o);
public Object dequeue() throws
EmptyQueueException;
}
49 online.mirea.ru
Центрдистанционногообучения
Реализация очереди на основе связанного списка (1/3)
•Для реализации очереди используется обобщенный односвязнный список.
•Передняя часть очереди является заглавным звеном связанного списка и задняя часть очереди это хвост связанного списка
•В классе очереди необходимо поддерживать ссылки как для заглавных, так и хвостовых узлов в списке.
•каждый метод на АТД очереди на основе односвязной реализации списка работает O (1) время.
•Два метода, называемых dequeue() and enqueue(), реализваны на следующем слайде.
50 online.mirea.ru