6.1. Стеки.

Пусть T - некоторый тип. Рассмотрим (отсутствующий в паскале) тип "стек элементов типа T". Его значениями являются последовательности значений типа T.

Операции:
Сделать_пустым (var s: стек элементов типа T).
Добавить (t: T; var s: стек элементов типа T).
Взять (var t: T; var s: стек элементов типа T).
Пуст (s: стек элементов типа T): boolean
Вершина (s: стек элементов типа T): T

(Мы пользуемся обозначениями, наполняющими паскаль, хотя в паскале типа "стек" нет.) Процедура "Сделать_пустым" делает стек s пустым. Процедура "Добавить" добавляет t в конец последовательности s. Процедура "Взять" применима, если последовательность s непуста; она забирает из неё последний элемент, который становится значением переменной t. Выражение "Пуст(s)" истинно, если последовательность s пуста. Выражение "Вершина(s)" определено, если последовательность s непуста, и равно последнему элементу последовательности s.

Мы покажем, как моделировать стек в паскале и для чего он может быть нужен.

Моделирование ограниченного стека в массиве.

Будем считать, что количество элементов в стеке не превосходит некоторого числа n. Тогда стек можно моделировать с помощью двух переменных:
Содержание: array [1..n] of T;
Длина: integer;

считая, что в стеке находятся элементы Содержание [1],...,Содержание [длина].

Чтобы сделать стек пустым, достаточно положить
Длина := 0

Добавить элемент t:
{Длина < n}
Длина := Длина+1;
Содержание [Длина] :=t;

Взять элемент в переменную t:
t := Содержание [Длина];
Длина := Длина - 1;

Стек пуст, если Длина = 0.

Вершина стека равна Содержание [Длина].

Таким образом, вместо переменной типа стек в программе на паскале можно использовать две переменные Содержание и Длина. Можно также определить тип стек, записав
const N = ...
type stack = record
Содержание: array [1..N] of T;
Длина: integer;
end;

(Мы позволяем себе использовать имена переменных из русских букв, хотя обычно паскаль этого не любит.) После этого могут быть - в соответствии с правилами паскаля - описаны процедуры работы со стеком. Например, можно написать
procedure Добавить (t: T; var s: stack);
begin
| {s.Длина < N}
| s.Длина := s.Длина + 1;
| s.Содержание [s.Длина] := t;
end;

Использование стека.

Будем рассматривать последовательности открывающихся и закрывающихся круглых и квадратных скобок ( ) [ ]. Среди всех таких последовательностей выделим правильные - те, которые могут быть получены по таким правилам:

    1. пустая последовательность правильна.
    2. если А и В правильны, то и АВ правильна.
    3. если А правильна, то [A] и (A) правильны.


