Program StekWork; { процедуры работы со стеком }

Uses Crt;

Type

Ukaz=^Stek;

Stek=record

Name: string;

Next: ukaz

end;

Var

Top, Kon: ukaz;

Rname: string;

C, Pr: char;

B: boolean;

N: integer;

Procedure SozdDob; {создание стека и добавление элементов}

Var B: boolean;

Begin

B:=True;

While B do

Begin

Write('Введите очередной элемент ');

ReadLn(Rname);

if Rname='конец' then B:=False

else

begin

New(Kon);

{ создание элемента стека, на который указывает Kon }

Kon^.Next:=Top;

Kon^.Name:=Rname;

Top:=Kon

end

end;

End;

Procedure Udal; {удаление из стека}

Begin

if Top=Nil then

WriteLn('Попытка удалить из пустого стека !!!')

else

begin

Kon:=Top;

Top:=Top^.Next;

Dispose(Kon);

{ удаление бывшей вершины стека }

end

End;

Procedure Pech; {выдача содержимого стека на экран}

Begin

if Top=Nil then

WriteLn(' Стек пуст !!!')

else

begin

Kon:=Top;

WriteLn(' Состояние стека: ');

While Kon<>Nil do

begin

WriteLn(Kon^.Name);

Kon:=Kon^.Next

end

end

End;

{ НАЧАЛО ОСНОВНОЙ ПРОГРАММЫ }

Begin

ClrScr;

Top:=Nil;

B:=True;

While B do

begin

WriteLn(' Выберите режим работы:');

WriteLn('1-добавление в стек');

WriteLn('2-удаление из стека');

WriteLn('3-выдача на экран');

WriteLn('4-конец работы');

ReadLn(N);

case N of

1: SozdDob;

2: Udal;

3: Pech;

4: B:=False

end

end

End.

Иногда приходится вставлять элементы в середину списка. При статическом описании в этом случае приходится сдвигать часть массива. Это достаточно трудоемкая операция, особенно если она повторяется в цикле.

Для демонстрации гибкости динамических структур данных рассмотрим следующую простую задачу. Имеется стек, описанный в предыдущем примере. Требуется вставить элемент с именем NewName после элемента KeyName. Пусть переменные P и Q имеют тип Ukaz.

P:=Top; B:=True;

While (P<>Nil) and B do

if P^.Name = KeyName then

Begin

B:=False; {для выхода из цикла}

New(Q);

Q^.Name:= NewName;

Q^.Next:=P^.Next;

P^.Next:=Q

End

else P:= P^.Next;

А теперь видоизменим задачу. Пусть вставка требуется перед элементом KeyName. На первый взгляд кажется, что сейчас придется сохранять указатель на предыдущий элемент либо анализировать вместе с текущим и следующий элемент, но указатели позволяют выбрать более простое и красивое решение. Изменения касаются последних трех операторов, следующих после New(Q).

Q^:= P^;

P^.Name:=NewName;

P^.Next:=Q;

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

Рассмотрим более содержательную задачу. С клавиатуры вводится строка, представляющая собой математическое выражение с вложенными скобками трех видов: "{}”, "[]” и "()”. Старшинство скобок не задано, то есть любая пара скобок может быть вложена в любую другую. Требуется проверить синтаксическую правильность расстановки скобок, что определяется следующим правилом: каждой закрывающей скобке должна предшествовать открывающая того же вида и того же уровня вложенности.

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

Program Syntax;

{ анализ вложенности скобок, стек на указателях }

Type

Ukaz=^Stek;

Stek=record { элемент стека }

Ch: char; { символ (открывающие скобки) }

Next:ukaz { следующий элемент }

end;

Var

Top, Kon: ukaz;

Vir: string[80]; { исходное выражение }

I, N: integer;

A, B, Pr: char;

Procedure Dob;

{ добавление в стек; A-добавляемый символ }

Begin

New(Kon);

Kon^.Next:=Top;

Kon^.Ch:=A;

Top:=Kon

End;

Procedure Udal(var Pr:char);

{ исключение из стека; Pr='e'-признак ошибки }

Begin

Pr:='o';

if Top=Nil then Pr:='e'

else

case A of

')': if Top^.Ch<>'(' then Pr:='e';

']': if Top^.Ch<>'[' then Pr:='e';

'}': if Top^.Ch<>'{' then Pr:='e';

end;

if Pr<>'e' then

begin { удаление элемента из вершины }

