Лабораторная работа 3 Структура данных типа "очередь"

1.Общие понятия

Очередь-это последовательный список с переменной длиной, включение элементов в который происходит с одной стороны, а исключение элементов-с другой стороны списка. Это позволяет реализовать принцип FIFO (первый пришел-первый ушел). Принцип FIFO хорошо вписывается в рельные процессы, что позволяет широко использовать структуру типа "очередь" при машинном моделировании указанных процессов. Основными операциями с очередью являются: включение элемента и исключение элемента. При выполнении первой операции модифицируется указатель на первый свободный слот после последнего занятого слота в хвосте очереди(Р2). При выполнении второй операции модифицируется указатель первого занятого слота в голове очереди(Р1). Указатели Р1 и Р2 изменяются в пределах, которые определяются при описании очереди. Для обычной очереди всегда выполняется соотношение Р2>=Р1. Однако в ней, когда Р2 достигает максимальное значение, фиксируется переполнение очереди даже в том случае, если со стороны головы имеются свободные слоты. Поэтому на практике чаще используют кольцевую очередь, которая образуется замыканием простой очереди. Процедура замыкания заключается в том, что при достижении верхнего предела очереди указатель Р1 или Р2 переключаются на самый первый слот (если при этом первый слот занят, то эта операция является для указателя Р2 недоступной, так как в этом случае очередь является "переполненной"). Кольцевая очередь в отличии от обычной позволяет использовать пространство, отведенное в памяти под очередь, более эффективно, то есть полностью под занятые слоты. В заключении отметим, что очередь, как и стек относится к типу полустатических структур.

2.Цель работы

Целью работы является изучение и отработка приемов и навыков использования кольцевых очередей в организации алгоритмических структур. Машинная реализация этих структур планируется на языке Турбо Паскаль или С++ и должна занимать не более 4-х часов.

3.Варианты заданий выполнения лабораторной работы

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

1. Используя очередь, сравнить символьный запрос с набором шаблонов.

2. Реализовать процедуру распределения информации, накопленной в кольцевой очереди, между несколькими пользователями таким образом, чтобы конкретному пользователю пересылалась информация из очередного слота только в том случае, если она начинается на заранее оговоренные символы.

3. Реализовать процедуру распределения информации, накопленной в кольцевой очереди, между несколькими пользователями таким образом, чтобы информация распределялась в ответ на запросы пользователя, но с учетом их приоритетов.

4. Реализовать процедуру распределения информации, накопленной в кольцевой очереди, между несколькими пользователями таким образом, чтобы информация из очередного слота доставалась пользователю, чей запрос совпадал бы с ключом этого слота.

5. Реализовать процедуру распределения информации, накопленной в кольцевой очереди, между несколькими пользователями таким образом, чтобы информация выдавалась свободному в данный момент пользователю (в случае, если свободны несколько пользователей, то абонент определяется в соответствии с некоторыми правилами, например, по принадлежности пользователя к какому либо району или фирме).

6. В режиме мультиочереди (не менее 4-х простых очередей) организовать сравнение элементов кольцевых очередей, находящихся на одинаковом расстоянии от указателя Р1 с последующим выводом одинаковых элементов на экран.

7. Используя очередь, разработать процедуру изъятия некорректных скобок и интервалов в арифметических выражениях.

8.Используя очередь, создать простейшую БД, содержащую сведения о студентах.

9.Используя очередь, вывести из экзаменационной ведомости список, получивших одинаковые оценки.

10.Объединить две очереди таким образом, чтобы в суммарной очереди не было одинаковых элементов;

11.Объединить две очереди таким образом, чтобы в суммарной очереди нечетный элемент второй очереди шел за нечетным элементом первой.

12.Объединить две очереди таким образом, чтобы суммарная очередь была отсортирована.

13.Объединить две очереди таким образом, чтобы элементы суммарной очереди представляли из себя разность соответствующих элементов исходных очередей.

14.Объединить две очереди таким образом, чтобы элементы суммарной очереди представляли из себя сумму соответствующих элементов исходных очередей.

15. При помощи очереди изъять лишние скобки из арифметического выражения.

16. Использовать буфер клавиатуры для фиксирования последней нажатой клавиши.

17. Найти способ (и реализовать его программно) увеличения размера буфера клавиатуры.

18. На основе очередей промоделировать работу какой-нибудь системы массового обслуживания.

19. Представляя колоду карт как очередь, найти способ ее перемешать так, чтобы карты в колоде(очереди) были расположены случайным образом.

20. Пусть первоначально карты расположены в нескольких очередях(кучках). Объединить их в одну очередь(колоду) таким образом, чтобы они были хорошо перемешаны.