Стек — это абстрактный тип данных и структура данных, которая организована по принципу LIFO (последним пришел, первым ушел). Это означает, что элемент, добавленный последним будет удален в первую очередь. Стек позволяет выполнять две операции push и Pop. Push добавляет элемент на вершину стека и Pop удаляет элемент из вершины стека.
Применение стека
Вычисление выражений
Стек используется для оценки префиксных, постфиксных и инфиксных выражений.
Преобразование выражений
Выражение можно представить в префиксной, постфиксной или инфиксной нотации. Стек может быть использован для преобразования одной формы выражения в другую.
Синтаксический разбор
Многие компиляторы используют стек для синтаксического разбора выражений, на низком уровне кода.
Поиск с возвратом
Предположим, что мы должны найти путь в лабиринте для решения проблемы. Мы выбираем путь и после этого понимаем, что этот путь неправильный. Теперь нам нужно вернуться к началу пути, чтобы начать новый путь. Это может быть сделано с помощью стека.
Проверка скобок
Стек используется, чтобы проверить правильность открытия и закрытия скобок.
Реверсирование строки
Стек используется для смены строки. Мы посылаем символы строки по одному в стек, а затем символы всплывают из стека.
Вызов функции
Стек используется для сохранения информации об активной функции или подпрограммы.
Существуют и другие виды применения стека. Если вам довелось с ними столкнуться пишите в комментариях.
