Стек (Stack) — что это и как используется?
Понятие стека часто упоминается в связке с другим алгоритмическим понятием, «рекурсией». Но использоваться он может во множестве разных случаев. Давайте рассмотим, что это такое и как может пригодиться в разработке программ.
Что такое стек
Что же такое стек? Процитирую Википедию:
Стек (англ. stack — стопка; читается стэк) — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
Итак, это структура данных, в которой элементы «складываются» только с одной стороны, друг на друга, а извлекаются в обратном порядке.
Простейшим примером стека в реальной жизни может быть обойма пистолета: патроны в нее вставляются сверху друг за другом, а вынимаются (или выстреливаются) затем начиная с верхнего. То есть чтобы добраться до первого добавленного в стек элемента, нужно вынуть все положенные следом за ним.
На рисунке выше изображена схема стека. Как видно, чтобы извлечь элемент 1, нужно сначала извлечь элементы 2, 3, 4 и 5 (если он будет положен в стек).
Методы
У стека обычно два основных метода - pop и push. Первый извлекает верхний элемент, а второй добавляет новый.
Где применяется стек
Для многих может быть интересным и неожиданным фактом, что стек в компьютерной технике применяется очень часто, и при работе со многими программами мы все так или иначе им пользовались. Например, самым известным примером стека может быть «стек вызовов» — понятие, применяемое при объяснении рекурсии. Если рассматривать другие области его применения — то здесь нет никаких ограничений, это может быть что угодно, начиная от списка задач, которые нужно выполнять в порядке добавления, и заканчивая любыми другими решаемыми задачами.
Как написать стек на языке программирования
Думаю, что рассматривать написание стека на одном из языков не имеет особого смысла, так как для его реализации можно воспользоваться разными способами, один из которых — уже рассмотренный ранее связный список.