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

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

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

Пример. Рассмотрим последовательные этапы засылки с стек чисел 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 к пустому стеку.

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