Структура данных СТЕК

Стек – упорядоченный набор данных, в котором размещение новых элементов и удаление существующих производится только с одного его конца, который называют вершиной стека, т.е. стек – это список с одной точкой доступа к его элементам. Графически это можно изобразить так:

Стек – структура типа LIFO (Last In, First Out) – последним вошел, первым выйдет. Стек получил свое название из-за схожести с оружейным магазином с патронами (обойма): когда в стек добавляется новый элемент, то прежний проталкивается вниз и временно становится недоступным. Когда же верхний элемент удаляется из стека, следующий за ним поднимается вверх и становится опять доступным.

Максимальное число элементов стека ограничивается, т.е. по мере вталкивания в стек новых элементов память под него должна динамически запрашиваться и освобождаться также динамически при удалении элемента из стека. Таким образом, стек – динамическая структура данных, состоящая из переменного числа элементов одинакового типа.

Состояние стека рассматривается только по отношению к его вершине, а не по отношению к количеству его элементов, т.е. только вершина стека характеризует его состояние.

Операции, выполняемые над стеком, имеют специальные названия:

push – добавление элемента в стек (вталкивание);

pop – выталкивание (извлечение) элемента из стека, верхний элемент стека удаляется (не может применяться к пустому стеку).

Кроме этих обязательных операций часто нужно прочитать значение элемента в вершине стека, не извлекая его оттуда. Такая операция получила название peek.

Рассмотрим основные алгоритмы работы со стеком, взяв для простоты в качестве информационной части целые числа, хотя информационная часть может состоять из любого количества объектов допустимого типа, за исключением файлов.