Стек ("магазин")

Начнем с рассмотрения примера. Пусть в трубку с запаянным концом закатываются шарики. Извлекать их можно только в обратном порядке: тот шарик, что закатился последним, будет извлечен первым.

Пример стека

Подобным образом можно организовать и данные. Стек – такая структура динамических данных, которая состоит из переменного числа компонент одинакового типа. Компоненты извлекаются из стека таким образом, что первой выбирается та компонента, которая была помещена последней. Извлеченная компонента в стеке не сохраняется.

Пример. Рассмотрим последовательные этапы засылки с стек чисел 1, 2, 3.

Заполнение стека

На этапе б) обращение к процедуре извлечения из стека дает число 2, на этапе в) – число 3.

Опишем стек, в который можно помещать цепочку динамических переменных:

type
	stackp = ^stackcomp;
	stackcomp = record
		I: integer;
		P: stackp
	end;
var
	S: stackp;

Если помещать в этот стек последовательность 1, 2, 3, то получится следующий вид:

Стек, состоящий из трех компонентов

Поместить в такой стек компоненту можно, например, процедурой SN:

S := nil;
…
procedure SN(k: integer);
	var 
		inew: stackp;
	begin
		{резервируется память под новую компоненту, 
		в inew засылается адрес этой компоненты}
		new(inew);
		with inew do begin
			I := k;
			P := S
		end;
		S := inew;
	end;

Если со стеком вида как на рисунке выше обратиться к процедуре SN для засылки числа 4, то получим стек вида:

Стек, состоящий из четырех компонентов

Процедура извлечения компоненты из такого стека может иметь следующий вид:

procedure OUT(var k: integer);
	var
		iold: stackp;
	begin
		iold := S;
		{значение последней компоненты}
		k := iold^.I;
		{извлекается и засылается в S значение
		соответствующего указателя на 3}
		S := iold^.P;
		dispose(iold);
	end;

После обращения к процедуре OUT стек вернется к первоначальному виду (1, 2, 3).

Пустым стеком называется стек, не содержащий компонент. Такой стек можно получить, присвоив значение Nil соответствующей ссылочной переменной (в нашем случае S := nil;).

Если к пустому стеку применить несколько раз процедуру SN, а затем столько же раз процедуру OUT, то получим снова пустой стек.

Замечание. Нельзя применять процедуру OUT к пустому стеку.

Стеки позволяют гибко и экономно использовать память, т.к. в каждый момент в стеке могут находиться только те переменные, которые нужны для дальнейшей работы программы. (В то время как под массивы, например, мы зачастую вынуждены резервировать и держать избыточную память.)