Очередь

Очередь – линейная структура данных переменного размера с ограниченным доступом. Доступ к элементам очереди осуществляется по указателю началаочереди и указателюконца очереди.

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

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

Данные в такой структуре обрабатываются в порядке их поступления по принципу «первым пришел – первым ушел». Структуру очереди называют структурой типа FIFO (First In – First Out).

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

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

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

Читается из очереди элемент, на который установлен указатель начала. После выполнения операции чтения указательначала изменяется на 1, передвигаясь к концу очереди, и устанавливается на следующий элемент очереди. Прочитанный элемент оказывается исключенным из очереди. Когда указатель начала совпадет с указателем конца (УН=УК), очередь окажется пустой.

После выполнения операций чтения в начале очереди появляются свободные ячейки, в которые можно записывать новые элементы. Поэтому когда в процессе записи указатель конца достиг конца зарезервированного блока, его можно «перебросить» на начало очереди и продолжат запись в освободившиеся ячейки. Когда указатель конца (после его «переброски») догонит указатель начала (УК=УН), очереди окажется переполненной.

Указатель начала в процессе чтения также может быть «переброшен», если после переброски указателя конца выполнялись операции записи в очередь. Когда указатель начала окажется равным указателю конца – очередь пуста.

 

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

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

 

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

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

Структура очереди используется для решения различных задач, в которых обработка данных должна выполняться в порядке их поступления.

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