Тема 1. Стеки, очереди, деки

1. Стек

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

Включение Исключение	 	E	D	C	B	A
		
	Вершина

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

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

2. Операции над стеком

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

1) включение нового элемента со значением v в стек – Push(s,v);

2) исключение и возвращение значения верхнего элемента стека – Pop(s);

3) выработка признака «стек пуст» – Empty(s) (возвращает значение «истина», если стек пуст, и «ложь» – в противном случае);

4) считывание значения верхнего элемента без его исключения – TopValue(s);

5) возвращение числа элементов стека – Size(s);

6) очистка стека – Clear(s).

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

3. Реализация стека

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

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

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

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

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

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

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

type

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

pItem = ^tItem; // тип указателя на элемент стека

tItem = record // тип элемента стека

Value : tValue; // содержательная часть элемента стека

Next : pItem; // указатель на следующий элемент стека

end; // tItem

tStack = class // класс–стек

protected

fHead : pItem; // поле - указатель на вершину стека

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; // очистка стека

constructor Create; // конструктор - создание пустого стека

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

end; // tStack

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