1.2 Что такое стек ?



==16

LIFO ( «Последний вошёл - первый вышел» ) буферы, известные так же, как «push down» стеки, - концептуально самый простой путь промежуточного хранения информации для типичных операций, таких как вычисление математических выражений и рекурсивный вызов подпрограмм.

1.2.1 Пример с подносами в кафетерии

В качестве примера работы стека, представим себе пружинный накопитель подносов, похожий на те, что используются в кафетериях. Предположим, что на каждом подносе написано число. В любой момент времени сверху может быть положен один поднос, что приведёт к сжатию пружин накопителя и освобождению места для нового подноса. Например, на рис. 1.1 подносы номер 42, 23, 2 и 9 кладутся на стопку подносов, причём 42 кладётся первым, а 9 - последним.

«Последний вошедший» - поднос номер 9. Таким образом, «первым вышедшим» также будет поднос номер 9. Так как покупатели берут подносы сверху, первым будет снят поднос номер 9, вторым - номер 2. Давайте представим, что в этот момент добавили несколько подносов. Эти подносы должны быть убраны раньше, чем будет снят первый положенный нами поднос. После любых сочетаний операций добавления и снятия подносов номер 42 по-прежнему внизу. Стопка опустеет снова только после того, как сверху будет снят поднос номер 42.

1.2.2 Примеры программной реализации

Существует несколько вариантов компьютерной реализации LIFO буферов. Самый примитивный - завести в памяти массив и выделить переменную с номером верхнего активного элемента. Те, кого заботит эффективность, могут подправить эту технику в направлении выделения блока памяти и загрузки указателя прямым адресом верхнего элемента стека. В любом случае «размещение» элемента в стеке предполагает выполнение действий по выделению в стеке нового слова и записи в него данных. «Выталкивание» означает процесс изъятия верхнего элемента из стека и передачу полученного значения запросившей операцию подпрограмме.



==17

Стеки часто располагают в верхних [* старших ]   адресах памяти машины. Растут они обычно от старших адресов памяти к младшим, что позволяет наиболее универсальным способом использовать память между концом кода программы и верхним элементом стека. В нашем случае безразлично растёт стек к «верхним» адресам или к «нижним». «Верхний» элемент стека это тот элемент, который положен в стек последним и будет взят первым. «Нижний» элемент стека тот, изъятие которого оставит стек пустым.



==18

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

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

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

1.2.3 Примеры аппаратной реализации

Очевидным преимуществом аппаратной реализации является гораздо более высокая скорость работы, нежели у программных стеков. В машинах, имеющих большой процент обращающихся к стеку инструкций, подобное увеличение быстродействия критично для поддержания высокой производительности.

Любой программный метод организации стека может быть реализован аппаратно, но общепринятой практикой является резервирование непрерывного массива ячеек памяти и обслуживающего эту память указателя. Обычно для этих целей выделяется аппаратный регистр, который может увеличиваться или уменьшаться в соответствии с проводимой над стеком операцией. Иногда организуют возможность прибавлять к указателю стека смещение, чтобы получить доступ к нескольким первым элементам стека без вызова последовательных команд выборки. Часто стек располагается в той же памяти, что и основная программа, но иногда, в целях увеличения быстродействия, под него отводят отдельные устройства хранения.

Другим возможным подходом может быть построение стеков на сдвиговых регистрах. «Торец» каждого сдвигового регистра виден, как один из битов слова на вершине стека. Тридцать два таких регистра длиной N бит каждый и формируют стек шириной 32-бита и глубиной N элементов. В прошлом подобный подход был редкостью, но с появлением технологии VLSI он может стать реальной альтернативой стандартному регистру, указывающему на массив памяти.



==18