Kon:=Top;

Top:=Top^.Next;

Dispose(Kon);

end

End;

Begin { начало основной программы }

WriteLn('Введите выражение');

ReadLn(Vir);

Top:=Nil;

N:=Length(Vir); { длина выражения }

For I:=1 to N do

begin

A:=Vir[I]; { очередной символ }

case A of

'(','[','{': Dob;

{ добавление в стек открывающей скобки }

')',']','}':

begin

Udal(Pr);

{ проверка вершины стека; удаление, если нет ошибки }

if Pr='e' then

begin

WriteLn('Ошибка в позиции ', I);

ReadLn; { пауза }

Exit { выход из программы }

end

end

end

end;

if Top<>Nil then

{ в конце не пустой стек }

WriteLn('Нет последних закрывающих скобок')

else

WriteLn('Все в порядке !!!');

ReadLn { заключительная пауза }

End.

Эта программа легко корректируется (на уровне контекстной замены) для случая статического представления стека с помощью массива. Приведем описание переменных и процедур данной версии программы.

Program Syntax; { анализ вложенности скобок, стек - массивом }

Var

Stek:array [1..80] of char;

Top, Kon: integer;

Vir: string[80]; { исходное выражение }

I, N: integer;

A, B, Pr: char;

Procedure Dob;

{ добавление в стек; A-добавляемый символ }

Begin

Top:=Top+1;

Stek[Top]:=A

End;

Procedure Udal(var Pr:char);

{ исключение из стека; Pr='e'-признак ошибки }

Begin

Pr:='o';

if Top=0 then Pr:='e'

else

case A of

')': if Stek[Top]<>'(' then Pr:='e';

']': if Stek[Top]<>'[' then Pr:='e';

'}': if Stek[Top]<>'{' then Pr:='e';

end;

if Pr<>'e' then Top:=Top-1;

{ удаление элемента из вершины }

End;

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

2.2. Очереди и их применение

Вторым распространенным типом линейных списков являются очереди. Это список типа FIFO (первым пришел – первым вышел) с двумя точками входа: начало и конец. Очередь пополняется с конца и продвигается с начала.

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

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

Пусть очередь описана Var Och[1..N] of T, где T – тип элементов очереди. Конец очереди задан индексом Endo.

Постановка в очередь производится командами

Endo:= Endo+1;

Och[Endo]:=NewElement;

Продвижение очереди выполняется команками

For I:=1 to Endo-1 do Och[I]:= Och[I+1];

Endo:= Endo-1;

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

При организации очереди на основе указателей используется следующее описание

Type

Ukaz=^Och;

Och=record

Info: …;

{ поля информационной части элемента }

Next: ukaz

end;

Var

Bego, Endo: ukaz; { начало и конец очереди }

Выгодно указатели Next ориентировать в направлении от начала очереди к концу, а не наоборот. В этом случае постановка в очередь выполняется командами

New(Kon);

Endo^.Next:=Kon;

Kon^.Next:=Nil;

и далее присвоение значений информационным полям.

Продвижение очереди производится операторами

If Bego <> Nil then

Begin

Kon:=Bego;

Bego:=Bego^.Next;

Dispose(Bego);

End;

В качестве примера рассмотрим следующую задачу, связанную с ведением очереди. Дан список клиентов, желающих посетить банк в некоторый период времени. Для каждого клиента заданы имя, момент прихода и время обслуживания. В банке работает один кассир. Если в момент прихода очередного клиента кассир занят, клиент становится в очередь. Обслуженный кассиром клиент покидает банк. Требуется промоделировать работу кассира, то есть последовательно выдать информацию о приходах и уходах клиентов из банка с указанием состояния очереди. Необходимо также найти среднее время обслуживания клиента.

Будем считать, что список упорядочен по возрастанию моментов прихода клиентов. При работе банка встречаются два класса событий:

• приход клиента и постановка его в очередь (если кассир не занят, то очередь будет состоять только из пришедшего клиента);

• продвижение очереди.

Пусть имеется N клиентов. Обозначим через M[I] момент прихода, а через T[I] время обслуживания i-го клиента. Рассмотрим алгоритм решения задачи.

1. S:=0 - общее время обслуживания клиентов.

2. R:=M[1]+T[1] - момент разгрузки очереди.

3. I:=1 - начало цикла по клиентам до I=N.

4. P:=M[I], где P - момент прихода очередного клиента.