Стек в программировании: для чего нужен и как устроен

Стек — это тип структуры данных, где обработка элементов происходит по принципу LIFO. Это означает «последний пришёл — первый ушёл» (англ. Last In, First Out). Иными словами, элемент, добавленный последним, извлекается первым.

Чтобы понять, как работает стек, представим бильярдную лузу, куда по одному падают шары. Первый шар оказывается в самом низу, а каждый следующий ложится поверх предыдущего. Если понадобится шар, получится взять только тот, что сверху. Чтобы добраться до нижних, придётся сначала вынуть все верхние — один за другим. Это и есть принцип LIFO: доступен только последний элемент, все остальные — временно недоступны.

Разобраться в особенностях стека и других структур можно на курсе «Алгоритмы и структуры данных». Студенты учатся писать эффективный код и готовятся к алгоритмическим задачам на собеседованиях.

Понятие стека описал в 1946 году математик и криптограф Алан Тьюринг. Через несколько лет немецкий информатик Фридрих Бауэр впервые предложил использовать стековую структуру в вычислительных машинах. Концепция оказалась настолько удачной, что легла в основу многих языков программирования и архитектур процессоров.

Особенность работы стека в том, что добавлять или удалять элементы можно только с одной стороны — с его вершины. Всё, что «ниже», временно недоступно, пока существуют верхние элементы.

Вот основные операции, которые можно производить со стеком:

● Push — добавляет новый элемент в стек.
● Pop — удаляет элемент, который находится сверху.
● Peek (или Top) — показывает верхний элемент стека, но не убирает его.
● Size — возвращает количество элементов, которые находятся в стеке.

Принцип LIFO описывает, как работает стек: сначала выходит тот элемент, который добавили последним. Это можно понять на примере браузера — разберём его подробнее.

Пользователь зашёл в браузер. Он открыл страницы в следующем порядке:

1. Зашёл на главную страницу Yandex.
2. Перешёл на страницу с результатами поиска.
3. Перешёл на конкретный сайт из списка результатов.

Теперь он нажимает кнопку «Назад». Браузер вернёт его на предыдущую страницу — ту, что была открыта последней перед текущей. Если он нажмёт «Назад» снова — окажется на ещё более ранней странице. В этом и заключается принцип работы стека. Каждая новая страница добавляется вверх стека (push), а кнопка «Назад» — это операция pop, которая убирает верхнюю страницу и показывает предыдущую. Точно так же принцип LIFO используется и в программировании: например, когда одна задача вызывает другую и нужно вернуться обратно после завершения.

Чтобы понять, как работает стек, важно разобраться, как он устроен внутри. На базовом уровне стек состоит из трёх элементов.

1. Хранилище данных. Это область памяти, где фактически лежат элементы. Она может быть:
● массивом фиксированной длины;
● динамическим списком или вектором;
● связным списком, где каждый элемент хранит ссылку на следующий.

2. Указатель на вершину стека. Это переменная top, которая указывает, где сейчас находится верхний элемент стека. Все операции push () и pop () работают именно с этой вершиной.

3. Размер стека. Часто стек ограничен по количеству элементов, особенно если используется в ограниченной памяти — например, стек вызовов функций в процессоре. Тогда нужно отслеживать, не превышен ли предел. Например, для защиты от Stack Overflow — переполнения стека.

Стек используют в программировании, операционных системах и даже в обычных пользовательских интерфейсах. Из-за своей простоты и принципа LIFO он подходит для задач, где нужно временно сохранять данные и возвращаться назад. Рассмотрим несколько примеров.

● Вызовы функций. Когда одна функция вызывает другую, она приостанавливается, а в стек помещается информация о том, куда нужно вернуться. После выполнения вложенной функции стек «отматывается» обратно.

Стек вызовов: a → b → c, потом обратно: c → b → a

● История действий в браузере. Каждый переход по ссылке сохраняется в стек. При нажатии «Назад» происходит pop () и открывается предыдущая страница.

● Отмена действий. В текстовых редакторах, например в Microsoft Word, каждое действие пользователя сохраняется в стек «отмен». При нажатии Ctrl + Z последние изменения извлекаются из стека и откатываются.

Например, человек напечатал «Статья», затем «Заголовок». Если он нажмёт Ctrl + Z, удаляется «Заголовок», затем — «Статья».

● Работа с выражениями и скобками. Используют при обработке арифметических выражений, особенно в компиляторах и интерпретаторах языков программирования. Так можно проверять правильность вложенных скобок или, например, вычислять значения выражений.

Например, проверка выражения (2 + (3 × 4)). Здесь стек помогает отследить, правильно ли открыты и закрыты скобки.

На уровне концепции стек — это линейная структура данных, в которой все операции происходят начиная с его вершины. Эту концепцию можно реализовать разными способами в зависимости от задачи, требований к производительности и ограничений по памяти.

● С помощью списка. Python предоставляет список list, у которого уже есть методы append () и pop (). Они подходят для создания стека:

Стек можно реализовать в коде с помощью списка

● Через класс. Чтобы лучше контролировать стек и делать код читаемым, часто создают собственный класс Stack. Это полезно, если стек будет частью более крупной программы, например интерпретатора или парсера.

Собственный класс помогает лучше контролировать стек

Стек — простая и полезная структура данных. Но у него есть свои ограничения и особенности.

● Доступ только с вершины. Концептуальная особенность стека — работа по принципу LIFO. Это значит, что получить доступ можно только к самому последнему добавленному элементу.

● Ограничение размера. В некоторых языках и системах у стека фиксированный объём памяти. Например, в низкоуровневых языках (C, C++).

● Особенности при многопоточности. В многопоточных приложениях доступ к стеку нужно контролировать. Если два потока используют стек одновременно, могут возникнуть ошибки из-за конфликта при обращении к данным.

Стек подходит не для всех задач. Если нужно больше гибкости, можно рассмотреть альтернативные структуры данных. Вот некоторые из них:

● Очередь — Queue. Работает по принципу FIFO — First In, First Out («первый вошёл — первый вышел»). То есть обрабатывается первым тот, кто пришёл первым. Подходит для обработки задач в порядке поступления — например, при печати документов, обслуживании клиентов.

● Двусторонняя очередь — Deque. Можно добавлять и удалять элементы с обеих сторон — и с начала, и с конца.

● Список — List или массив — Array. Доступ к элементам по индексу, произвольное размещение. Подходит, если нужно часто обращаться к элементам в середине либо по конкретному индексу или если нужна сортировка, фильтрация и другие гибкие операции.

● Связный список — Linked List. Элементы хранят данные и ссылку на следующий, а иногда и на предыдущий элемент. Подходит, если часто нужно вставлять или удалять элементы в середине списка.

● Деревья — Tree. Иерархическое хранение данных с узлами и подузлами. Нужны, если данные логически связаны как «родитель — потомок» — например, файловая система.

● Множество — Set. Хранят только уникальные элементы, без порядка. Можно использовать, когда нужно проверить, встречался ли элемент.