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) правильны.

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

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
лишь наличием лишней скобки на дне стека (раз ее не вынимают,
она никак не влияет на работу программы). Снова ссылаемся на
предположение индукции и определение правильности.

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

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

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

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

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-ый стек пуст) <=> Вершина[s] = 0.
Стрелочные траектории, выходящие из Вершина[1], ..., Верши-
на[k] (из тех, которые не равны 0) не должны пересекаться. Поми-
мо них, нам понадобится еще одна стрелочная траектория, содержа-
щая все неиспользуемые в данный момент ячейки. Ее начало мы бу-
дем хранить в переменной Свободная (равенство Свободная = 0 оз-
начает, что пустого места не осталось). Вот пример:


n=8 | a | p | q | d | s | t | v | w |


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

Содержание = <a,p,q,d,s,t,v,w>, Следующий = <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;