Стек является распространенной и простой структурой данных, используемой в целом ряде приложений: обработке языков, поиске на графах и так далее. Например, вычисление выражений в калькуляторе с графическим интерфейсом, который будет представлен в следующей главе, в значительной степени опирается на манипулирование стеками. Языки программирования в целом обычно реализуют вызовы функций как операции со стеком, на котором запоминается местоположение в программе, откуда следует продолжить выполнение после возврата из функции. Стеки также могут использоваться при синтаксическом анализе документов XML: они естественным образом подходят для отслеживания движения по произвольно вложенным конструкциям.
Вкратце, стек представляет собой коллекцию объектов, построенную по принципу «последним пришел, первым ушел»: элемент, добавленный в коллекцию последним, всегда оказывается следующим удаляемым. В отличие от очередей, которые мы использовали для организации взаимодействий с потоками выполнения и которые добавляют и удаляют объекты с противоположных концов, все операции со стеком происходят на его вершине. Клиенты используют следующие операции со стеками:
• Проталкивание элементов на вершину стека (pushing).
• Выталкивание элементов с вершины стека (popping).
В зависимости от требований клиентов, могут также иметься средства решения таких задач, как проверка наличия элементов в стеке, извлечение верхнего элемента без его выталкивания, обход элементов стека, проверка наличия в стеке некоторого элемента и так далее.
Использованная литература:
Марк Лутц — Программирование на Python, 4-е издание, II том, 2011
