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 размер стека.

4. Реализация основных операций над стеком

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

Одинарными линиями показаны связи в исходном состоянии стека, пунктирными – связи, устанавливаемые в процессе выполнения операции. Сначала организуется вспомогательная динамическая переменная с указателем NewItem типа pItem. В поле значения этой переменной записывается значение нового элемента стека, в поле ссылки – адрес верхнего элемента стека, на который указывала ранее переменная fHead. Затем указатель fHead получает значение адреса вновь созданного элемента стека.

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

procedure tStack.Push(v: tValue);

Var

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

Begin

NewItem: = New(pItem); // выделение памяти под новый элемент стека

NewItem^.Value: = v; // запись v в поле значения нового элемента

NewItem^.Next: = fHead; // fHead -> в поле ссылки нового элемента

fHead: = NewItem; // перемещение fHead на новый элемент

Inc(fSize); // увеличение числа элементов стека на 1

end; //procedure tStack.Push

Исключение элемента из стека. Сначала читается значение верхнего элемента стека. Затем в переменную DisItem типа pItem из указателя fHead переписывается адрес верхнего элемента стека. Указатель fHead перемещается на элемент стека, следующий за выталкиваемым, и освобождается занимаемая исключаемым элементом память. Схема исключения:

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

function tStack.Pop: tValue;

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

Var

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

Begin

Pop: = fHead^.Value; // чтение верхнего элемента стека

DisItem: = fHead; // получение адреса исключаемого элемента

fHead: = fHead^.Next; // перемещение вершины на следующий элемент

Dispose(DisItem); // удаление из памяти бывшего верхнего элемента

Dec(fSize); // уменьшение числа элементов стека на 1

end; // function tStack.Pop

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

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

function tStack.Empty: Boolean;

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

Begin

Empty: = fHead = nil;

end; // function tStack.Empty

5. Использование стека для преобразования
форм записи выражений.

В инфиксной записи операция разделяет два операнда, в постфиксной – операция следует за двумя операндами, в префиксной – операция предшествует двум операндам. Например:

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

После просмотра выражения выталкиваются из стека и записываются в постфиксную строку все оставшиеся в стеке операции.

v Вычисление значения выражения по его постфиксной записи.

Постфиксное выражение сканируется слева направо и обрабатывается следующим образом:

v Перевод из инфиксной формы записи выражения в префиксную.

Инфиксное выражение сканируется справа налево, и префиксная строка строится также справа налево. Алгоритм преобразования такой же, как и при преобразовании в постфиксную форму, только открывающие скобки меняются на закрывающие и, наоборот, при определении приоритета операции «£» изменяется на «<», чтобы равноприоритетные операции выполнялись слева направо.

v Вычисление значения выражения по его префиксной записи.

Алгоритм вычисления полностью совпадает с алгоритмом вычисления по постфиксной записи, но префиксная строка сканируется справа налево.

6. Очередь

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

Очередь функционирует по принципу FIFO (First In – First Out: «первым пришел – первым исключается»). В реальном мире имеется множество примеров очередей: очередь к кассе магазина, очередь задач, обрабатываемых вычислительной машиной. Каждый элемент очереди может содержать одно или несколько полей, число элементов в очереди не ограничено. Очередь, не содержащая ни одного элемента, называется пустой.

7. Операции над очередью

Над очередью q (от англ. queue – очередь) могут быть выполнены следующие операции:

1) включение нового элемента v в конец очереди – Insert (q, v);

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

3) выработка признака «очередь пуста» – Empty (q);

4) считывание первого элемента без его удаления – HeadValue (q);

5) считывание последнего элемента очереди – RearValue (q);

6) определение числа элементов очереди Size (q);

8) очистка очереди – Clear (q).

Первые три операции над очередью являются основными. Операции Empty, Size, и Clear для очереди аналогичны соответствующим операциям для стека.

8. Дек

Деком (DEQ – от английского double ended queue, очередь с двумя концами) называется упорядоченный набор элементов, включение и исключение элементов в котором могут осуществляться с любого из двух его концов. Логическая структура дека:

Частные случаи дека – дек с ограниченным входом и дек с ограниченным выходом (включение или исключение элементов осуществляется только с одного из концов дека).

9. Операции над деком

Над деком d могут быть выполнены все операции, определенные для очереди q, а также добавляются две основные операции:

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

– исключение элемента из конца дека – Delete (d) и возвращение его в качестве значения функции.

10. Реализация очереди и дека

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

При этом вводятся две переменные типа указателя на элемент очереди или дека: Head – на начало, Rear – на конец очереди или дека. В поле ссылки последнего элемента записывается значение nil.

Описание классов tQueue и tDEQ – наследников класса tStack – может быть следующим:

Type

// Описание класса tQueue

tQueue = class (tStack) // класс - очередь