Стек и очередь

Begin

Begin

if (p<>nil)and(p^.next<>p)then begin

q:=p^.next^.next;

dispose(p^.next);

p^.next:=q;

q^.prev:=p;

end;

end;

{Вставить перед указанным:}

procedure InsertBefore(p: tItemPtr; d: tData);

var q: tItemPtr;

if p<>nil then begin

new(q);

q^.data:=d;

q^.next:=p;

q^.prev:=p^.prev;

p^.prev:=q;

q^.prev^.next:=q;

end;

end;

Стеком называется такой способ хранения данных, при котором элемент, записанный в хранилище данных, последним всегда извлекается первым (дисциплина LIFO – «last in - first out»). При извлечении элемента происходит его удаление со стека.

Рассмотрим простейший пример использования стека. Предположим, что имеется строка, состоящая из одних лишь открывающих и закрывающих скобок. Требуется определить, является ли она правильным скобочным выражением (то есть для каждой открывающей скобки должна найтись закрывающая). Заведём массив и переменную для хранения номера последнего значимого элемента в массиве (то есть вершины стека), в который при проходе по строке будем складывать все открывающиеся скобки (с увеличением номера вершины на 1), а при встрече с закрывающей будем удалять соответствующую открывающую (попросту уменьшать номер вершины стека). Если окажется, что «пришла» закрывающая скобка, а стек пуст (то есть номер вершины равен 0), то выражение ошибочно. Это же можно сказать и в случае, когда строка закончилась, а стек не пуст.

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

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

Любая реализация стека должна содержать следующие процедуры и функции:

procedure InitStack – инициализация стека;

procedure Push(d: tData) – положить элемент в стек;

procedure Pop(var d: tData) – извлечь элемент с вершины стека;

function NotEmpty: boolean – проверка стека на пустоту;

Очередь отличается от стека тем, что последний пришедший в неё элемент будет извлечён последним, а первый – первым («FIFO»). С помощью списков её можно организовать следующим образом: будем хранить не только указатель на «голову» списка, но и на «хвост»; добавлять будем в «хвост», а извлекать – из «головы».

Любая реализация очереди (не обязательно с помощью списков) должна «уметь» выполнять такие действия:

procedure InitQueue – инициализация очереди;

procedure AddQueue(d: tData) – поставить элемент в очередь;

procedure SubQueue(var d: tData) – извлечь элемент из очереди;

function NotEmpty: boolean – проверка очереди на пустоту;