Что такое “стек”?¶

Стек (иногда говорят “магазин” - по аналогии с магазином огнестрельного оружия) - это упорядоченная коллекция элементов, где добавление нового или удаление существующего всегда происходит только на одном из концов. Этот конец обычно называют “вершиной”, а противоположный ему - “основанием”.

Значимость основания стека заключается в том, что хранящиеся ближе к нему элементы представляют из себя те, которые находятся в стеке дольше всего. Элемент, добавленный последним, расположен на той позиции, с которой будет удалён в первую очередь. Такой принцип организации иногда называется LIFO, last-in, first-out (англ. «последним пришёл — первым вышел»). Он предоставляет упорядочение по времени нахождения в коллекции. Более новые элементы расположены ближе к вершине, более старые - ближе к основанию.

С примерами стека мы сталкиваемся ежедневно. Едва ли не каждая закусочная имеет стопку из подносов или тарелок, где вам нужно брать одну сверху, открывая новый поднос или тарелку для следующего посетителя в очереди. Вообразите стек из книг на столе (рисунок 1). Единственной книгой, чья обложка видна, является самая верхняя. Чтобы получить доступ к остальным в стопке, нам нужно удалить лежащую поверх остальных. Рисунок 2 демонстрирует другой стек, содержащий несколько простых объектов данных Python.

Рисунок 1: Стек из книг

Рисунок 2: Стек из простых объектов Python

Одна из наиболее часто используемых идей, связанных со стеком, пришла из простого наблюдения за тем, как добавляются и удаляются его элементы. Предположим, вы начинаете с чистого стола. Теперь кладите книги по одной за раз друг поверх друга. Вы конструируете стек. Посмотрим, что случится, когда вы начнёте их удалять. Очерёдность, в которой это будет происходить, в точности противоположна тому, как они клались. Стеки фундаментально важны, поскольку их можно использовать для реверсирования порядка элементов. Последовательность вставок противоположена последовательности удалений. Рисунок 3 показывает стек из объектов данных Python в процессе его создания и удаления из него элементов. Обратите внимание на порядок объектов.

Рисунок 3: Свойство реверсирования у стеков

Рассматривая это реверсивное свойство, вы, возможно, подумаете о примерах стека, имеющих место при работе с компьютером. Например, каждый веб-браузер имеет кнопку “Назад”. Когда вы перемещаетесь от одной веб-страницы к другой, они помещаются в стек (точнее, в стек помещаются их URL’ы). Текущая страница, которую вы просматриваете, находится на вершине, а самая первая из просмотренных - в основании. Если вы нажмёте кнопку “Назад”, то начнёте двигаться по страницам в обратном порядке.