Стек - это структура данных, которая используется для временного  хранения информации.  Программа может поместить данные в стек  (PUSH) или забрать их оттуда (POP).  Стековая структура данных  предполагает упорядочивание помещенных в него данных специальным  образом. Во всех случаях первым из стека извлекается то, что было  в нем сохранено последним.  Такая организация хранения данных  сокращенно обозначается LIFO (last in, first out - последний  введенный первым выводится).  Если мы поместили в стек сначала A,  затем B, то первое, что мы извлечем из него будет B.  Следующая  команда извлечения (POP) вернет A.  Информация возвращается из  стека в порядке, строго противоположном порядку ее помещения в  стек.

Стек противоположен очереди.  Очередь - это обычная последовательность, подобная очередям на почте или в магазине.  Это  структура данных типа "первым вошел - первым вышел" (first in,  first out:  FIFO).  Тот, кто первым встал в очередь, первым и  покинет ее.  Стек и очередь - очень разные вещи.

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

Фиг. 2.19 дает пример стека.  В части (a) изображен стек после  того как в него последовательно помещены значения A, B, C.  Указатель стека указывает на текущую вершину стека, в данном случае на  C.  В части (b) в стек помещается еще одно значение: D.  Операция  PUSH уменьшает указатель стека SP (от Stack Pointer - указатель  стека), который теперь указывает на новую вершину D.  Указатель  стека всегда фиксирует то, что было последним помещено в стек.

Фиг. 2.19(c) показывает состояние стека после операции POP.  Этой операцией значение D было извлечено из стека.  Команда POP  помещает извлеченное из стека значение в указанное место.  Если в  части (c) выполнялась команда POP AX, то процессор поместил  значение D в регистр AX (это уже дополнительный аспект, который мы  обсудим в следующей главе).  POP увеличивает указатель стека.  Теперь он указывает на новую вершину, C.  Заметим, что элементы  извлекаются из стека по описанному принципу LIFO.  Последним  помещенным в стек элементом был D и он же первым извлечен из стека.

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

На Фиг. 2.19(d) видно, что происходит с D при помещении в сетк  нового элемента E.  Элемент E записывается на место D и становится  новой вершиной стека.  Мораль из этой истории такова, что хотя  извлеченные из стека значения могут оставаться в памяти, полагаться  на это не следует.

       ГДДДґ            ГДДДґ      ГДДДґ      ГДДДґ

       і  і            і D і<ДД SP    і D і       і E і<ДД SP

       ГДДДґ            ГДДДґ      ГДДДґ      ГДДДґ

       і C і<ДД SP    і C і        і C і<ДД SP    і C і

       ГДДДґ            ГДДДґ      ГДДДґ      ГДДДґ

       і B і            і B і      і B і      і B і

       ГДДДґ            ГДДДґ      ГДДДґ      ГДДДґ

       і A і            і A і      і A і      і A і

       ГДДДґ            ГДДДґ      ГДДДґ      ГДДДґ

      (a)          (b)        (c)        (d)

      Фиг. 2.19  Пример работы стека

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

Мы занялись обсуждением стека потому, что стек используется для  хранения адреса возврата из процедуры.  Как это делается?

Каждая команда CALL вызывает как бы выполнению команды PUSH для  стека - сохраняет в стеке адрес возврата.  Команда RET извлекает из  стека, подобно команде POP, адрес возврата и помещает его в  указатель команд.  8088 использует стек для хранения адресов  возврата потому, что это позволяет вкладывать процедуры одна в  другую. Что такое вложение?  На Фиг.  2.20 показан пример  вложенных процедур.

На Фиг. 2.20 показана абсурдная программа, которую мы используем как пример вложения процедур.  Часть (a) показывает  стек перед выполнением программы.  Как только начинает выполняться  процедура MAIN, она вызывает процедуру SUBROUTINE_A.  В это время  процессор сохраняет в стек адрес возврата.  Часть (b) показывает  адрес возврата 103 помещенным в стек.  SUBROUTINE_A в процессе  своего выполнения вызывает SUBROUNINE_B.  Команда этого вызова  сохраняет адрес возврата 108 в SUBROUNINE_A.  Когда SUBROUNINE_B  заканчивается, команда возврата извлекает из стека значение 108,  как показано в части (d).  Процессор помещает это значение в  указатель команд, как требуется при команде возврата.  Как видно на  листинге ассемблера, адрес 108 относится к SUBROUNINE_A и следует  сразу за вызовом SUBROUNINE_B.  Затем SUBROUNINE_A заканчивается.  Команда возврата извлекает из стека значение 103 для указателя  команд. Адрес 103 относится к процедуре MAIN и следует сразу за  вызовом SUBROUNINE_A.

Наиболее важным в примере на Фиг.  2.20 является вложение  процедур. Одна процедура может вызывать другую, а команда возврата  всегда обеспечивает правильный возврат управления.  Единственное,
        Microsoft (R) Macro Assembler Version 5.00              11/10/88 23:18:17

          Фиг. 2.20 Вызов вложенных процедур                Page   1-1

 

                                         PAGE   ,132

                                         TITLE  Фиг. 2.20 Вызов вложенных процедур

           0000                   CODE   SEGMENT

 

                                         ASSUME CS:CODE

           0100                         ORG    100H

 

           0100  E8 0104 R             MAIN:   CALL    SUBROUTINE_A

           0103  40                          INC     AX

 

                                   ;----- Здесь главная процедура продолжается . . .

 

           0104                   SUBROUTINE_A    PROC    NEAR

           0104  43                          INC     BX

           0105  E8 0109 R                    CALL    SUBROUTINE_B

           0108  C3                           RET

           0109                   SUBROUTINE_A    ENDP

 

           0109                   SUBROUTINE_B    PROC    NEAR

           0109  41                          INC     CX

           010A  C3                           RET

           010B                   SUBROUTINE_B    ENDP

 

           010B                   CODE   ENDS

                                         END

 

            ГДДДґ        ГДДДґ           ГДДДґ      ГДДДґ

            і  і        і   і           і108іДД SP    і108і

            ГДДДґ        ГДДДґ           ГДДДґ      ГДДДґ

            і  і        і103іДД SP   і103і        і103іДД SP

            ГДДДґ        ГДДДґ           ГДДДґ      ГДДДґ

            іxxxіДД SP    іxxxі          іxxxі      іxxxі

            ГДДДґ        ГДДДґ           ГДДДґ      ГДДДґ

             (a)        (b)         (c)        (d)

            Фиг. 2.20 Вызов вложенных процедур

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

Пример программы на Фиг.  2.20 показывает также использование  еще одной псевдооперации ассемблера - PROC.  Оператор PROC  используется ассемблером для идентификации процедур.  Как мы  дальше увидим, ассемблер должен знать, как далеко располагается  процедура и как возвращаться к точке ее вызова.  Операнд NEAR  определяет процедуру как расположенную в пределах легкой  достигаемости вызывающей программы.  Мы еще вернемся к оператору  PROC, когда будем обсуждать реальное действие команд CALL и JMP.