Методичка: Лабораторная 4

Очередь

Очередью называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (хвоста очереди), а исключение – с другой стороны (из головы очереди). Часто для обозначения очереди используется аббревиатура FIFO (First In First Out – первым пришел – первым исключается).

Операции над очередью те же, что и над стеком: основные – включение и исключение, вспомогательные – неразрушающее чтение, очистка, проверка на пустоту, проверка на полноту.

Как и стеки, очереди могут представляться в памяти в виде вектора или связного списка.

При векторной реализации очереди в дополнение к обычным для дескриптора параметрам должны находиться два указателя (индекса): индекс начала очереди (первого элемента очереди) и индекс ее конца (первого свободного элемента в очереди). При включении элемента в очередь элемент записывается по адресу, определяемому указателем на конец, после чего этот указатель увеличивается на единицу. При исключении элемента из очереди выбирается элемент, адресуемый указателем на начало, после чего этот указатель также увеличивается на единицу.

Очевидно, что со временем указатель на хвост при очередном включении элемента достигнет верхней границы той области памяти, которая выделена для очереди. Однако если операции включения чередовались с операциями исключения элементов, то в начальной области отведенной под очередь памяти имеется свободное место. Для того чтобы память, занимаемая исключенными элементами, могла быть повторно использована, очередь замыкается в кольцо: указатели (на голову и на хвост), достигнув конца выделенной области памяти, переключаются на ее начало. Такая организация очереди в памяти называется кольцевой очередью.

В исходном состоянии указатели на голову и на хвост очереди указывают на начало области памяти. Равенство этих двух указателей (при любом их значении) является признаком пустой очереди. Если в процессе работы с кольцевой очередью число операций включения превышает число операций исключения, то может возникнуть ситуация, в которой указатель конца «догонит» указатель начала. Очередь будет заполненной, но если при этом указатели сравняются, понять, заполнена очередь или пуста, будет невозможно. Во избежание такой ситуации к кольцевой очереди предъявляется требование, чтобы между указателем на хвост и указателем на голову оставался «зазор» из свободных элементов. Когда этот «зазор» сокращается до одного элемента, очередь считается заполненной, и дальнейшие попытки записи в нее блокируются. Очистка очереди сводится к записи одного и того же (необязательно начального) значения в оба указателя. Пример организации кольцевой очереди приведен в приложении 6.

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

Дек

Дек (англ. deque – double ended queue, т.е. очередь с двумя концами) – это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом концах списка. Операции над деком: включение элемента справа, включение элемента слева, исключение элемента справа, исключение элемента слева.

Как и стеки, очереди могут представляться в памяти в виде вектора или связного списка.

Физическая структура дека в векторном представлении идентична структуре кольцевой очереди. Единственное отличие – изменение индексов левого и правого концов дека возможно не только в сторону увеличения, но и в сторону уменьшения адресов. Естественно, что при достижении нижней границы вектора указатель должен быть переставлен на его верхнюю границу.

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

Частный случай дека – дек с ограниченным входом и дек с ограниченным выходом. В первом случае добавление элемента возможно только в один конец списка, а удаление – с обоих. Во втором добавление элементов осуществляется в оба конца списка, а удаление – только с одного. Соответственно при списковой реализации дек с ограниченным входом потребует наличия двух связей, а для дека с ограниченным выходом будет достаточно односвязного списка.

Постановка задачи

Написать две программы согласно номеру индивидуального варианта. В первом задании данные хранятся в бинарном файле записей (можно использовать файл, созданный при выполнении лабораторной работы №1), а для обработки считываются в список. При выходе из программы обработанные данные сохраняются в том же файле. Список должен описываться классом. Для организации интерфейса в программе должно использоваться меню. Во втором задании необходимо создать класс, описывающий стек или очередь, и программу решения поставленной задачи с использованием объекта этого класса.

Задания могут быть выполнены на трех уровнях сложности.