Пример. Последовательности (), , [()[]()][] правильны, а последовательности ], )(, (], ([)] - нет.

6.1.1. Проверить правильность последовательности за время, не превосходящее константы, умноженной на её длину. Предполагается, что члены последовательности закодированы числами:
( 1
[ 2
) -1
] -2

Решение. Пусть a[1]..a[n] - проверяемая последовательность. Рассмотрим стек, элементами которого являются открывающиеся круглые и квадратные скобки (т. е. 1 и 2).

Вначале стек делаем пустым. Далее просматриваем члены последовательности слева направо. Встретив открывающуюся скобку (круглую или квадратную), помещаем её в стек. Встретив закрывающуюся, проверяем, что вершина в стеке - парная ей скобка; если это не так, то можно утверждать, что последовательность неправильна, если скобка парная, то заберем её (вершину) из стека. Последовательность правильна, если в конце стек оказывается пуст.
Сделать_пустым (s);
i := 0; Обнаружена_ошибка := false;
{прочитано i символов последовательности}
while (i < n) and not Обнаружена_ошибка do begin
| i := i + 1;
| if (a[i] = 1) or (a[i] = 2) then begin
| | Добавить (a[i], s);
| end else begin {a[i] равно -1 или -2}
| | if Пуст (s) then begin
| | | Обнаружена_ошибка := true;
| | end else begin
| | | Взять (t, s);
| | | Обнаружена_ошибка := (t <> - a[i]);
| | end;
| end;
end;
Правильно := (not Обнаружена_ошибка) and Пуст (s);

Убедимся в правильности программы.

    1. Если последовательность построена по правилам, то программа даст ответ "да". Это легко доказать индукцией по построению правильной последовательности. Надо проверить для пустой, для последовательности AB в предположении, что для A и B уже проверено - и для последовательностей [A] и (A) - в предположении, что для A уже проверено. Для пустой очевидно. Для AB действия программы происходят как для A и кончаются с пустым стеком; затем все происходит как для B. Для [A] сначала помещается в стек открывающая квадратная скобка и затем все идет как для A - с той разницей, что в глубине стека лежит лишняя скобка. По окончании A стек становится пустым - если не считать этой скобки - а затем и совсем пустым. Аналогично для (A).
    2. Покажем, что если программа завершает работу с ответом "да", то последовательность правильная. Рассуждаем индукцией по длине последовательности. Проследим за состоянием стека в процессе работы программы. Если он в некоторый промежуточный момент пуст, то последовательность разбивается на две части, для каждой из которых программа дает ответ "да"; остается воспользоваться предположением индукции и определением правильности. Пусть стек все время непуст. Это значит, что положенная в него на первом шаге скобка будет вынута лишь на последнем шаге. Поэтому первый и последний символы последовательности - это парные скобки, и последовательность имеет вид (A) или [A], а работа программы (кроме первого и последнего шагов) отличается от её работы на A лишь наличием лишней скобки на дне стека (раз ее не вынимают, она никак не влияет на работу программы). Снова ссылаемся на предположение индукции и определение правильности.


6.1.2. Как упростится программа, если известно, что в последовательности могут быть только круглые скобки?

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

6.1.3. Реализовать с помощью одного массива два стека, суммарное количество элементов в которых ограничено длиной массива; все действия со стеками должны выполняться за время, ограниченное константой, не зависящей от длины стеков.

Решение. Стеки должны расти с концов массива навстречу друг другу: первый должен занимать места
Содержание[1] ... Содержание[Длина1],

а второй -
Содержание[n] ... Содержание[n - Длина2 + 1]
(вершины обоих стеков записаны последними).

6.1.4. Реализовать k стеков с элементами типа T, общее количество элементов в которых не превосходит n, с использованием массивов суммарной длины C*(n+k), затрачивая на каждое действие со стеками (кроме начальных действий, делающих все стеки пустыми) время, ограниченное некоторой константой.

Решение. Применяемый метод называется "ссылочной реализацией". Он использует три массива:
Содержание: array [1..n] of T;
Следующий: array [1..n] of 0..n;
Вершина: array [1..k] of 0..n.

Массив Содержание будем изображать как n ячеек с номерами 1..n, каждая из которых содержит элемент типа T. Массив Следующий изобразим в виде стрелок, проведя стрелку из i в j, если Следующий[i] = j. (Если Следующий[i] = 0, стрелок из i не проводим.) Содержимое s-го стека (s из 1..k) хранится так: вершина равна Содержание[Вершина[s]], остальные элементы s-го стека можно найти, идя по стрелкам - до тех пор, пока они не кончатся. При этом (s-ый стек пуст) <=><a,p,q,d,s,t,v,w> Вершина[s] = 0.

Стрелочные траектории, выходящие из Вершина[1], ..., Вершина[k] (из тех, которые не равны 0) не должны пересекаться. Помимо них, нам понадобится еще одна стрелочная траектория, содержащая все неиспользуемые в данный момент ячейки. Ее начало мы будем хранить в переменной Свободная (равенство Свободная = 0 означает, что пустого места не осталось). Вот пример:
n=8 | a | p | q | d | s | t | v | w |


k=2 | | | Свободная

Содержание = , Следующий = <3,0,6,0,0,2,5,4>
Вершина = <1, 7>, Свободная = 8
Стеки: 1-ый: p t q a (a-вершина); 2-ой: s v (v-вершина).

procedure Начать_работу; {Делает все стеки пустыми}
| var i: integer;
begin
| for i := 1 to k do begin
| | Вершина [i]:=0;
| end;
| for i := 1 to n-1 do begin
| | Следующий [i] := i+1;
| end;
| Следующий [n] := 0;
| Свободная:=1;
end;

function Есть_место: boolean;
begin
| Есть_место := (Свободная <> 0);
end;

procedure Добавить (t: T; s: integer);
| {Добавить t к s-му стеку}
| var i: 1..n;
begin
| {Есть_место}
| i := Свободная;
| Свободная := Следующий [i];
| Следующий [i] := Вершина [s];
| Вершина [s] :=i;
| Содержание [i] := t;
end;

function Пуст (s: integer): boolean; {s-ый стек пуст}
begin
| Пуст := (Вершина [s] = 0);
end;

procedure Взять (var t: T; s: integer);
| {взять из s-го стека в t}
| var i: 1..n;
| begin
| {not Пуст (s)}
| i := Вершина [s];
| t := Содержание [i];
| Вершина [s] := Следующий [i];
| Следующий [i] := Свободная;
| Свободная := i;
end;

function Вершина_стека (s: integer): T;
| {вершина s-го стека}
begin
| Вершина_стека := Содержание[Вершина[s]];
end;