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 - момент прихода очередного клиента.