|
Страница 21 из 60
Очереди Очередь представляет собой линейный список данных, доступ к
которому осуществляется по принципу "первый вошел, первый вышел"
/иногда сокращенно его называют методом доступа FIFO/. Элемент,
который был первым поставлен в очередь, будет первым получен при
поиске. Элемент, поставленный в очередь вторым, при поиске будет
получен также вторым и т.д. Этот способ является единственным при
постановке элементов в очередь и при поиске элементов в очереди.
Применение очереди не позволяет делать прямой доступ к любому
конкретному элементу.
В повседневной жизни очереди встречаются часто. Например,
очередь в банке или очередь в кафетериях с быстрым обслуживанием
являются очередью в указанном выше смысле /исключая те случае,
когда человек пытается добиться обслуживания вне очереди!/. Для
того, чтобы лучше понять работу очереди, рассмотрим две процеду-
ры: постановка в очередь и выборка из очереди. При выполнении
процедуры постановки в очередь элемент помещается в конец очере-
ди. При выполнении процедуры выборки из очереди из нее удаляется
первый элемент, который является результатом выполнения данной
процедуры. Работа очереди проиллюстрирована на рис.4. Следует
помнить, что при выборке из очереди из нее действительно удаляет-
ся один элемент. Если этот элемент нигде не будет сохранен, то в
последствии к нему нельзя будет осуществить доступ.
Операция Содержимое очереди
1 Qstore(A) A
1 Qstore(B) A B
1 Qstore(C) A B C
2 Qretrieve returns A B C
1 Qstore(D) B C D
2 Qretrieve returns B C D
2 Qretrieve returns C D
Рис.4. Работа очереди:
1 - постановка в очередь;
2 - выборка из очереди элемента А, В, С.
Очереди в программировании используются во многих случаях,
например, при моделировании (обсуждается ниже в соответствующей
главе), при планировании работ (метод ПЕРТ или графики Гатта),
при буферизации ввода-вывода.
В качестве примера рассмотрим простую программу планирования
предписаний, которая позволяет обращаться к нескольким предписа-
ниям. При каждом обращении предписание удаляется из списка и на
экран выводится следующее предписание. Для простоты в программе
используется массив символьных строк для управления событиями.
Описание предписания ограничивается 80 символами и число предпи-
саний не должно превышать 100. Прежде всего в этой программе пла-
нирования должны быть предусмотрены процедура постановки в оче-
редь и процедура выборки из очереди. Эти процедуры приводятся
ниже и даются необходимые описания глобальных переменных и типов
данных.
const
MAX_EVENT = 100;
type
EvtType = string[80];
var
event: array[1..MAX_EVENT] of EvtType;
spos, rpos: integer;
{добавить в очередь}
procedure Qstore(q:EvtType);
begin
if spos=MAX_EVENT then
WriteLn('List full')
else
begin
event[spos]:=q;
spos:=spos+1;
end;
end; {конец процедуры постановки в очередь}
{ выборка объекта из очереди }
function Qretrieve:EvtType;
begin
if rpos=spos then
begin
WriteLn('No appointments scheduled.');
Qretrieve := '';
end else
begin
rpos:=rpos+1;
Qretrieve := event[rpos-1];
end;
end; { конец процедуры выборки из очереди }
В работе этих функций используются три глобальные перемен-
ные: "spos", которая содержит индекс следующего свободного эле-
мента; "rpos", которая содержит индекс следующего выбираемого
элемента и "event", которая представляет собой массив символьных
строк с описанием предписаний. Переменные "spos" и "rpos" должны
быть установлены в нулевое значение до первого обращения к проце-
дурам постановки в очередь и выборки из очереди.
В этой программе процедура постановки в очередь помещает но-
вые события в конец списка и делает проверку заполнения списка.
Функция выборки из очереди выбирает события из очереди при необ-
ходимости их обработки. Когда планируется новое событие, перемен-
ная "spos" увеличивается на единицу, а когда событие завершается,
то увеличивается на единицу переменная "rpos". Фактически пере-
менная "rpos" преследует переменную "spos" в проходах по очереди.
Этот процесс иллюстрируется на рис.5. Если значение указателя
свободного места совпадает со значением указателя выбираемого
элемента, то это означает, что в очереди нет событий. Следует
помнить, что хотя функция выборки элемента из очереди в действи-
тельности не нарушает информацию в очереди, повторный доступ к
ней невозможен и фактически она исчезает.
Ниже приводится целиком программа, осуществляющая простое
планирование предписаниями. Вы можете усовершенствовать эту прог-
рамму по собственному желанию.
|