Void stack::Push(int NewElement){

// поместить в стек значение NewElement

if(v>=MAXSTACK){

// переполнение

OverFlow=true;

return;

}

A[++v]=NewElement;

Empty=false;

}

//-----------------------------------

Int stack::Pop(){

int p=-1; // -1 возвращается, если стек пуст

If(!Empty){

p=A[v--];

if(v<0){

Empty=true;

}

}

return p;

}

2.1. Применения стека

2.1.1. Программный стек

Многие компиляторы языков программирования (в частности компиляторы Си и Си++) используют так называемый программный стек для размещения аргументов под­про­грамм (функций) и локальных переменных. Программный стек – некоторая область памяти, используемая программой для размещения своих объектов. Рас­смот­рим в качес­тве примера следующую программу, состоящую из трех функций – main, f1, f2.

Void main(void){

char x,y;

int z;

// 1

x=f1(x,z); // 3

………………………………………………

z=f2(z); // 7

}

//---------------------

char f1(char t, int u){

float q;

// 2,5

…………………………………………………

}

//---------------------

int f2(int k){

char p=7;

// 4

p=f1(1,2); // 6

………………………………………………………

}

В процессе работы, программа проходит ряд точек, отмеченных в программе комментариями:

• 1 – после входа в функцию main

• 2 – после входа из main в f1

• 3 –после выхода из f1 в main

• 4 –после входа в f2 в main

• 5 – после входа в f1 из f2

• 6 – после выхода из f1 в функции f2

• 7 – после выхода из f2 в функции main

При входе в функцию программа помещает в программный стек значения аргументов в байты памяти, отводимой для параметров и локальных перемен­ных, после чего вершина стека поднимается (Push). При выходе из функции, вершина стека опускается до уровня, предшествующего входу (Pop). В таблице 1 изображено состояние стека в различных точках программы. По горизонтали – адреса байтов программного стека, по вертикали – номера точек.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
1	x	y	z
2	x	y	z				t	u				q
3	x	y	z
4	x	y	z				k				p
5	x	y	z				k				p	t	u				q
6	x	y	z				k				p
7	x	y	z

Таблица 1. Состояние стека в процессе выполнения программы

Примечания:

• здесь не учитывается выравнивание адресов на границу слова, двойного слова,

• длина типа int – 4 байта,

• не учитывается что адрес точки возврата при обращении к функции тоже помещается в стек.

Использование механизма программного стека для распре­де­ле­ния памяти для параметров и локальных переменных (класс памяти automatic) приводит к тому, что никаких дополнительных усилий для реализации рекурсии уже не требуется. Каждое новое обращение к рекурсивной функции помещает в стек новое поколение параметров и локальных переменных.