СТЕКИ, ОЧЕРЕДИ, ДЕКИ

СТЕК

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

Вершина

?

Включение —»

Исключение <—

Рис. 1.1. Логическая структура стека

Здесь А, В,... — элементы стека, каждый из которых может содержать одно или несколько полей. Стек функционирует по принципу LIFO (Last In — First Out — «последним пришел — первым исключается»), Известный пример стека — винтовочный патронный магазин. Число элементов стека не ограничено. Стек, в котором нет ни одного элемента, называется пустым.

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

ОПЕРАЦИИ НАД СТЕКОМ

Над стеком S могут быть выполнены следующие операции:

• 1) включение нового элемента со значением v в стек — Push(S, v);
• 2) исключение и возвращение значения верхнего элемента стека — Pop(S);
• 3) выработка признака «стек пуст» — Empty(S) (возвращает значение «истина», если стек пуст, и «ложь» — в противном случае);
• 4) считывание значения верхнего элемента без его исключения — TopValue(S);
• 5) возвращение числа элементов стека — Size(S);
• 6) очистка стека — Clear(S).

Первые три операции над стеками являются основными.

РЕАЛИЗАЦИЯ СТЕКА

Возможны два способа реализации стека — с помощью последовательного и связанного хранения элементов в памяти ЭВМ.

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

Достоинством последовательного способа хранения элементов стека в памяти ЭВМ являются простота реализации стека и выполняемых над ним операций. Однако описание стека с помощью массива приводит к неэкономному использованию памяти ЭВМ — отведение фиксированного объема памяти при непостоянстве числа элементов стека. Невозможность увеличения однажды отведенного объема может вызвать переполнение стека, тогда как по определению число элементов стека не ограниченно.

Использование связанного хранения элементов стека в памяти ЭВМ позволяет избежать этих недостатков. Реализация стека с помощью динамических переменных приведена на рис. 1.2.

Head Value Next Value Next Value Next

Рис. 1.2. Реализация стека с помощью динамических переменных

Каждый элемент стека состоит из двух частей: содержательной и ссылки на ранее включенный элемент. Переменная Head ссылочного типа указывает на верхний элемент стека (содержит адрес этого элемента). За первым включенным элементом стека (последним от Head) нет следующего элемента, поэтому в поле ссылки этого элемента записывается значение nil.

Описание класса tStack с элементами вещественного типа может быть выполнено следующим образом:

type

tValue = Real; // тип значения элемента стека - вещественный pltem = ^Atltem; // тип указателя на элемент стека

tltem = record Value : tValue;

// тип элемента стека //содержательная часть элемента стека //указатель на следующий элемент стека

// класс-стек

// поле - указатель на вершину стека // поле - число элементов стека

Next: pltem; end; // tltem tStack = class protected fHead : pltem; fSize : Word; public

property Size: Word read fSize; //число элементов стека procedure Push(v: tValue);//включение элемента со значением v function Pop: tValue; //исключение верхнего элемента стека function Empty: Boolean; //возвращение true, если стек пуст function TopValue: tValue; //возвращение значения верхнего элем. procedure Clear; virtual; //очистка стека constructor Create; // конструктор - создание стека

destructor Destroy; override; //деструктор - удаление стека end; //tStack

Свойство Size доступно только для чтения. Конструктор Create выполняет операции fHead:=nil и fSize:=0. Деструктор Destroy вызывает метод Clear для удаления элементов стека из памяти. Метод Push включает элемент в вершину стека и увеличивает число элементов стека на единицу. Метод Pop исключает элемент из вершины стека и уменьшает на единицу размер стека.

РЕАЛИЗАЦИЯ ОСНОВНЫХ ОПЕРАЦИИ НАД СТЕКОМ

Включение элемента со значением V в стек приведено на рис. 1.3. Одинарными линиями показаны связи в исходном состоянии стека, пунктирными — связи, устанавливаемые в процессе выполнения операции. Сначала организуется вспомогательная динамическая переменная с указателем №укет типа рКет. В поле значения этой переменной записывается значение нового элемента стека, в поле ссылки — адрес верхнего элемента стека, на который указывала ранее переменная fHead. Затем указатель fHead получает значение адреса вновь созданного элемента стека.

fHead

Рис. 1.3. Включение элемента со значением v в стек

Реализация метода включения элемента в стек:

procedure tStack.Push(v:tValue);

// Включение элемента со значением v в стек

var

//указатель на новый элемент

// выделение памяти под новый элемент //запись і/ в поле значения нового элемента // /НеасУ -> в поле ссылки нового элемента //перемещение іНеай на новый элемент //увеличение числа элементов стека на 1

Newltem: pltem;

begin

Newltem:= New(pltem);

Newltem^A.Value:= v;

Newltem^A.Next:= fHead; fHead:= Newltem;

Inc(fSize);

end; //procedure tStack.Push

Исключение элемента из стека. Сначала читается значение верхнего элемента стека. Затем в переменную Э^Рет типа ркет из указателя Шеаё переписывается адрес верхнего элемента стека. Указатель fHead перемещается на элемент стека, следующий за выталкиваемым, и освобождается занимаемая исключаемым элементом память. Схема исключения приведена на рис. 1.4.

Рис. 1.4. Исключение элемента из стека

Реализация метода исключения элемента из стека: function tStack.Pop:tValue;

// Исключение верхнего элемента стека и возвращение его значения

var

Disltem: pltem; //указатель на исключаемый элемент

begin

Рор:= fHead^A.Value;//чтение верхнего элемента стека Disltem:= fHead; //получение адреса исключаемого элемента fHead:= fHeadCNext//перемещение вершины на следующий элемент Dispose(Disltem); //удаление из памяти верхнего элемента Dec(fSize); //уменьшение числа элементов стека на 1

end;//function tStack.Pop

Операция Pop неприменима к пустому стеку, поэтому перед ее выполнением необходимо проверять значение признака «стек пуст».

Выработка признака «стек пуст» выполняется следующим образом:

function tStack.Empty: Boolean;

// Возвращает True, если стек пуст

begin

Empty:= fHead = nil;

end; //function tStack.Empty