Анализ структур данных. Часть 2: Очередь, стек и хеш-таблица
Страница 4. Структура данных \"стек\"

Структура данных "стек": Первым пришел, последним обслужен (First Come, Last Served)

Очередь дает нам доступ к элементам в порядке "первым пришел, первым ушел" и использует для этих целей внутренний циклический массив object-ов. Такая функциональность предоставляется посредством методов Enqueue() и Dequque(). Порядок обработки "первым пришел, первым ушел" имеет много применений в реальных приложениях, таких как веб-серверы, очереди печати и прочих программах, ориентированных на обработку множественных запросов.

Другой популярной схемой обработки в компьютерных программах является подход "первым пришел, последним ушел". Структура данных, предоставляющая такой доступ к своим элементам, называется стек (или магазин - по аналогии с магазином автоматического оружия). Библиотека классов .NET Framework содержит класс System.Collections.Stack, который, подобно классу Queue, хранит свои элементы в циклическом массиве типа object. Управление данными, содержащимися в стеке, происходит с помощью метода Push(item) ("втолкнуть"), который помещает объект, переданный в качестве параметра в стек, и метода Pop() ("извлечь"), который возвращает объект из вершины стека, удаляя его из стека.

Графически стек можно изобразить в виде вертикальной "пирамиды" элементов. При "заталкивании" элемента в стек он помещается сверху над всеми прочими элементами. Извлечение элемента из стека, удаляет его свершины стека. Следующие 2 рисунка показывают стек после "заталкивания" в него элементов 1, 2, and 3 и последующего их удаления из стека.

Рисунок 5. Графическое представление стека из трех элементов

Рисунок 6. Графическое представление стека после извлечения элементов

Отметим, что размер стека по умолчанию устанавливается равным 10 элементам, в отличие от 32 элементов очереди. Однако, как и раньше с классами Queue и ArrayList, вы легко можете изменить это количество, задав его в конструкторе класса. Как и в случае с ArrayList-ом, когда возникает необходимость увеличить стек, его размер автоматически удваивается. (Вспомним, что у очереди фактор роста может быть задан в конструкторе)

Примечание Стеки часто называют структурами данных типа LIFO = Last In, First Out ("Последним вошел, первым вышел").

Стеки - желанные гости в Computer Science

Когда говорят об очередях легко и просто представить множество примеров из обычной жизни - очереди в магазине, обработка заданий принтера и т.д. Наглядные примеры использования стека в обычной жизни представить несколько сложнее. Несмотря на это, стек - воистину выдающаяся структура данных, используемая во многих компьютерных приложениях.

Например, рассмотрим любой императивный язык программирования вроде C# (императивный - значит, задающий жесткую последовательность действий, в противоположность функциональным и логическим языкам программирования - прим. перев.). Когда программа, написанная на C#, выполняется, CLR хранит стек вызовов, в котором записывается информация о вызове функций программы. При каждом вызове функции, ее информация добавляется на вершину стека. При завершении функции эта информация удаляется из стека. Информация в вершине стека вызовов представляет текущую функцию, выполняющуюся в данный момент. Чтобы самим взглянуть на стек вызовов, создайте проект в Visual Studio^® .NET, установите точку останова (breakpoint), выберите пункт меню Debug/Start. Когда выполнение программы остановится на breakpoint-е, вызовите окно Call Stack с помощью пункта меню Debug/Windows/Call Stack.

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