Моделирование структуры данных 'очередь FIFO'
Лабораторная
работа № 1
Название
работы: Моделирование структуры данных «очередь FIFO»
Цель
работы: Подробное изучение моделирования и способа организации данных в очереди
FIFO
Теоретическая часть
Понятие очереди
Очередью FIFO («First in - First out» - «первым
вошёл - первым вышел») называется такой последовательный список с переменной
длиной, в котором включение элементов выполняется только с одной стороны списка
(эту сторону часто называют концом или хвостом очереди), а исключение - с
другой стороны (называемой началом или головой очереди).
Основные операции над очередью.
При работе с очередью применяют следующие
основные операции:- включение в очередь нового элемента. Если в позиции уже
есть элемент, то он смещается, чтобы освободить место для нового элемента. Все
последующие элементы перестраиваются с учётом нового.- удаление элемента из
очереди.- очистка очереди. Обнуление всех элементов очереди.- вывод на экран
содержимого очереди.
Структурный вид очереди приведён на рис. 1.
Рис. 1. Структурный вид очереди.
Машинное представление очереди и реализация
операций
При включении элемента в очередь последний
записывается по адресу, определяемому указателем на конец, после чего этот
указатель увеличивается на единицу. При исключении элемента из очереди
выбирается элемент, адресуемый указателем на начало, после чего этот указатель
уменьшается на единицу. Очевидно, что со временем указатель на конец очереди
при очередном включении элемента достигнет верхней границы той области памяти,
которая выделена для очереди. Однако, если операции включения чередовались с
операциями исключения элементов, то в начальной части, отведенной под очередь
памяти, имеется свободное место. Для того, чтобы места, занимаемые исключенными
элементами, могли быть повторно использованы, очередь замыкается в кольцо:
указатели (на начало и на конец), достигнув конца выделенной области памяти,
переключаются на ее начало. Такая организация очереди в памяти называется
кольцевой очередью. Если в процессе работы с кольцевой очередью число операций включения
превышает число операций исключения, то может возникнуть ситуация, в которой
указатель конца «догонит» указатель начала. Это ситуация заполненной очереди и
попытки записи в нее блокируются.
Использования типа данных «очередь».
Очередь в программировании используется, как и в
реальной жизни, когда нужно совершить какие-то действия в порядке их
поступления, выполнив их последовательно. Примером может служить организация
событий в Windows. Когда пользователь оказывает какое-то действие на
приложение, то в приложении не вызывается соответствующая процедура (ведь в
этот момент приложение может совершать другие действия), а ему присылается
сообщение, содержащее информацию о совершенном действии, это сообщение ставится
в очередь, и только когда будут обработаны сообщения, пришедшие ранее,
приложение выполнит необходимое действие. Клавиатурный буфер BIOS организован в
виде кольцевого массива, обычно длиной в 16 машинных слов, и двух указателей:
на следующий элемент в нём и на первый незанятый элемент.
На рис. 2 представлен исходный код программы,
демонстрирующей процесс функционирования очереди.
Рис. 2 (начало). Исходный код
программы, моделирующей очередь FIFO.
Рис. 2 (продолжение). Исходный код
программы, моделирующей очередь FIFO.
На рис. 3 представлено консольное
окно программы, отображающее результаты функционирования очереди при добавлении
элементов.
Рис. 3. Окно программы при
добавлении элементов в очередь FIFO.
На рис. 4 представлено окно
программы, отображающее результаты функционирования очереди при удалении всех
элементов, кроме одного.
Рис. 4. Окно программы при удалении
элементов из очереди.
На рис. 5 представлена гистограмма
изменения совокупности значений элементов, входящих в очередь, в зависимости от
последовательно проводимых операций добавления и удаления элементов.
Рис. 5. Гистограмма изменения
совокупности элементов.
Вывод
машинное очередь операция
В данной лабораторной работе мы подробно изучили
моделирование очереди FIFO и способ организации данных в ней. В ходе работы на
вычислительной машине была смоделирована очередь FIFO. Кроме того была показана
работа данной очереди на примере последовательности натуральных чисел, которые
сначала добавлялись, а затем удалялись.