Программирование на языке высокого уровня. Марапулец Ю.В. - 68 стр.

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




                                  Рис. 2.5. Структура стека

      Исключительная популярность стека в программировании объясняется тем, что
при заданной последовательности записи элементов в стек (например, А-В-С) извлече-
ние их происходит в обратном порядке (С-В-А). А именно эта последовательность дей-
ствий соответствует таким понятиям, как вложенность вызовов функций, вложенность
определений конструкций языка и т.д. Следовательно, везде, где речь идет о вложенно-
сти процессов, структур, определений, механизмом реализации такой вложенности яв-
ляется стек. Для способа хранения данных в стеке имеется общепринятый термин -
LIFO (last in - first out, «последний пришел - первый ушел»). Другое важное свойство
стека - относительная адресация его элементов. На самом деле для элемента, сохранен-
ного в стеке, важно не его абсолютное положение в последовательности, а положение
относительно вершины стека или его указателя, которое отражает «историю» его запол-
нения. Поэтому адресация элементов стека происходит относительно текущего значения
указателя стека. В архитектуре практически всех компьютеров используется аппаратный
стек. Он представляет собой обычную область внутренней (оперативной) памяти ком-
пьютера, с которой работает специальный регистр - указатель стека. С его помощью
процессор выполняет операции Push и Pop по сохранению и восстановлению из стека
байтов и машинных слов различной размерности.
      Рассмотрим пример стека. Для его формирования и работы достаточно иметь ука-
затель на вершину стека. Как и ранее допустим, что стек состоит из целых чисел Value,
то есть описание элемента стека выглядит следующим образом:

struct X
{
        int Value;
        X *p;
};

     Первоначально создадим первый элемент стека с помощью функции FirstElement(),
исходный код которой практически аналогичен приведенному ранее при инициализации
списка. Функция создает первый элемент, получая его значение A в качестве параметра
и выделяя под него память:

X * FirstElement(int A)
{
       X *FirstX;
       FirstX = (X *)malloc(sizeof(X));
       FirstX->Value = A;


                                             68