Динамические структуры данных. Задание практикума. Язык Паскаль. Вылиток А.А - 24 стр.

другой объект, уже находящийся в данный момент на хранении. Пример –
транспортёрная лента для погрузки багажа. Чемодан, раньше других попавший
на ленту, раньше других сойдёт с неё.
       В хранилищах типа «стек» (или LIFO2) каждый добавляемый объект не
может быть изъят позже, чем любой другой объект, уже находящийся в данный
момент на хранении. Примеры: стопка тарелок на полке буфета; магазин в
автоматическом оружии. В этих примерах соблюдается дисциплина LIFO, так
как взять можно только верхний предмет (тарелку или патрон), а добавить
новый объект можно, только положив его на верхний.
       Потребность в использовании стека или очереди возникает при
программировании многих реальных процессов и ситуаций. Рассмотрим один
из способов организации очередей и стеков в программе. В качестве структуры
данных для хранения объектов (элементов) будем использовать список. В
случае очереди элементы добавляются в конец списка, а удаляются из его
начала. В случае стека элементы добавляются и удаляются с одного конца
списка. Такой способ представления стеков и очередей очень распространён,
так что на его основе можно дать более узкие определения данных понятий:
       Очередь – это список, в который элементы всегда добавляются в конец, а
удаляются из начала.
       Стек – это список, в котором все вставки и удаления выполняются на
одном конце, называемом вершиной стека.
       Каждая из возможных реализаций списка на Паскале может быть
использована для представления очередей и стеков. Для стеков рассмотрим
вариант представления с помощью массивов, а для очередей – с помощью
динамических цепочек.


        Представление стеков с помощью массивов

       Опишем тип данных stack и две процедуры: push(S,x) – положить в
стек S элемент x и pop(S,x) – взять с вершины стека S элемент, присвоив его
параметру x.

const
  stacksize = … {максимальное число элементов, которые
                  могут одновременно находиться в стеке};
type
  elemtype = … {подходящий для задачи тип элементов
                   стека};
  stack = record
           elems: array [1..stacksize] of elemtype;
           top: integer {индекс вершины стека}
          end;

var S: stack; {стек}


2
 LIFO означает “Last In – First Out”, т.е. «последним вошёл – первым вышел».

                                            - 24 -