Стек

Большинство современных ЭВМ использует стек для того, чтобы обрабатывать данные в определенном порядке. Стеки являются устройствами магазинной памяти (LIFO); можно только или добавлять элемент данных в его верхнюю ячейку, или извлекать его оттуда. Добавление элемента данных в стек есть операция PUSH (занести в стек), извлечение данных из стека—POP или PULL. На рис. 2.17 показаны результаты операций занесения в стек и извлечения из него.

Некоторые ЭВМ имеют стеки, которые физически похожи на распределители тарелок в кафетериях, т. е. действительно все элементы данных физически сдвигаются, когда ЭВМ заносит или выбирает элементы. Стек, показанный на рис. 2.17, один из тех, в которых двигаются все элементы. Этот тип стека может быть построен на основе реверсивного сдвигового регистра.



В стеках большинства ЭВМ элементы данных в действительности не перемещаются. Единственное изменение, которое имеет место, приходится на указатель стека, который содержит адрес верхнего элемента стека. Электронно-вычислительная машина добавляет один элемент в стек, помещая элемент в ячейку памяти, адресуемую указателем стека, а затем увеличивает на 1 содержимое указателя стека. Извлечение элемента из стека производится путем уменьшения на 1 содержимого указателя стека и извлечения этого элемента из соответствующей ячейки памяти.

На рис. 2.18 показаны примеры этих операций. Заметим, что элементы данных в стеке совсем не передвигаются. Этот тип стека использует обычное ОЗУ.



Основное преимущество стека состоит в том, что можно заносить в него данные (увеличивать емкость стека), не разрушая структуру уже записанных в нем данных. Если данные запоминаются в ячейках памяти или в регистре, то теряется предыдущее содержимое этого участка памяти. Таким образом, прежде чем использовать одну и ту же ячейку памяти или регистр снова, необходимо где-то запомнить ее содержимое. Вместе с тем можно использовать стек снова и снова, так как предыдущее содержимое его автоматически сохраняется. Кроме того, ЦП может легко и быстро передавать данные в стек и из стека, так как адрес содержится в указателе стека, а не является частью команды. Формат команд операций со стеком очень короткий.



Стек можно использовать для того, чтобы иметь возможность очень просто запоминать адреса возвратов при работе с подпрограммами, как это показано на рис. 2.19.

Каждая команда ПЕРЕХОД К ПОДПРОГРАММЕ автоматически засылает адрес возврата из счетчика команд в стек. Каждая команда ВОЗВРАТ извлекает адрес возврата в программу из стека и помещает его в счетчик команд. 

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