На этом шаге мы дадим краткую характеристику стека и наметим план дальнейшего изложения.
Стек представляет собой коллекцию объектов, которая поддерживает быструю семантику доступа "последним пришел - первым ушел" (LIFO - last in, first out) для вставок и удалений. В отличие от списков или множеств, стеки, как правило, не допускают произвольного доступа к объектам, которые они содержат. Операции вставки и удаления также нередко называются вталкиванием (push) и выталкиванием (pop).
Полезной аналогией для стековой структуры данных из реального мира является стопка тарелок.
Новые тарелки добавляются на вершину стопки. И поскольку тарелки дорогие и тяжелые, можно взять только самую верхнюю тарелку (метод "последним пришел - первым ушел"). Чтобы добраться до тарелок, которые находятся внизу стопки, необходимо поочередно удалить все тарелки, которые находятся выше.
Стеки и очереди похожи. Обе эти структуры данных являются линейными коллекциями элементов, и разница между ними состоит в порядке доступа к элементам.
В случае с очередью вы удаляете элемент, который был добавлен в нее раньше всех (метод "первым пришел - первым ушел", или FIFO); однако в случае со стеком вы удаляете элемент, который был добавлен в него позже всех (метод "последним пришел - первым ушел", или LIFO).
С точки зрения производительности предполагается, что надлежащая реализация стека будет занимать O(1) времени на операции вставки и удаления.
Стеки находят широкое применение в алгоритмах, например в синтаксическом анализе языка и управлении рабочей памятью времени исполнения ("стек вызовов"). Короткий и красивый алгоритм с использованием стека представлен поиском в глубину (DFS) на древовидной или графовой структуре данных.
Python поставляется с несколькими реализациями стека, каждая из которых имеет слегка отличающиеся характеристики. Сейчас мы их рассмотрим и сравним их характеристики.
На следующем шаге мы рассмотрим класс list.
