Материал: 7 - Презентация - Дженерики, Абстрактные типы данных, Стек, Очередь
Центрдистанционногообучения
Реализация очереди на основе связанного списка (2/3)
public void enqueue(E elem) {
Node<E> node = new Node<E>(); node.setElement(elem);
node.setNext(null); //узел,которыйбудетновым хвостом
if (size == 0) head = node; //специальный случайпустаяочередь
else tail.setNext(node); // добавляемузел
хвостсписка
tail = node; //обновляемссылкунахвостовой узел
size++;
}
51 online.mirea.ru
Реализация очереди на основеЦентрдистанционногообучения
связанного списка (3/3)
public E dequeue() throws EmptyQueueException
{
if (size == 0) throw new EmptyQueueException("Queue is empty.");
E tmp = head.getElement(); head = head.getNext();
size--; // очередьсейчаспуста
if (size == 0) tail = null; return tmp;
}
online.mirea.ru
Центрдистанционногообучения
Применение1: Диспетчеризация Round Robin (в ОС модуль ядра диспетчер)
• |
Мы можем реализовать диспетчер Round Robin с |
||||||||||||||||||||||||||||||
|
использованием очереди Q, путем многократного выполнения |
||||||||||||||||||||||||||||||
|
следующих этапов: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
1. |
e = Q.dequeue() |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
2. |
обслуживание элемента очереди e |
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
3. |
Q.enqueue(e) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
Queue - очередь |
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Обслуживание |
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
Удалить |
|
|
|||||||||||||||
|
|
1 |
|
Поместить в |
|
2 |
. |
. |
|
|
|||||||||||||||||||||
|
|
|
|
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
Следующего элемента |
|
|
Обслуженный |
|
||||||||||||||||
|
|
|
|
Следующий |
|
|
|
|
|||||||||||||||||||||||
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
элемент |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
элемент |
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
Разделяемый |
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Сервис |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
53 online.mirea.ru |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Центрдистанционногообучения
Задача Иосифа Флавия или Джозефуса
Известная математическая задача с историческим подтекстом. Задача основана на легенде, что отряд Иосифа Флавия, защищавший город Йодфат, не пожелал сдаваться в плен блокировавшим пещеру превосходящими силам римлян.
Воины, в составе сорока человек, стали по кругу и договорились, что каждые два воина будут убивать третьего, пока не погибнут все. При этом двое
воинов, оставшихся последними в живых, должны были убить друг друга.
Иосиф Флавий, командовавший этим отрядом, якобы быстро рассчитал, где нужно встать ему и его товарищу, чтобы остаться
последними, но не для того, чтобы убить друг друга, а чтобы сдать
крепость римлянам (Википедия) https://ru.wikipedia.org/wiki/Иосиф_Флавий
54 online.mirea.ru
Центрдистанционногообучения
Задача Иосифа Флавия или Джозефуса
В современной формулировке задачи участвует n воинов, стоящих по кругу, и убивают каждого m-го. Требуется определить номер k
начальной позиции воина, который останется последним.
55 online.mirea.ru