(* Очередь - последовательность (однотипных) элементов данных, в которой: *) (* - включение элементов выполняется на одном конце последовательности; а *) (* - выбор элементов - на другом конце последовательности. *) (* *) (* Основные операции: (* - включить в очередь новый элемент; PushOh *) (* - выбрать элемент из очереди; PopOh *) (* + породить пустую очередь; BornOh *) (* + проверить наличие элементов в очереди. EmpOh *) |
(* Пример. Очередь символов. *)
(* Реализация в виде циклического массива Oh *)
(* Bg - позиция чтения из очереди *)
(* Ko - количество элементов в очереди *)
program ExmOh;
Const So = 8; (* So+1 - мах эл-тов в очереди *)
Var Oh : array [0..So] of char;
Bg,Ko : integer;
A : char;
procedure PushOh(A : char);
var L : integer;
begin if Ko < So + 1 then begin
L:=(Bg + Ko) mod (So + 1);
Oh[L]:=A;
Ko:=Ko+1
end end;
procedure PopOh(var A : char);
begin if 0 < Ko then begin
A:=Oh[Bg];
Ko:=Ko-1;
Bg:=(Bg + 1) mod (So + 1);
end end;
function EmpOh : boolean;
begin EmpOh:=(Ko = 0) end;
procedure BornOh;
begin Bg:=0;
Ko:=0 end;
begin (* Пример внутри примера *)
BornOh;
PushOh(';'); PopOh(A);
PushOh(';'); PopOh(A);
PushOh(';'); PopOh(A);
PushOh(';'); PopOh(A);
PushOh(';'); PopOh(A);
writeln('Bg = ',Bg,' Ko = ',Ko); (* Bg = 5; Ko = 0 *)
(* Посимвольный ввод 'Иванов' *)
PushOh('И'); PushOh('в');PushOh('а');
PushOh('н'); PushOh('о');PushOh('в');
writeln('Bg = ',Bg,' Ko = ',Ko); (* Bg = 5; Ko = 6; Oh = 'ов***Иван' *)
PushOh('а');
writeln('Bg = ',Bg,' Ko = ',Ko); (* Bg = 5; Ko = 7; Oh = 'ова**Иван' *)
PopOh(A);
writeln('Bg = ',Bg,' Ko = ',Ko); (* Bg = 6; Ko = 6; Oh = 'ова***ван' *)
writeln(' A = ',A);
while not EmpOh do begin
PopOh(A);
write(A)
end;
writeln;
writeln('Bg = ',Bg,' Ko = ',Ko);
(* ... *)
end.
(* Протокол Bg = 5 Ko = 0
Bg = 5 Ko = 6
Bg = 5 Ko = 7
Bg = 6 Ko = 6
A = И
ванова
Bg = 3 Ko = 0
Конец протокола *)
|
(* Стек - последовательность (однотипных) элементов данных, в которой *) (* включение/выбор элементов выполняются на одном конце последовательности *) (* *) (* Основные операции: (* - включить в стек новый элемент; Push *) (* - выбрать элемент из стека; Pop *) (* + породить пустой стек; Born *) (* + проверить наличие элементов в стеке. Emp *) |
(* Пример. Быстрая сортировка методом свечи целочисленного массива. *) (* Пусть MACC = array [1..2200] of integer; *) (* K - количество элементов в массиве A : MACC *) |
(* Рекурсивная реализация *)
procedure Rord(var A : MACC; K : integer);
procedure MEH(L,R : integer);
var Z : integer;
begin Z:=A[L];
A[L]:=A[R];
A[R]:=Z
end;
function Candle(H,K : integer) : integer;
label 777;
var Hp,Kp,I,X : integer;
begin X:=A[H]; (* Представитель A[H..K] *)
Hp:=H; Kp:=K;
777: while A[Hp] < X do Hp:=Hp+1;
for I:=Kp downto Hp do
if not(X <= A[I]) then begin
Kp:=I;
MEH(Hp,Kp);
goto 777
end;
Candle:=Hp
end;
procedure RE(H,K : integer);
var M : integer;
begin if K-H+1 <= 1 then else begin
M:=Candle(H,K);
if M = H then RE(H+1,K) else begin
RE(H,M-1);
RE(M, K)
end
end
end;
begin RE(1,K) end; (* of Rord *)
|
(* Реализация с помощью стека *)
procedure Uord(var A : MACC; K : integer);
var SK : array [1..200,1..2] of integer;
H,SP : integer;
procedure PUSH(H,K : integer);
begin SP:=SP+1;
SK[SP,1]:=H;
SK[SP,2]:=K end;
procedure POP(var H,K : integer);
begin H:=SK[SP,1];
K:=SK[SP,2];
SP:=SP-1 end;
procedure MEH(L,R : integer);
var Z : integer;
begin Z:=A[L];
A[L]:=A[R];
A[R]:=Z
end;
function Candle(H,K : integer) : integer;
label 777;
var Hp,Kp,I,X : integer;
begin X:=A[H]; (* Представитель A[H..K] *)
Hp:=H; Kp:=K;
777: while A[Hp] < X do Hp:=Hp+1;
for I:=Kp downto Hp do
if not(X <= A[I]) then begin
Kp:=I;
MEH(Hp,Kp);
goto 777
end;
Candle:=Hp
end;
procedure Un(H,K : integer);
var M : integer;
begin if K-H+1 <= 1 then else begin
M:=Candle(H,K);
if M = H then PUSH(H+1,K) else begin
PUSH(H,M-1);
PUSH(M, K)
end
end
end;
begin SP:=0; (* Инициализация стека *)
PUSH(1,K); (* Исходная задача *)
while 0 < SP do begin (* Пока стек не пуст *)
POP(H,K);
Un(H,K)
end
end;
|