Материал: 7

Операция исключения из очереди генерирует исключение, если очередь пуста. Это исключение указывается в AТД очереди.

Algorithm dequeue() { if ( isEmpty() )

throw EmptyQueueException

else

{ o = Q[f];

f = (f + 1) mod N; return o;

}

}

Интерфейс очереди в 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;

}

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

Для реализации очереди используется обобщенный односвязнный список.

Передняя часть очереди является заглавным звеном связанного списка и задняя часть очереди — это хвост связанного списка.

В классе очереди необходимо поддерживать ссылки как для заглавных, так и хвостовых узлов в списке.

каждый метод на АТД очереди на основе односвязной реализации списка работает O (1) время.

Два метода, называемых dequeue() and enqueue(), реализваны на следующем слайде.

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++;

}

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;

}

Применение1: Диспетчеризация Round Robin (в ОС модуль ядра диспетчер)

Мы можем реализовать диспетчер Round Robin с использованием очереди Q, путем многократного выполнения следующих этапов:

1.e = Q.dequeue()

2.обслуживание элемента очереди e

3.Q.enqueue(e)

Задача Иосифа Флавия или Джозефуса

Известная математическая задача с историческим подтекстом.

Задача основана на легенде, что отряд Иосифа Флавия, защищавший город Йодфат, не пожелал сдаваться в плен блокировавшим пещеру превосходящими силам римлян. Воины, в составе сорока человек, стали по кругу и договорились, что каждые два воина будут убивать третьего, пока не погибнут все. При этом двое воинов, оставшихся последними в живых, должны были убить друг друга. Иосиф Флавий, командовавший этим отрядом, якобы быстро рассчитал, где нужно встать ему и его товарищу, чтобы остаться последними, но не для того, чтобы убить друг друга, а чтобы сдать крепость римлянам (Википедия) https://ru.wikipedia.org/wiki/Иосиф_Флавий

В современной формулировке задачи участвует n воинов, стоящих по кругу, и убивают каждого m-го. Требуется определить номер k начальной позиции воина, который останется последним.

Применение: Решение проблемы Джосефуса

Группа детей садятся в кругу и передают друг-другу по-очереди предмет, условно называемый "картошка", по кругу.

Игра в Картошку начинается с какого-то одного ребенка в кругу, а затем все дети продолжают передавать картошку, до тех пор, пока ведущий не позвонит в колокол, в этот момент ребенок, который держит картофель должен покинуть игру, после передачи картофеля к следующему ребенку в кругу.

После того, как проигравший ребенок выходит из круга, дети смыкают круг, и игра повторяется.

Этот процесс затем продолжается до тех пор, пока не останется один - последний ребенок, который будет объявлен победителем.

Если ведущий игры всегда использует следующую стратегию: колокольчик звонит после того, как картофель был принят k раз, то для некоторого фиксированного k, определяющего победителя для данного списка детей известна как проблема Иосифа.

public static <E> E Josephus(Queue<E> Q, int k) { if (Q.isEmpty()) return null;

while (Q.size() > 1) {

System.out.println(" Queue: " + Q + " k = " + k);

//Перемещаемэлементизначалакконцу

for (int i=0; i < k; i++) Q.enqueue(Q.dequeue()); //удаляемначальныйэлементизколлекции

E e = Q.dequeue() ; System.out.println(" " + e + " is out");

}

return Q.dequeue();победитель!//

}

/**Созданиеочередиизмассиваобъектов*/

public static <E> Queue<E> buildQueue(E a[])

{

Queue<E> Q = new NodeQueue<E>();

for (int i=0; i<a.length; i++) Q.enqueue(a[i]); return Q;

}

/** Метод тестер*/

public static void main(String[] args) {

String[] a1 = {"Alice", "Bob", "Cindy", "Doug", "Ed", “Fred"};

String[] a2 = {"Gene", "Hope", "Irene", "Jack", "Kim", "Lance"};

String[] a3 = {"Mike", "Roberto"}; System.out.println("First winner is " +

Josephus(buildQueue(a1), 3)); System.out.println("Second winner is " + Josephus(buildQueue(a2), 10)); System.out.println("Third winner is " + Josephus(buildQueue(a3), 7));

} }

Материал для чтения

1.https://javarush.ru/groups/posts/2321-strukturih-dannihkh--stek-i-

ocheredjh

2.https://habr.com/ru/post/182776/

3.http://ermak.cs.nstu.ru/flp/flp_book/2.8.html

4.http://wp.wiki-wiki.ru/wp/index.php/Задача_Иосифа_Флавия

5.http://neerc.ifmo.ru/wiki/index.php?title=Очередь

6.http://www.k-press.ru/cs/2008/3/generic/generic.asp

7.Структуры данных и алгоритмы в Java, Гудрич М.Т., Тамассия Р. , 2003 (Глава 5)

8. Структуры данных и алгоритмы в Java, Роберт Лафоре

2018

9.https://tproger.ru/articles/computational-complexity-explained/

10.https://habr.com/ru/post/196560/

11.https://proglib.io/p/analysis-of-algorithm/

12.Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.

–М.: Вильямс, 2019.