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

Стек (stack) — это структура данных, которая работает по принципу "последним пришел, первым вышел" (LIFO - last in, first out), что означает, что последним добавленный элемент будет первым удаленным.

Структура стека представляет собой набор элементов, связанных друг с другом в линейном порядке. Она состоит из двух основных операций: добавления элемента в стек (push) и извлечения последнего добавленного элемента (pop).

При добавлении нового элемента он помещается наверх стека, вершиной, а при извлечении, верхний элемент удаляется из стека. Также возможен доступ к верхнему элементу без его извлечения (peek).

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

Пример реализации стека на языке Python с использованием списка:

python
stack = []  # инициализация стека
# добавление элемента в стек
stack.append("A")
stack.append("B")
stack.append("C")
print(stack)  # вывод содержимого стека: ["A", "B", "C"]
# извлечение элемента из стека
item = stack.pop()
print(item)  # вывод удаленного элемента: "C"
print(stack)  # вывод обновленного содержимого стека: ["A", "B"]

В данном примере был создан пустой список, который представляет собой стек. Операция добавления элемента в стек осуществляется методом `append()`, а операция удаления, соответственно, методом `pop()`. В конечном итоге мы получаем стек, содержащий элементы "A" и "B".