Стек. Функциональная спецификация стека: LIFO и семь операций
Что это такое
Стек (stack) - упорядоченный набор данных с переменным числом элементов, доступ к которому возможен только с одного конца, называемого вершиной (top). Представьте стопку тарелок: положить новую тарелку можно только сверху, и взять тоже можно только верхнюю.
Отсюда главный принцип - LIFO, Last In - First Out: последним пришел, первым ушел. Элемент, который вы положили в стек последним, будет извлечен первым.
Зачем это нужно
Стек появляется везде, где важны вложенность и возврат к предыдущему состоянию:
- Вызов функций и рекурсия - при каждом вызове в стек сохраняются локальные переменные и адрес возврата.
- Разбор программ трансляторами - проверка скобок и вложенности блоков.
- Вычисление выражений - обратная польская запись, калькуляторы (подробно - в следующем уроке).
- Кнопка "Отменить" в редакторах - действия складываются в стек, Ctrl+Z снимает последнее.
Стек. Функциональная спецификация стека: семь операций
С математической точки зрения стек полностью описывается набором операций - это называется функциональной спецификацией. Она отвечает на вопрос, что умеет структура, не говоря ни слова о том, как она хранится в памяти.
- СОЗДАТЬ - порождает пустой стек.
- ПУСТО - проверяет, есть ли элементы (возвращает истину или ложь).
- ГЛУБИНА - возвращает текущее количество элементов.
- В_СТЕК (Push) - кладет новый элемент, он становится вершиной.
- ИЗ_СТЕКА (Pop) - убирает верхний элемент. Это "разрушающее чтение": посмотрели - и элемента больше нет.
- ВЕРХ (Top) - показывает верхний элемент, не трогая его.
- УНИЧТОЖИТЬ - удаляет стек целиком.
Важное свойство: стек инвертирует порядок. Положите по очереди 1, 2, 3 - и достанете 3, 2, 1. Это не побочный эффект, а инструмент: например, так удобно разворачивать последовательности.
Тренажер: операции стека по шагам
Выполним над пустым стеком цепочку операций Push 5, Push 3, Push 8, Top, Depth, Pop, Pop, Push 1, Pop, Pop и проследим, что происходит с вершиной.
list.append(x) - это Push, list.pop() - это Pop, и обе операции
работают за O(1), потому что списки Python оптимизированы для работы с концом.
Конец списка и есть вершина стека.
Интерфейс стека на C
На C функциональная спецификация превращается в заголовочный файл: набор объявлений функций без тел. Обратите внимание - здесь нет ни массивов, ни указателей на узлы. Как именно хранить элементы, решится позже, и пользователю стека это знать не нужно:
#include <stdbool.h>
typedef int T; /* тип элемента */
typedef struct Stack Stack;
/* Интерфейс стека (функциональная спецификация) */
void Create(Stack* s);
bool Empty(Stack* s);
int Depth(Stack* s); /* ГЛУБИНА */
void Push(Stack* s, T element); /* В_СТЕК */
void Pop(Stack* s); /* ИЗ_СТЕКА: убирает верхний элемент */
T Top(Stack* s); /* ВЕРХ: смотрит, не убирая */
void Destroy(Stack* s);Коротко: главное
- Стек - структура данных с доступом только к одному концу, вершине.
- Принцип LIFO: последний добавленный элемент извлекается первым.
- Стек инвертирует порядок проходящих через него элементов.
- Операции: Create, Empty, Depth, Push, Pop (разрушающее чтение), Top, Destroy.
- Применение: рекурсия и вызовы функций, разбор скобок, вычисление выражений.
Проверьте себя
В пустой стек по очереди положили буквы А, Б, Ц. В каком порядке они будут извлечены?