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