Главная » Java, Структуры данных и алгоритмы » Абстрактный тип данных «очередь»

0

Еще одной базовой структурой данных является очередь. Эта структура данных аналогична стеку, так как очередь объединяет объекты, работа с которыми — добавление и удаление — осуществляется по принципу FIFO (first-in first-out)(«первым пришел — первым ушел»). Добавление объектов в очередь может осуществляться в любое время, однако удаленным может быть лишь объект, который был добавлен первым. Говорят, что элементы добавляются в очередь с конца, а удаляются с начала. Можно сравнить очередь данных с очередью людей в парке аттракционов. Люди встают в очередь с конца, а те, кто был первым в очереди, катаются на аттракционе.

Формально абстрактный тип данных «очередь» представляет собой последовательность объектов, в которой доступ и удаление разрешены только для первого элемента очереди, называемого началом очереди,

а добавление элементов возможно только в конец очереди. Данное правило основано на принципе FIFO (first-in first-out) («первым пришел — первым ушел»).

Стек S является абстрактным типом данных (АТД), который поддерживает два следующих основных метода:

enqueue (0): помещает объект о в конец очереди.

Input: объект; Output: нет.

dequeue (): производит удаление и возвращает объект из начала оче- . реди; если очередь пуста, выдается сообщение об ошибке.

Input: нет; Output: объект.

Кроме того, как и в случае с АТД «стек», АТД «очередь» выполняет следующие дополнительные методы:

size (): возвращает число объектов в очереди. Input: нет; Output: целое число.

isEmpty (): возвращает логическое значение, подтверждающее, что очередь пуста.

Input: нет; Output: логическое значение, front (): возвращает первый объект в очереди, не удаляя его; если очередь пуста, выдается сообщение об ошибке. Input: нет; Output: объект.

Пример 4.4. В данной таблице представлены операции работы с очередями и результаты их выполнения над изначально пустой очередью целочисленных объектов Q. Для простоты в качестве аргументов операций используются целые числа, а не целочисленные объекты.

Операции

Output

начало <- Q <- конец

enqueue(5)

-

(5)

enqueue(3)

-

(5,3)

dequeue()

5

(3)

enqueue(7)

-

(3,7)

dequeue()

3

(7)

front()

7

(7)

dequeue()

7

0

dequeue()

«error»

0

isEmpty()

true

0

enqueue(9)

-

(9)

enqueue(7)

-

(9,7)

size()

2

(9,7)

ОНерации

Output

начало <— Q <— конец

enqueue(3)

 

(9,7,3)

enqueue(5)

-

(9,7,3,5)

dequeue()

9

(7,3,5)

Интерфейс Queue

Java-интерфейс АТД «очередь» представлен фрагментом кода 4.8. Общий интерфейс указывает, что в очередь могут быть добавлены объекты произвольных классов. Поэтому при попытке удаления элементов может понадобиться приведение типов.

public interface Queue {

*                      возвращает количество элементов в очереди.

7

public int size(); /**

*                      возвращает true, если очередь пуста, в противном случае — false. 7

public boolean isEmptyO;

*                      проверяет элемент в начале очереди.

*                      возвращает элемент из начала очереди.

*                      исключение QueueEmptyException, если очередь пуста. 7

public Object front() throws QueueEmptyException;

*                      добавляет элемент в конец очереди.

*                      параметр element — добавляемый элемент. 7

public void enqueue (Object element); /**

*                      удаляет первый элемент очереди.

*               

*                      возвращает удаленный элемент.

*                      исключение QueueEmptyException, если очередь пуста. 7

public Object dequeue() throws QueueEmptyException;

}

Фрагмент кода 4.8. Интерфейс Queue с комментариями Javadoc (см. п. 1.9.2)

Обратите внимание, что методы size() и isEmpty() выполняют те же функции, что и в случае с АТД «стек». Данные методы, а также метод front() называются аксессорными методами, так как они только возвращают некоторое значение, но не меняют состояние структуры данных. Для обработки ошибки операции над пустой очередью генерируется исключение QueueEmptyException.

Примеры использования очереди

Существует несколько способов применения очереди. Обслуживание клиентов в таких организациях, как магазины, театры, государственные учреждения, центры бронирования билетов и тому подобное, происходит, как правило, по принципу FIFO[12]. В таких организациях вполне логично использовать приложения, в которых обработка транзакций осуществляется на основе очереди. Например, вполне естественно использовать подобные программы для обработки поступающих звонков в автоматический центр бронирования авиабилетов, где клиенты заказывают билеты на определенный рейс. Аналогично такие программы могут быть успешно использованы в автоматических системах продажи билетов на концерты и театральные представления.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии