Стек (stack) это абстрактная структура данных для хранения набора элементов, обработка которого допустима только с одного конца, называемого вершиной стека. Положение вершины в стеке отображает указатель стека sp (stack pointer). Через вершину в стеке можно добавить (протолкнуть) новый элемент или извлечь (вытолкнуть) последний добавленный элемент, изменяя при этом соответствующим образом указатель стека. Извлекать элементы из стека и добавлять элементы в стек можно неоднократно, пока стек не пуст и не переполнен, соответственно. Реализуемая стеком дисциплина обслуживания набора данных называется LIFO (LastIn, FirstOut - последним пришел, первым обслужен).
Для хранения данных в стеке выделяется специальный буфер sbuf (stack buffer). В простейшем случае буфер стека реализуется одномерным массивом, длина которого априори устанавливает предельный размер стека ssize (stack size), задаваемый при создании стека. Такая организация стека называется стеком с фиксированным буфером (FixStack). Указатель стека в нем интерпретируется как целочисленный индекс массива, представляющего буфер стека. Логическую структуру стека с фиксированным буфером, в котором содержатся 3 элемента: A, B, C отображает следующий рисунок.

Рис. 1.  Логическая структура стека с фиксированным буфером.

Для работы со стеком используются 3 примитивные процедуры: PUSH, POP и STATE, которые обеспечивают извлечение данных из стека, загрузку данных в стек и оценку состояния стека, соответственно.
Примитив PUSH загружает (проталкивает) новый элемент в вершину стека и увеличивает на 1 значение указателя стека. Псевдокод процедуры PUSH выражают следующие операторы:

    Sbuf[sp] <- V; 
    sp <- sp+1; 
    RETURN; 

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

Рис. 2.  Диаграмма загрузки в стек.

Для стека с фиксированным буфером процедура извлечения данных необязательно является деструктивной операцией, т.е. вытолкнутые элементы не уничтожаются в буфере стека, по крайней мере, до загрузки новых данных. Очевидно, что процедура проталкивания данных в стек имеет деструктивный эффект, модифицируя содержания буфера стека. Рассмотренные примитивы PUSH и POP обеспечивают желаемую обработку стека с фиксированным буфером, когда он не переполнен (sp < ssize) и не пуст (sp=0), соответственно.
Для оценки текущего состояния стека используется примитив STATE. Он обеспечивает оценку состояния стека по возвращаемому значению его указателя. Целесообразной представляется следующая кодировка возврата примитива STATE. Если при оценке в буфере стека нет свободного места для размещения новых данных, т.е. буфер заполнен полностью, возвращается отрицательный код. В противном случае, когда в буфере стека есть свободное пространство для размещения новых элементов, при оценке стека примитивом STATE возвращается текущее значение указателя стека. Очевидно, когда стек пуст примитив STATE будет возвращать нулевое значение.
Псевдокод примитива STATE выражают следующие операторы:

       IF sp<ssize THEN RETURN(sp); 
          ELSE RETURN(-sp); 

На следующем рисунке представлены 3 диаграммы состояний для пустого, допустимо заполненного и переполненного стека, которые иллюстрируют принятую кодировку возврата примитива STATE.

Рис. 3.  Диаграмма состояний стека.

Примитив STATE следует использовать в сочетании с примитивами PUSH и POP, чтобы избежать потери значимости при переполнении стека и попытке извлечь данные из пустого стека. Следующий псевдокод блокирует потерю значимости в случае пустого стека (underflow) при использовании примитива POP для извлечения данных в переменную W:

      IF STATE() > 0 THEN 
             W <- POP(); 
      ELSE 
             UNDERFLOW(); 

где процедура UNDERFLOW реализует желаемую в программе последовательность обработки состояния пустого стека при попытке извлечь данные. Исключение потери значимости в случае переполнения стека (overflow) при попытке протолкнуть в стек новый элемент V, используя примитив PUSH, демонстрирует следующий псевдокод:

      IF STATE() < 0 THEN 
             OVERFLOW(); 
      PUSH(V); 

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