Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

Области применения стеков такие же, как и у очередей: Системные —
передача процедурам и функциям аргументов по значе—



— сохранение и восстановление содержимого регистров об- щего назначения процессора при вызове процедур (проло- ги и эпилоги функций).
Прикладные —
стековая (магазинная) память, например в языке програм- мирования Forth,
вспомогательные структуры данных (например, при поис- ке в графе).
Примеры стеков. Второе название стека — магазин, — при- водит к механическому примеру стека магазин стрелкового оружия. Ещё один простой пример — стакан.
Стеки, также как и очереди, могут реализовываться при по- мощи одномерных массивов или связпы.v cппcкos.
HHme npiiBe@ HMI npHMe]3si npouenyp saHéCéHHII n H3BJIéUéHHII
QIIHHI›IX QJIJI CT KiI HiI OCHOB MIIGCHB I HH II3I›IKIIX IICKIIJII› H THIS.
HporpaMMI1 ]3II60ThI CO CTéKOM HH II3hIKé IICKlIJIh.

Programm Stack Test; const N=30;

var
stack: array[0..N] of char; slen, pos: integer;

procedure push(i:char);

begin
if pos < slen then begin
stack[pos] := i; pos := pos = 1
end else
writelo( 'Crew noioH.')
end;

function pop() :char;

begin
if pos=0 then begin
writeln(' Crew nyci. ');
PYP ⁰
end
else
begin
pos := pos - 1;
pop := stack[pos]
end; end:

P O S — HHQéKC GnepyioiiieJJ OTK]3hITO$J nO3HIJHH — Bé]3IIIHHhI CTé-

KH. Ecuii Po s 6c›JIsIiié HH,IJéKCIl nocné@HéFo coxpaHeHHll, 3HtlUHT CTéK 3lIHOJIHéH; écJIH P O S = — CTex nycT.
84

begin
slen N;
pos 0; push('A');
push(' B');
push('C');
PYP()•
push('D');
P P()•
PYP()•
P P()•
end.



A

2. 
   A
   
3. 
   B A
   

{Bo3Bpayaei C} B A

2. 
   B A
   

{Bo3Bpaiaei D} B A
{Bosepamaei B} A
{BO3Bpamaei A} View nyci

AHanorriuHas nporpavvll HU II3hIKé Sri++.

#include using namespace std; const int N = 30; char stack[N];

int pos = O ,slen = N;

// *aHeCeHXe 3LeMeHTa B CTeK.

void Push(char i)
if (pos == slen) cout<<” Ciex noiOH!\n”,
return;

stack[pos] = i;

// %3BLeUeHUe 3LeMeHTa X3 CTeKa.
char Pop()

if (pos == 0)

85

cout<<"Cтeк пуст.\п", return 0;

return stack[pos];
int maiп() Содержимое

Push('A'); Push('B');				А В	А
Push('C'); cout>>Pop()>>endl; Push('F'); cout>>Pop()>>'\n';	// //	Возвр. Возвр.	С F	С В F В	В А А В А А
cout>>Pop()>>endl;	//	Возвр.	В	А
return 0;

Представим стек, как динамическую цепочку звеньев, т.е. склзны й сппсок. Первое звено — вершина. Так как доступна толь- ко вершина, то в таком списке главное звено становится излиш- ним. Стек как единый объект представляет указатель, значение его адрес вершины стека. Каждое звено цепочки содержит ука- затель на следующее звено, «дно» стека — элемент, занесенный первым, имеет этот указатель равным ni 1.
Программа работы с динамическим стеком на языке Пас—
каль.

Programm Stack Test;

type (* Секция описания типов *) stype = real;
next = ’elem;

elem=record
dr: next; data: stype
(* Запись *)

var
end;
stack = next; р: stack;

86

procedure push(var st: stack; newl: stype); var

q:next; begin
new(q);
q’.data := newl; q’.dr := st;
(* HOBOe 3BeHO *)

end;
st := q;

(* HOBOe 3BeHO - Be lUHa ’)

function pop(var st: stack) :stype; var

q:next;
begin
if st = nil then
writeln(' Crew nyci.')
else
begin
pop := st’.data; q st;
st := st’.dr; dispose(q)
end;
end;

var P: stack;

EcJIH GTeK nycT, TO 3HflUéHHe yKasllTéJIII P pIIBHO II i 1. K HflUfl- my Hcnoas3OBllHHlf CTéKa ero HymHo GpeJIIITs nycTsIM H]9H HOMO H One]3iITOpa p := n i 1.

begin
p nil; push(p,43);

writeln(pop(p) :3:9); push(p,54); writeln(pop(p) :3:9);

87

readln;
end.

AHI1JIorHUHhIe npouepypsI HH II3hIKé in++.

typedef float stype; /* HeodesaieebHoe Mepe-

xMeHOBaHxe iuM) B xM n	TuMa float stype */	(vo*ei wCM Oeb3OBaTbCS	eA/O/
struct	elem

elem* dr; // yxasdTéH 6Haqpyro?TdKO?meaMéeéHT stype data; // xpaHxMbe B CTexe QaHHBe

void Push(elem*& st, stype newel) elem* q = new elem;

q->data = newel; // HOBoe sBeHO
q->dr = st;
s = q i / / HOBO 3B HO CTflHOBHTGll B ]3IIIHHO/J GT KH.

stype Pop(elem*& st) stype a;

elem *q;
if (st == NULL)

cout<<” Ciex nyci.\n", return;

a = st->data; q st;

st = st->dr; delete q; return a;