Лабораторная работа № 7 очередь
Цель работы: изучить структуру данных очередь, разработать класс TQueue для работы с ней и получить практический навык его использования.
Теоретические сведения
Очередь (Queue) – это структура данных, представленная в виде списка элементов, обеспечивающая доступ к ним для чтения только с начала списка, а для записи – только с конца.
Позиция первого элемента в списке называется началом очереди (Front), а позиция последнего – концом очереди (Rear). Первоначально, начало и конец очереди совпадают, т.е. очередь является пустой.
Число элементов в списке определяет длину очереди (Length), которая находится по формуле: Length = Rear - Front +1.
При добавлении элемента в очередь (Операция Insert) позиция последнего элемента увеличивается на единицу, и новый элемент вставляется в конец списка.
При удалении элемента из очереди (Операция Delete) извлекается элемент, который находится в начале списка, а все остальные передвигаются на одну позицию вперед, уменьшая на единицу указатель Rear.
Таким образом, элементы удаляются из очереди в том же порядке, в котором они были там и сохранены, т.е. первый вставленный элемент будет и первым удаляемым. Такой режим доступа к данным получил название FIFO – первым пришел – первым вышел (First In – First Out).
Кроме операции добавления и удаления в очереди предусмотрена операция чтения (Front). Она возвращается значение первого элемента, который будет удален следующим, причем структура самой очереди не изменяется.
Определение очереди допускает возможность существования неограниченно большого списка элементов. Реально построение такой структуры данных практически невозможно. Поэтому очередь всегда имеет ограниченный размер (QueueSize). По мере заполнения очереди ее размер может достичь максимального значения, и добавление следующего элемента станет невозможным. Условием возникновения такой ошибки (QueueOverflow) является следующее равенство: Rear = QueueSize – 1.
Аналогичная ошибка (QueueEmpty) происходит при попытке удаления элемента из пустой очереди: Rear = –1.
ADT - формат класса TQueue
ADT TQueue
Поля
Конец очереди (Rear): Целый тип
Максимальный размер очереди (Size): Целый тип
Список элементов (Items): Динамический массив класса vector
Методы
Конструктор (Create)
Вход: Максимальный размер очереди
Предусловие: Максимальный размер не меньше 1
Начальные значения: Максимальный размер максимален для типа int
Процесс: Конец очереди устанавливается в -1
Добавление (Insert)
Вход: Значение нового элемента очереди
Предусловие: Очередь полностью не заполнена
Процесс: Конец очереди увеличивается на единицу.
Новый элемент добавляется в конец очереди
Постусловие: Конец очереди увеличен на 1. Новый элемент добавлен в конец списка элементов.
Выход: Нет
Удаление (Delete)
Вход: Нет
Предусловие: Очередь не пуста
Процесс: Возвращается элемент из начала очереди. Все последующие элементы переставляются на одну позицию в перед. Удаляется последний элемент, и конец очереди уменьшается на единицу
Постусловие: Элемент удален из начала очереди, и её конец уменьшен на 1
Выход: Значение элемента из начала очереди
Чтение (Front)
Вход: Нет
Предусловие: Очередь не пустая
Процесс: Нет
Выход: Значение элемента из начала очереди
Постусловие: Очередь не изменяется
Проверка пустой очереди (Empty)
Вход: Нет
Предусловие: Нет
Процесс: Проверка, пустая очередь или нет
Постусловие: Нет
Выход: Значение true, если очередь пуста, иначе false
Проверка заполненной очереди (Full)
Вход: Нет
Предусловие: Нет
Процесс: Проверка, полностью заполнена очередь или нет
Постусловие: Нет
Выход: Значение true, если очередь заполнена, иначе false
Очистка очереди (Clear)
Вход: Нет
Предусловие: Нет
Процесс: Удаление всех элементов из очереди и установка её конца в -1
Постусловие: Очередь пуста. Конец очереди установлен в -1
Выход: Нет
Конец ADT TQueue