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

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

Рис. 8

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

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

Рис. 9

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

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

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

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

Если со стеком вида 1) обратиться к процедуре IN для засылки числа 4, то получим стек вида 2):

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

После обращения к процедуре OUT стек вернется к виду 1).

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

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

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

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