Что такое “стек”?¶
Стек (иногда говорят “магазин” - по аналогии с магазином огнестрельного оружия) - это упорядоченная коллекция элементов, где добавление нового или удаление существующих всегда происходит только на одном из концов. Этот конец обычно называют “вершиной”, а противоположный ему - “основанием”.
Важность основания стека в том, что хранящиеся ближе к нему элементы представляют из себя те, что находятся в стеке дольше всего. Элемент, добавленный последним, расположен на той позиции, с которой будет удалён в первую очередь. Такой принцип организации иногда называется LIFO, last-in first-out (англ. «последним пришёл — первым вышел»). Он предоставляет упорядочение по длительности нахождения в коллекции. Более новые элементы расположены ближе к вершине, в то время как более старые - ближе к основанию.
С примерами стека мы сталкиваемся ежедневно. Едва ли не каждая закусочная имеет стопку из подносов или тарелок, где вам нужно брать одну сверху, открывая новый поднос или тарелку для следующего посетителя в очереди. Вообразите стек из книг на столе (Рисунок 1). Единственной книгой, чья обложка видна, является самая верхняя. Чтобы получить доступ к остальным в стопке, нам нужно удалить лежащую поверх остальных. Рисунок 2 демонстрирует другой стек, содержащий несколько простых объектов данных Python.
Рисунок 1: Стек из книг
Рисунок 2: Стек из простых объектов Python
Одна из наиболее часто используемых идей, связанных со стеком, пришла из простого наблюдения за тем, как добавляются и удаляются его элементы. Предположим, что вы начинаете с чистого стола. Теперь кладите книги по одной за раз друг поверх друга. Вы конструируете стек. Посмотрим, что случится, когда вы начнёте их удалять. Очерёдность, в которой это будет происходить, в точности противоположна тому, как они клались. Стеки фундаментально важны, поскольку их можно использовать для реверсирования порядка элементов. Последовательность вставок противоположена последовательности удалений. Рисунок 3 показывает стек из объектов данных Python в процессе его создания и удаления из него элементов. Обратите внимание на порядок объектов.
Рисунок 3: Свойство реверсирования у стеков
Рассматривая это реверсивное свойство, вы, возможно, подумаете о примерах стека, имеющих место в процессе использования вами компьютера. Например, каждый веб-браузер имеет кнопку “Назад”. Когда вы перемещаетесь от одной веб-страницы к другой, они помещаются в стек (точнее, в стек помещаются их URL’ы). Текущая страница, которую вы просматриваете, находится на вершине, а самая первая из просмотренных - в основании. Если вы нажмёте кнопку “Назад”, то начнёте перемещаться по страницам в обратном порядке.