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

Стек (Stack) – это структура данных, представленная в виде списка элементов, доступ к которым возможен только с одного конца списка.

Конец списка называется вершиной стека (Top). Первоначально, она устанавливается в -1. Это означает, что стек является пустым, т.е. в нем нет ни одного элемента.

При добавлении элемента в стек (Операция Push) его вершина увеличивается на единицу, и элемент вставляется в конец списка.

При удалении элемента из стека (Операция Pop) извлекается элемент, на который указывает вершина стека, и она сама уменьшается на единицу (рис. 1).

Рис. 1. Последовательность выполнения операций со стеком

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

Кроме операций добавления и удаления элементов в стеке предусмотрена операция чтения (Peek). При её выполнении возвращается значение элемента, который будет удален следующим, причем сам стек и его вершина не изменяются.

Определение стека допускает возможность существования неограниченно большого списка элемента. Реально построение такой структуры данных практически невозможно. Поэтому стек всегда имеет ограниченный размер (Size). По мере заполнения стека его размер может достичь максимального значения, и добавление следующего элемента станет невозможным. Условием возникновения такой ошибки (StackOverflow) является следующее равенство:

Top = Size – 1.

Аналогичная ошибка (Empty) происходит при попытке удаления или чтения элемента из пустого стека:

Top = –1.