1. Низкий. В первом задании список линейный односвязный. Обязательные методы класса: добавление элемента в начало или конец списка (на выбор), просмотр списка, удаление элемента из начала или конца списка (на выбор). Вывод списка на экран можно выполнять в любом (главное, читабельном) виде. Во втором задании реализовать определенную вариантом структуру данных (стек или очередь) любым удобным способом, вместо решения поставленной задачи можно написать программу тестирования объекта созданного класса.

2. Средний. В первом задании список линейный односвязный. Обязательные методы класса: добавление элемента в упорядоченный список с сохранением упорядоченности (ключевое поле выбрать самостоятельно), просмотр списка, удаление произвольного элемента списка. Вывод данных осуществлять в табличном виде с графлением подходящими символами. Во втором задании создать класс, описывающий требуемую структуру данных, в соответствии с заданным вариантом реализации.

3. Высокий. В первом задании список линейный двусвязный. Обязательные методы класса: добавление элемента в произвольное место списка, просмотр списка в прямом и обратном направлении, удаление произвольного элемента списка. Вывод данных осуществлять постранично в табличном виде с графлением подходящими символами. Во втором задании создать необходимую для решения задачи структуру данных с помощью двух структур хранения: векторной и списковой,– реализацию оформить в виде классов с единым интерфейсом.

Варианты реализаций

1. Стек в массиве. Заполнение стека должно производиться с начала массива. Методы класса: добавление элемента в стек, удаление элемента из стека, получение значения с вершины стека, проверка заполнения стека, проверка пустоты стека.

2. Разработайте класс, реализующий стек с помощью указателей. Методы класса: добавление элемента в стек, удаление элемента из стека, получение значения с вершины стека, проверка заполнения стека, проверка пустоты стека, очистка стека.

3. Разработайте класс, реализующий очередь в «циклическом» массиве. Поля класса: массив, индексы первого и последнего элементов в очереди. Методы класса: добавление элемента в очередь, удаление элемента из очереди, получение значения из очереди, проверка заполнения очереди, проверка пустоты очереди.

4. Разработайте класс, реализующий очередь в «циклическом» массиве. Поля класса: массив, индекс первого элемента в очереди, количество элементов в очереди. Методы класса: добавление элемента в очередь, удаление элемента из очереди, получение значения из очереди, проверка заполнения очереди, проверка пустоты очереди.

5. Разработайте класс, реализующий очередь с помощью указателей. Методы класса: добавление элемента в очередь, удаление элемента из очереди, получение значения из очереди, проверка заполнения очереди, проверка пустоты очереди.

Контрольные вопросы

1. Что такое абстрактный тип данных?

2. Что такое список?

3. Что такое связанный список?

4. Какие виды списков Вы знаете?

5. Какие методы применимы к спискам?

6. Какие методы реализации списков Вы знаете?

7. Что такое стек?

8. Какие операции применимы к стекам?

9. Каков механизм заполнения стека? Что такое «дно» стека?

10. Что такое очередь?

11. Какие операции применимы к очередям?

12. Каков механизм заполнения очереди?

13. Что такое дек? Какие операции применимы к декам?

14. В чем различие между конкатенацией двух стеков и конкатенацией двух очередей?

15. Что такое дескриптор списка?

16. Как и когда используется нулевой указатель NULL?

17. Какая структура данных описывается аббревиатурой LIFO?

18. Какая структура данных описывается аббревиатурой FIFO?

19. Что такое «структура данных» и «структура хранения»?

20. От чего зависит выбор структуры хранения для реализации структуры данных?

Варианты заданий

Вариант 17

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

2.Написать программу, использующую класс (реализация 2) для отыскания прохода по лабиринту. Лабиринт представляется в виде матрицы, состоящей из квадратов. Каждый квадрат либо открыт, либо закрыт. Вход в закрытый квадрат запрещен. Если квадрат открыт, то вход в него возможен со стороны, но не с угла. Каждый квадрат определяется его координатами в матрице. После отыскания прохода программа печатает найденный путь в виде координат квадратов.