Ñòåêîì íàçûâàåòñÿ äèíàìè÷åñêàÿ ñòðóêòóðà äàííûõ, äîáàâëåíèå êîìïî-
íåíòû â êîòîðóþ è èñêëþ÷åíèå êîìïîíåíòû èç êîòîðîé ïðîèçâîäèòñÿ èç
îäíîãî êîíöà, íàçûâàåìîãî âåðøèíîé ñòåêà. Ñòåê ðàáîòàåò ïî ïðèíöèïó
LIFO (Last-In, First-Out) -
ïîñòóïèâøèé ïîñëåäíèì, îáñëóæèâàåòñÿ ïåðâûì.
Îáû÷íî íàä ñòåêàìè âûïîëíÿåòñÿ òðè îïåðàöèè:
-íà÷àëüíîå ôîðìèðîâàíèå ñòåêà (çàïèñü ïåðâîé êîìïîíåíòû);
-äîáàâëåíèå êîìïîíåíòû â ñòåê;
-âûáîðêà êîìïîíåíòû (óäàëåíèå).
Äëÿ ôîðìèðîâàíèÿ ñòåêà è ðàáîòû ñ íèì íåîáõîäèìî èìåòü äâå ïåðå-
ìåííûå òèïà óêàçàòåëü, ïåðâàÿ èç êîòîðûõ îïðåäåëÿåò âåðøèíó ñòåêà, à
âòîðàÿ - âñïîìîãàòåëüíàÿ. Ïóñòü îïèñàíèå ýòèõ ïåðåìåííûõ èìååò âèä:
var pTop, pAux: Pointer;
ãäå pTop - óêàçàòåëü âåðøèíû ñòåêà;
pAux - âñïîìîãàòåëüíûé óêàçàòåëü.
Íà÷àëüíîå ôîðìèðîâàíèå ñòåêà âûïîëíÿåòñÿ ñëåäóþùèìè îïåðàòîðàìè:
ÉÍÍÍÍÍ» ÉÍÍÍÍÍ»
New(pTop); º *ÄĺÄÄÄ¿ º º
ÈÍÍÍÍͼ ³ ºÍÍÍÍͺ
pTop ÀÄÄ>º º
ÈÍÍÍÍͼ
ÉÍÍÍÍÍ» ÉÍÍÍÍÍ»
pTop^.pNext:=NIL; º *ÄĺÄÄÄ¿ º º
ÈÍÍÍÍͼ ³ ºÍÍÍÍͺ
pTop ÀÄÄ>º NIL º
ÈÍÍÍÍͼ
ÉÍÍÍÍÍ» ÉÍÍÍÍÍ»
pTop^.D:=D1; º *ÄĺÄÄÄ¿ º D1 º
ÈÍÍÍÍͼ ³ ºÍÍÍÍͺ
pTop ÀÄÄ>º NIL º
ÈÍÍÍÍͼ
Ïîñëåäíèé îïåðàòîð èëè ãðóïïà îïåðàòîðîâ çàïèñûâàåò ñîäåðæèìîå
ïîëÿ äàííûõ ïåðâîé êîìïîíåíòû.
Äîáàâëåíèå êîìïîíåíòû â ñòåê ïðèçâîäèòñÿ ñ èñïîëüçîâàíèåì âñïî-
ìîãàòåëüíîãî óêàçàòåëÿ:
ÉÍÍÍÍÍ» ÉÍÍÍÍÍ» ÉÍÍÍÍÍ»
New(pAux); º *ÄĺÄÄÄ¿ º º ÚÄÄĺÄÄ* º
ÈÍÍÍÍͼ ³ ºÍÍÍÍͺ ³ ÈÍÍÍÍͼ
pTop ³ º º<ÄÄÙ pAux
³ ÈÍÍÍÍͼ
³
³ ÉÍÍÍÍÍ»
³ º D1 º
³ ºÍÍÍÍͺ
ÀÄÄ>º NIL º
ÈÍÍÍÍͼ
ÉÍÍÍÍÍ» ÉÍÍÍÍÍ» ÉÍÍÍÍÍ»
pAux^.pNext:=pTop; º *ÄĺÄÄÄ¿ º º ÚÄÄĺÄÄ* º
ÈÍÍÍÍͼ ³ ºÍÍÍÍͺ<ÄÄÙ ÈÍÍÍÍͼ
pTop ³ º *ÄĺĿ pAux
³ ÈÍÍÍÍͼ ³
³ ³
³ ÉÍÍÍÍÍ» ³
³ º D1 º ³
³ ºÍÍÍÍͺ ³
ÀÄÄ>º NIL º<Ù
ÈÍÍÍÍͼ
ÉÍÍÍÍÍ» ÉÍÍÍÍÍ» ÉÍÍÍÍÍ»
pTop:=pAux; º *ÄĺÄÄÄ¿ º º ÚÄÄĺÄÄ* º
ÈÍÍÍÍͼ ³ ºÍÍÍÍͺ<ÄÄÙ ÈÍÍÍÍͼ
pTop ÀÄÄ>º *ÄĺĿ pAux
ÈÍÍÍÍͼ ³
³
ÉÍÍÍÍÍ» ³
º D1 º ³
ºÍÍÍÍͺ ³
º NIL º<Ù
ÈÍÍÍÍͼ
ÉÍÍÍÍÍ» ÉÍÍÍÍÍ»
pTop^.D:=D2; º *ÄĺÄÄÄ¿ º D2 º
ÈÍÍÍÍͼ ³ ºÍÍÍÍͺ
pTop ÀÄÄ>º *ÄĺĿ
ÈÍÍÍÍͼ ³
³
ÉÍÍÍÍÍ» ³
º D1 º ³
ºÍÍÍÍͺ ³
º NIL º<Ù
ÈÍÍÍÍͼ
Äîáàâëåíèå ïîñëåäóþùèõ êîìïîíåíò ïðîèçâîäèòñÿ àíàëîãè÷íî.
Ðàññìîòðèì ïðîöåññ âûáîðêè êîìïîíåíò èç ñòåêà. Ïóñòü ê ìîìåíòó íà-
÷àëà âûáîðêè ñòåê ñîäåðæèò òðè êîìïîíåíòû:
ÉÍÍÍÍÍ» ÉÍÍÍÍÍ»
º *ÄĺÄÄÄ¿ º D3 º
ÈÍÍÍÍͼ ³ ºÍÍÍÍͺ
pTop ÀÄÄ>º *--ºÄ¿
ÈÍÍÍÍͼ ³
³
ÉÍÍÍÍÍ» ³
º D2 º ³
ºÍÍÍÍͺ ³
ÚĺÄÄ* º<Ù
³ ÈÍÍÍÍͼ
³
³ ÉÍÍÍÍÍ»
³ º D1 º
³ ºÍÍÍÍͺ
À>º NIL º
ÈÍÍÍÍͼ
Ïåðâûé îïåðàòîð èëè ãðóïïà îïåðàòîðîâ îñóùåñòâëÿåò ÷òåíèå äàííûõ
èç êîìïîíåíòû - âåðøèíû ñòåêà. Âòîðîé îïåðàòîð èçìåíÿåò çíà÷åíèå óêà-
çàòåëÿ âåðøèíû ñòåêà:
ÉÍÍÍÍÍ» ÉÍÍÍÍÍ»
D3:=pTop^.D; º *ÄĺÄÄÄ¿ º D3 º
pTop:=pTop^.pNext; ÈÍÍÍÍͼ ³ ºÍÍÍÍͺ
pTop ³ º º
³ ÈÍÍÍÍͼ
³
³ ÉÍÍÍÍÍ»
³ º D2 º
³ ºÍÍÍÍͺ
ÀÄÄ>º *ÄĺĿ
ÈÍÍÍÍͼ ³
³
ÉÍÍÍÍÍ» ³
º D1 º ³
ºÍÍÍÍͺ ³
º NIL º<Ù
ÈÍÍÍÍͼ
Êàê âèäíî èç ðèñóíêà, ïðè ÷òåíèè êîìïîíåíòà óäàëÿåòñÿ èç ñòåêà.
Ïðèìåð. Ñîñòàâèòü ïðîãðàììó, êîòîðàÿ ôîðìèðóåò ñòåê, äîáàâëÿåò â
íåãî ïðîèçâîëüíîå êîëè÷åñòâî êîìïîíåíò, à çàòåì ÷èòàåò âñå êîìïîíåíòû
è âûâîäèò èõ íà ýêðàí äèñïëåÿ,  êà÷åñòâå äàííûõ âçÿòü ñòðîêó ñèìâî-
ëîâ. Ââîä äàííûõ - ñ êëàâèàòóðû äèñïëåÿ, ïðèçíàê êîíöà ââîäà - ñòðîêà
ñèìâîëîâ END.
Program STACK;
uses Crt;
type
Alfa= String[10];
PComp= ^Comp;
Comp= Record
sD: Alfa;
pNext: PComp
end;
var
pTop: PComp;
sC: Alfa;
Procedure CreateStack(var pTop: PComp; var sC: Alfa);
begin
New(pTop);
pTop^.pNext:=NIL;
pTop^.sD:=sC
end;
Procedure AddComp(var pTop: PComp; var sC: Alfa);
var pAux: PComp;
begin
NEW(pAux);
pAux^.pNext:=pTop;
pTop:=pAux;
pTop^.sD:=sC
end;
Procedure DelComp(var pTop: PComp; var sC:ALFA);
begin
sC:=pTop^.sD;
pTop:=pTop^.pNext
end;
begin
Clrscr;
writeln(' ÂÂÅÄÈ ÑÒÐÎÊÓ ');
readln(sC);
CreateStack(pTop,sC);
repeat
writeln(' ÂÂÅÄÈ ÑÒÐÎÊÓ ');
readln(sC);
AddComp(pTop,sC)
until sC='END';
writeln('****** ÂÛÂÎÄ ÐÅÇÓËÜÒÀÒÎÂ ******');
repeat
DelComp(pTop,sC);
writeln(sC);
until pTop = NIL
end.