| [Оглавление] | [<< страница] | [>>страница] |
Очередь это динамически изменяемый упорядоченный набор элементов. Добавление элемента в очередь производится с одного конца (хвоста очереди), а выборка — с другого конца (головы очереди) в соответствии с правилом "Первым пришел — первым ушел" (FIFO: First Input — First Output). Такая очередь является простой очередью без приоритетов. Часто используются очереди с приоритетами, в них более приоритетные элементы включаются ближе к голове очереди, выборка осуществляется, как обычно, с головы очереди.
Очереди находят широкое применение в операционных системах (очереди задач, буфера ввода-вывода, буфер ввода с клавиатуры, очереди в сетях ЭВМ и т.п.), при моделировании реальных процессов и т.д. Очереди могут иметь векторную или списковую структуру хранения, в свою очередь векторная структура может занимать статическую либо динамическую память. Очередь векторной структуры из-за ограниченности элементов имеет свойство переполнения, когда хвост очереди достигнет конца вектора. В этом случае добавление элементов становится невозможным, даже если в начальной части вектора будут свободные элементы из-под выбранных элементов. Для устранения такого недостатка образуют кольцевые очереди. При достижении конца вектора новые элементы добавляются в свободные элементы с начала вектора. Здесь так-же возможно переполнение, когда хвост догонит голову. Если же голова догонит хвост, то очередь оказывается пустой.
Основными операциями над очередью являются;
При их выполнении используются такие вспомогательные операции, как проверка наличия элементов, проверка переполнения, организация перехода по кольцу, изменение приоритета: вызванная этим перестройка очереди.
Операции над очередями списковой структуры не вызываю никаких затруднений. Элементы добавляются в начало списка, а выбираются с его конца либо, наоборот, в зависимости от того, какая операция должна выполняться быстрее: включение или выборка элемента.
Операции создания и освобождения очереди векторной структуры. Они такие же, как и при работе со стеками. Дескриптор очереди должен содержать адрес начала вектора, указатели головы, хвоста и конца очереди в виде их адресов или индексов.
Рассмотрим возможные состояния и соответствующие действия при выполнении операций включения и выборки элементов.
Включение в очередь нового элемента. 1. Очередь заполнена -возврат признака переполнения. 2. Очередь пуста — включение элемента в начало очереди, корректировка указателя хвоста. 3. Очередь заполнена частично - добавление в первый свободный элемент с учетом кольцевой организации, корректировка указателя хвоста.
Выборка элемента из очереди. 1. Очередь пуста - возврат соответствующего признака. 2. В очереди единственный элемент — выбрать элемент и установить указатели в начальное состояние. 3. Очередь заполнена частично — выбрать элемент с головы очереди с у том кольцевой организации, скорректировать указатель головы.
Создадим файл, в котором определены структура дескриптора очереди QUE и переменная ql типа QUE: туда же включены функции, реализующие операции над очередями. Дескриптор строится транслятором, память под элементы выделяется динамически по запросу. Этот файл включается директивой #include в исходный файл с программой для работы с очередью. Предварительно должен быть определен тип элемента ЕL, например define int EL. Допускаются типы EL, только такие, что переменным этого типа можно присваивать значения оператором “=". Такими типами являются скалярные типы и структурный тип struct.
Пример разберём на практических занятиях.
| [Оглавление] | [<<страница] | [>>страница] | [В начало ] |