Реализация стеков и очередей (псевдодинамическими) массивами.

Псевдодинамические массивы - последовательности переменной длины m, m£MaxLen, где MaxLen - константа.

const MaxLen=100;

type

tIndex=1..MaxLen;

tArray=array[tIndex];

tPseudoArray=

record content:tArray; {содержимое/компоненты массива}

{можно задать len:tIndex; фактическая длина массива}

{или - принимаемый далее вариант}

top:tIndex; {len+1, первое свободная позиция в массиве, начало кучи -незаполненной части массива }

end;

Нетрудно сопоставить содержимому стеков содержимое массивов, а стековым операциям - соответствующие алгоритмы обработки массивов.

type

tStack=tPseudoArray;

 

procedure Pop(var stack:tStack; var x:T);

begin with stack do begin top:=top-1; x:=Content[top] end; end;

procedure Push(var stack:tStack;x:T);

begin with stack do begin Content[top]+1; top:=top+1; end; end;

{при неосмотрительном использовании, выполнение операторов чревато }

{выходом за границы массива [1..MaxLen]}

{но ситуация не совсем симметрична, у пользователя есть функция проверки пустоты стека, но нет функции проверки переполнения стека }

function Empty(Stack:tStack):boolean;

begin Empty:=Stack.top=1 end

procedure Create(var Stack:tStack); begin Stack.top:=1 end;

procedure Destroy(Stack:tStack)); begin Stack.top:=1 end;

 

Одинаковая реализация разных операций, конечно, настораживает. Create призвана порождать функцию (с пустой областью определения), Destroy - уничтожать функцию (с любой областью определения), наша релизация лишь опустошает область определения функции. Причина ясна - мы никак не моделируем понятие состояния (см. далее) Пока оставим нюансы - так или иначе, главные стековые операции push и pop работают правильно.

 

Обратимся к моделированию очередей. Определим "псевдодинамические" массивы с двумя концами.

tPseudoArray2=

record content:tArray; {содержимое/компоненты массива}

start, finish:tIndex; {начало+1 и конец-1 массива -}

{начало правой кучи и конец левой кучи}

end;

tQueue=tPseudoArray2;

 

Реализация операций как будто очевидна - класть значения в конец, а брать - из начала массива. Формально верная, такая реализация порождает частный случай проблемы динамического распределения памяти (общую формулировку см. ниже): Вводя в конец (занимая одну, "правую" часть кучи) и выводя из начала массива значения компонент (опустошая другую, "левую" часть кучи), мы весьма скоро можем оказаться в ситуации, когда свободной памяти много, а класть компоненты некуда!

 

Правда, в этом частном случае ее нетрудно решить, объединяя две части кучи, мысленно рассматривая массив как кольцо.

procedure Put(var Queue:tQueue; x:T); { Поставить В Очередь }

begin

with Queue do

begin content[finish]:=x;

if finish=nMax then finish:=1 else inc(finish) {» finish:=finish+1 (mod nMax)}}

{интересно - см. понятие модульной арифметики в курсе дискретной математики}

end; end;

procedure Get(r,x); { Вывести Из Очереди }

begin

with r do

begin x:= content[start];

if start=1 then start:=nMax else dec(start) {» start:=start-1 (mod nMax)}}

end; end;

function Empty(r): boolean;

begin Empty:= (start=finish) or ((start=nMax) and (finish=1)) {start=finish (mod nMax)} end;

 

Замечание. Снова более эффективная, но не защищенная реализация - пользователь процедур должен сам следить за переполнением очереди.