Аналогично стеку, каждый элемент очереди должен иметь ссылку на следующий за ним элемент, поэтому элемент очереди объявляется как запись с двумя полями – информационное поле и связующее поле. Но для реализации операций с очередью необходимы уже две переменные: указатель pFirst на начало очереди и указатель pLast на конец очереди.
Приведенная ниже схема элементов очереди отражает логический порядок следования элементов, физически же элементы могут находиться в любых свободных областях памяти.
| эл-т 1 |
| next : 2 |
. . . . . . . .
| pFirst |
Основные операции с динамической очередью:
- проверка отсутствия элементов в очереди
- добавление нового элемента в конец очереди
- удаление элемента из начала очереди
- проход по очереди от начала к концу
Добавление нового элемента немного по-разному реализуется для пустой и непустой очереди. Аналогично, по-разному выполняется удаление из очереди, содержащей один или более одного элемента. Для того, чтобы эти операции во всех случаях выполнялись единообразно, часто используется следующий прием: в начало очереди вводится фиктивный элемент-заголовок, который НИКОГДА не удаляется и всегда содержит адрес первого элемента очереди.
В этом случае создание пустой очереди включает в себя:
- выделение памяти для заголовка с помощью указателя pFirst
- занесение в ссылочную часть заголовка пустого указателя nil
- установка указателя конца очереди pLast = pFirst
Схемы пустой и непустой очереди приводятся на следующих рисунках:
| заголовок |
| Next: 1 |
…..
| pFirst |
Необходимые описания типов и переменных:
type pQueueItem = ^ TQueueItem;
{ссылочный тип для адресации элементов очереди}
TQueueItem = record{базовый тип: структура элемента очереди}
inf : integer; {информационная часть}
next : pQueueItem;
{ссылочная часть: адрес следующего элемента}
end;
var pFirst, pLast : pQueueItem;
Тогда условие пустой очереди можно записать следующим образом:
pFirst^.next = nil
Для прохода по очереди от первого реального элемента к последнему необходимо:
- ввести вспомогательную ссылочную переменную pTemp
- установить pTemp в адрес первого реального элемента: pTemp := pFirst^.next
- организовать цикл по условию достижения конца очереди
- в цикле обработать очередной элемент с помощью указателя pTemp и изменить этот указатель: pTemp := pTemp^.next
Добавление элемента в конец очереди выполняется следующим образом:
- выделить память для нового элемента с помощью стандартной функции Newи вспомогательной ссылочной переменной pTemp:
- заполнить поля нового элемента, в частности в связующую часть установить значение nil: pTemp^.next := nil
- изменить связующую часть бывшего последнего элемента таким образом, чтобы она адресовала новый добавленный элемент: pLast^.next := pTemp;
- изменить значение указателя pLast так, чтобы он указывал новый последний элемент: pLast := pTemp;
Удаление элемента из начала очереди (но после заголовка!) выполняется следующим образом:
- адресуем удаляемый элемент с помощью вспомогательной переменнойpTemp: pTemp := pFirst^.next;
- изменить связующую часть заголовка так, чтобы она указывала на второй элемент очереди, который теперь должен стать первым: pFirst^.next := pTemp^.next
- если после удаления в списке не остаётся реальных элементов, то необходимо изменить указатель pLast: pLast := pFirst
- обработать удаленный элемент, например — освободить занимаемую им память с помощью стандартной подпрограммы Dispose(pTemp)или включить его во вспомогательную очередь удаленных элементов
Сравнение двух способов реализации очереди полностью аналогично стеку. Интересной разновидностью очереди являются приоритетные очереди, в которых элементы выстраиваются не только в порядке поступления, но и в соответствии с их приоритетами: сначала идут более приоритетные элементы, потом – все менее приоритетные. Одноприоритетные элементы располагаются в порядке поступления. Это требует изменения процедуры добавления элемента в очередь: надо прежде всего найти место в очереди, куда должен вставиться новый элемент в соответствии с его приоритетом, а потом уже выполнить саму вставку. Фактически, приоритетную очередь можно рассматривать как разновидность упорядоченного линейного списка. Реализация линейных списков подробно рассматривается в следующей теме.
Практические задания
Задание 1.Реализовать программу, выполняющую стандартный набор операций со стеком на основе массива:
- проверку пустоты стека
- проверку заполненности стекового массива
- добавление элемента в вершину стека
- удаление элемента из вершины стека
- вывод текущего состояния стека на экран
Требования:
- все действия должны быть оформлены как процедуры или функции
- добавлению/удалению должна предшествовать проверка возможности выполнения этих операций
- главная программа реализует следующий набор действий:
o инициализация пустого стека
o организация диалогового цикла с пользователем
Задание 2.Реализовать тот же набор действий на основе динамического распределения памяти.
Требования аналогичны заданию 1, за исключением того, что проверку заполненности стека проводить не надо. Пустой стек задается установкой sp := nil.
Задание 3. Добавить в предыдущую программу возможность занесения в стек сразу нескольких значений. Количество вводимых значений должно запрашиваться у пользователя, а сами значения можно формировать случайным образом с помощью функции Random (не забыть предварительно вызвать функцию Randomize). Проверить работоспособность программы при различных количествах вводимых элементов, в том числе – для больших значений (десятки тысяч элементов).
Задание 4 (дополнительно).Добавить в предыдущую программу следующие возможности:
- при удалении элемента из основного стека запросить у пользователя, что делать далее с этим элементом: действительно удалить с освобождением памяти или включить его в вершину вспомогательного стека удаленных элементов
- при добавлении нового элемента запросить у пользователя происхождение этого элемента: действительно создание нового элемента или выбор его с вершины вспомогательного стека
- вывод содержимого вспомогательного стека удаленных элементов
Задание 5.Реализовать программу, выполняющую стандартный набор операций с кольцевой очередью на основе массива:
- проверку пустоты очереди
- проверку заполненности очереди
- добавление элемента в конец очереди
- удаление элемента из начала очереди
- вывод текущего состояния очереди на экран
Требования к программе:
- все действия должны быть оформлены как процедуры или функции
- добавлению/удалению должна предшествовать проверка возможности выполнения этих операций
- главная программа реализует следующий набор действий:
o инициализация пустой очереди
o организация диалогового цикла с пользователем
Задание 6.Реализовать тот же набор действий на основе динамического распределения памяти.
Требования аналогичны заданию 1, за исключением того, что проверку заполненности очереди проводить не надо. Пустая очередь содержит только заголовочный элемент
Задание 7.Написать программу для моделирования работы очереди со случайным числом добавляемых и удаляемых элементов.
Пусть за единицу времени (например – 1 минуту) в очередь либо добавляется, либо удаляется случайное число элементов в количестве от 1 до 3-х. Одновременно добавление и удаление НЕ происходит. Для наглядности элементами пусть являются большие латинские буквы (коды ASCII от 65 до 90), выбираемые случайным образом. Тип операции с очередью (добавление или удаление) также задается случайно. Это приводит к тому, что очередь случайно растет и убывает. Программа должна наглядно показывать состояние очереди в каждый момент времени.
Рекомендации по разработке программы.
За основу взять предыдущую программу, внеся в ее процедуры следующие изменения:
- процедура добавления вместо запроса у пользователя информационной части нового элемента должна получать ее как входной параметр
- процедура удаления должна выполнять удаление одного элемента только если очередь НЕ пустая
Главная программа должна:
- после создания пустой очереди, содержащей только заголовок, инициировать датчик псевдослучайных чисел (процедура Randomize) и вывести соответствующее сообщение
- организовать цикл с выходом при вводе пользователем какого-либо специального символа (например – буквы q)
- сгенерировать случайное число в диапазоне от 1 до 100 и проверить его четность с помощью операции взятия остатка от деления этого числа на 2
- если число четное – реализовать операцию добавления, если нечетное – операцию удаления
- в том и другом случае выполнить:
o генерацию случайного числа добавляемых или удаляемых символов в диапазоне от 1 до 3-х
o вывод сообщения о выполняемом действии и количестве добавляемых/удаляемых элементов
o выполнение цикла для добавления или удаления заданного числа элементов с вызовом соответствующих процедур работы с очередью, причем при добавлении новый символ должен генерироваться случайно с помощью его кода (диапазон 65 – 90) с последующим преобразованием кода в сам символ с помощью стандартной функции CHR
- вывести текущее состояние очереди
- запросить у пользователя символ для окончания цикла (при выполнении программы для продолжения работы цикла можно просто дважды нажать клавишу ввода)
После отладки программы надо выполнить ее несколько раз для следующих ситуаций:
- случайное число добавляемых и удаляемых элементов одинаково (например – от 1 до 3-х)
- число добавляемых элементов чуть больше (в среднем!) числа удаляемых (например, добавляется случайное количество элементов в диапазоне от 1 до 4-х, а удаляется – от 1 до 3-х)
- число удаляемых элементов чуть больше числа добавляемых
Для каждого случая выполнить программу при достаточно большом числе добавлений/удалений (30-40) и сделать вывод о поведении очереди.
.
2.7. Контрольные вопросы по теме
1. Что такое стековый принцип сохранения элементов?
2. Какие основные операции реализуются для стеков?
3. Какие шаги выполняются при добавлении элемента в стек-массив?
4. Какие шаги выполняются при удалении элемента из стека-массива?
5. Какие особые ситуации возможны при реализации стека с помощью массива?
6. Какую структуру должен иметь элемент стека при динамической реализации?
7. Что такое физический и логический порядок следования элементов в стеке?
8. Как между собой связываются соседние элементы стека?
9. Какие типы данных необходимы для динамической реализации стека?
10. Какие переменные необходимы для реализации операций с динамическим стеком?
11. Как реализуется проход по динамическому стеку?
12. Как выполняется добавление элемента в динамический стек?
13. Как выполняется удаление элемента из динамического стека?
14. Сравните динамическую и статическую реализации стека
15. Что такое структура данных типа очередь?
16. Какие основные операции необходимы для реализации структур типа очередь?
17. Как реализуется очередь с помощью массива?
18. Как работает кольцевая очередь, реализованная с помощью массива?
19. Какие особые ситуации возможны при реализации очереди с помощью массива?
20. Как выполняется добавление элемента в очередь-массив?
21. Как выполняется удаление элемента из очереди-массива?
22. На чем основана динамическая реализация очереди?
23. Зачем в очередь вводится фиктивный заголовочный элемент?
24. Что включает в себя создание пустой динамической очереди с заголовком?
25. Какие типы данных необходимы для динамической реализации очереди?
26. Какие переменные используются для реализации основных операций с динамической очередью?
27. Как реализуется проход по динамической очереди?
28. Как реализуется добавление элемента в динамическую очередь?
29. Как реализуется удаление элемента из динамической очереди?
30. Какие особенности имеет приоритетная очередь?
31. Сравните статическую и динамическую реализации очереди.
