Стек - одна из простейших и в тоже время основных структур данных в информатике. Эта структура данных часто встречается как в програмном обеспечении, так и на аппаратном уровне. Существует множество вариаций стека для решения различных задач. В этом разделе будет рассмотрен простейший стек с его базовыми операциями.
Стек как структура данных призвана хранить данные в заданном порядке и с определёнными правилами взаимодействия с данными. Эта структура данных представляет собой коллекцию элементов данных с принципом доступа к ним - LIFO (Last In First Out). Т.е. первый вставленный в стек элемент будет доступен последним на извлечение из стека.
Стек наиболее близок по своему поведению к стопке книг или тарелок. Рассмотрим работу стека и его особености на примерах.
Для наглядности рассмотрим работу со стеком на примере стопы тарелок на столе. В начальный момент времени Стек, т.е стол пустой, на нём нет ни одной тарелки:
Для нас, как разработчиков программного обеспечения необходимо понимать, что в начальный момент времени у нас есть контейнер, место, где можно хранить наши объекты. Предствим, что у нас есть абстракция (класс), которая реализует класс стека.
class Stack:
...-
Попробуем положить тарелку в нашу стопу:
Теперь на стол (стек) не пустой, на нём стоит одна тарелка. Если проводоить аналогию со стеком - в нём один элемет. Обычно, операция добавления элемента в стек называется PUSH. Метод push принемает одно значение - элемент, который нужно положить в стек и не возвращает ничего:
# ... def push(self, element): ...
Важно заметить, что хоть это и скрыто от пользователя, но добавление производится на "вершину" стека. Вершина - последний добавленый в стек элемент.
Можно проделывать операцию с добавлением элемента снова и снова. Размер стопы в таком случае будет расти и в определённый момент она станет не устойчивой и может упасть. В случае со стеком такая ситуация так же может возникнуть, что приведёт к ошибке переполнения стека.
-
Вершина - важнейшее понятие стека. Хоть это незаметно для пользователя, практически всё взаимодействие со стеком происходит через его вершину. Именно это и даёт возможность реализовать принцип LIFO. Для того чтобы посмотреть, какой элемент сейчас находится на вершине стека, реализуется операция TOP:
# ... def top(self) -> element: ...
Этот метод не изменяет стек, а лишь возвращает значение, лежащее на вершине стека.
-
Обратная операции добавлению - операция изъятия элемента из стека. Она так же имеет определённые ограничения. Представим, что нам нужно взять тарелку из стопы, мы, конечно, возьмём верхнюю, так как это самый простой выбор, который не приведёт к проблемам. Если мы попытаемся взять из середины, есть большой шанс разбить тарелки, уронив стопу. Так же в Стеке операция изъятия элемента производится только с вершины стека, т.е. изъяить можно только последний добавленый элемент.
-
Часто возникает необходимость определить размер стека, т.е. узнать, сколько элементов сейчас находится в стеке. Для этого в стеке есть операция size, которая возвращает целое число - количество элементов в стеке:
