Стек. Структура и принцип работы

Курс по структурам данных: https://stepik.org/a/134212

Мы продолжаем курс по структурам данных. На этом занятии речь пойдет о следующей структуре под названием стек.

Идея стека состоит в организации данных по принципу очереди LIFO (Last in, First Out): последним вошел, первым вышел. Например, так можно организовать историю посещения страниц в браузере для определенной вкладки.

И здесь, естественно, возникает вопрос: чем стек отличается от очереди LIFO? В действительности, особо ничем. Стек – это и есть организация данных по принципу этой очереди. Но небольшое отличие, правда есть. Функционал стека позволяет только читать значение верхнего элемента, добавлять/удалять только элементы сверху. Например, перейти к произвольному элементу стека и получить его значение уже не получится. Тогда, как в очередях такая возможность имеется. То есть, стек – это все та же очередь, но с более ограниченным функционалом.

Зачем тогда вообще выделили стек в отдельную структуру данных? Использовали бы вместо него очередь типа LIFO и функционал бы был шире? Дело в том, что на практике встречается довольно много задач, где данные удобно представлять в виде стека и при этом не предполагается произвольный доступ к другим элементам и работа с ними. Поэтому, чтобы в программе подчеркнуть, что используется именно стек, а не просто очередь LIFO и выделили отдельно эту структуру данных.

В программах стек (равно, как и очереди) часто реализуют на базе односвязного или двусвязного списка. На вершину стека ссылается указатель top. Через него и выполняется обработка элементов стека. Однако стек можно реализовать на основе любых других подходящих структур данных, например, динамического массива с добавлением и удалением последних элементов:

В результате, стек можно рассматривать, как некую абстрактную структуру данных, в которой возможна работа только с верхним (последним) элементом, и которая может быть реализована на базе любой подходящей (не абстрактной) структуры данных (связные списки, динамические массивы).

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

Приведу несколько примеров, где активно применяют стек. Наверное, самый распространенный случай – это стек вызова функций. Смотрите, когда одна функция вызывает другую, например, так:

def main():
    a = 5
    print("a = " + str(a))
    b = 4

То здесь сначала вызывается функция main(), а затем, она вызывает другую функцию print(). Причем, обе функции в момент вызова продолжают работать. Затем, завершается функция print() и только потом – функция main(). Чтобы программа «знала» в каком порядке были вызваны функции и в каком порядке их следует завершать, как раз и используется стек вызова функций. В момент вызова функции main она помещается наверх стека. Затем, когда очередь доходит до функции print, эта функция помещается наверх стека. После отработки функции print, она извлекается из стека, т.к. находится на самом верху. А после завершения функции main стек становится пустым. На самом деле в реальном стеке вызова хранится много других функций, но для примера мы ограничились двумя.

Следующий пример – анализ данных с помощью стека. Предположим, у нас записано некоторое математическое выражение:

78 * (23 - 7 * (1 - 4)) + (95 / 5)

и требуется выделить фрагменты во всех круглых скобках. Как это сделать? Один из эффективных подходов – воспользоваться стеком. Вначале мы посимвольно анализируем выражение. И как только встречается открывающаяся круглая скобка, то записываем ее индекс в стек. Далее, встречается следующая открывающаяся круглая скобка. Снова заносим ее индекс в стек. Идем дальше по строке и видим закрывающуюся круглую скобку. В этом случае извлекаем из стека верхний объект, читаем значение индекса и выделяем фрагмент (срез) в диапазоне индексов [start+1:end). Для следующей закрывающейся круглой скобки делаем то же самое, но с очередным верхним объектом стека. В результате у нас выделяются нужные фрагменты.

Существует масса других задач, где используются стеки, например, заливка областей произвольной формы, построение фрактальных кривых с помощью L-систем и так далее. Часто там, где возникает некая иерархия работы алгоритма, удается эффективно решить задачу с использованием стека.

Методы стека

Я думаю, что общая структура стека вам понятна. Давайте теперь посмотрим на основные методы, которые, как правило, поддерживаются стеком:

Метод

Описание

Сложность

top()

Возвращает значение верхнего элемента стека

O(1)

push()

Добавляет новый элемент на вершину стека

O(1)

pop()

Удаляет элемент с вершины стека

O(1)

size()

Возвращает число элементов в стеке

O(1)

empty()

Возвращает True, если стек пуст, и False в противном случае

O(1)

Вот общая идея работы стека. На следующих занятиях мы увидим, как реализована эта структура данных на языках С++ и Python.

Курс по структурам данных: https://stepik.org/a/134212

Видео по теме