Затем необходимо создать пустую очередь, выполнив
операцию init. Параметрами этой процедуры являются
имя массива, моделирующего очередь, и связанные с ним указатели
очереди. При этом изменяются только значения указателей. Написание в
качестве параметров имени массива и указателей подчеркивает тот
факт, что имя массива и указатели являются единым целым при
моделировании очереди.
S[0]: = 1;
a[0]: = 1;
for i:=1 to N do {1. 2}
begin
a[i]: = a[i - 1]/x;
S[i]: = S[i - 1] + a[i]
end;
Procedure Init (var q: Queue;
var Free,First:integer);
begin
First: =1;
Free: =1;
end;
Операция Empty используется для
того, чтобы определить, пуста очередь или нет.
Function Empty(var q: Queue;
var First, Free:integer): boolean;
begin
if First=Free then Empty:=true
else Empty:=false;
end
Операция добавления в очередь
Insert может выполняться всегда, если не существует
ограничений на количество элементов очереди. Если же для реализации
очереди используется массив из maxqueue элементов, то в очереди не
может быть помещено более maxqueue элементов.
Поэтому, прежде чем вставить элемент в очередь,
необходимо проверить есть ли в массиве свободное место для
размещения нового элемента очереди. Если места достаточно, то новый
элемент помещается в массив. При этом будем формировать код, что
операция добавления прошла успешно. Для этого будет использоваться
переменная Code, значение которой будет равно 0.
Если места для нового элемента в массиве нет, то значение переменной
Code будет равно 1, что будет означать, что
операция добавления элемента не выполнена из-за отсутствия места в
очереди.
Добавление нового элемента можно оформить в виде
процедуры:
Procedure InsQue (var q: Queue;
var Free,First: integer;
var Code: integer;
x: real);
begin
if Free > maxqueue
then begin
Code:=1; {Очередь полна}
exit;
end;
q[Free]:=x;
Free:=Free+1;
Code:=0;
end
Операция удаления элемента из очереди
Remove может выполняться только в том случае, если
очередь не пуста. Поэтому при удалении элемента из очереди прежде
всего необходимо убедиться в том, что очередь не пуста. И лишь после
этого можно удалять элемент очереди. Если ни одного элемента в
массиве нет, то значение переменной Code будет
равно 2, что будет означать, что операция удаления элемента не
выполнена из-за отсутствия элементов в очереди.
Процедура удаления из очереди может быть записана в
виде:
Procedure RemQue(var q: Queue;
var Free,First: integer;
var Code: integer;
var x: real);
begin
if Empty(q,First,Free) then
begin
Code:=2; {Очередь пуста}
exit;
end;
x:=q[First];
First:=First+1;
Code:=0;
end;
Одним из недостатков приведенной реализации
является тот факт, что при многократном выполнении поочередно
операций Insert и Remove в очереди
реально будет находится небольшое число элементов, в то время как
указатель конца очереди Free превысит значение maxqueue. Другим недостатком является тот факт, что
очередь не учитывает величину изменения данных, что может быть
полезно при выборе наилучшего очередного кандидата для пересчета.
Для устранения этих недостатков есть структура данных - куча.
Назад
