Статическая реализация стеков

Словарный порядок на последовательностях произвольной длины

c₁…c_k < c₁^|…c^|_L, т.е. $ i₀ (c_i0<c_i0^| and "i<i₀ (c_i=c^|_I) or ("i (c_i=c_i^|) and k<L)

Технический приём: дополнить меньшее слово фиктивным элементом, например пробелом, наименьшим по определению.

можно:=false;

pаскраска:=Первая раскраска; {<первый цвет>}

while (не кончилась раскраска) do

begin

{Пустая раскраска – последовательность длины 0}

if правильная (раскраска) then if полная (раскраска) then

begin

можно:=true {печать (раскраска)}

else {раскраска правильная, но не полная}

{дополнить} раскраска:=раскраска + первый цвет

else {возврат} раскраска:=succ(раскраска);

end;

end;

Переход к следующей раскраске при новом определении словарного порядка:

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

2) Если раскраски не кончились, возвратить следующий за последним, выкинутым в раскраску.

Последовательность, из конца которой можно выкидывать и в конец которой можно добавлять элементы, называется стеком (stack).

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

1) Push ([x:tStack], y:T), х – имя стека, затолкнуть y в стек.

Семантика: x:=x+y (добавление элементов в конец последовательности)

2) Pop ([x:tStack],y:T), x – имя стека, извлечь y из стека.

if x=c₁…c_n then pop=c_n. Длина стека уменьшается на 1: x=c₁…c_n-1.

Попытка взять элемент из пустого стека считается ошибкой.

3) Empty ([x:tStack]):boolean; – стек пуст.

if Empty([x:tStack]){=true} then {длина стека равна нулю}.

4) Характерные для динамических типов операции Create([x:tStack]) и Destroy([x:tStack]) рассмотрим позднее.

Стеки также называют «магазинной» памятью.

Переход к следующей раскраске, если такой нет, то к пустой.

procedure Новая (var раскраска:tStack);

var x:tЦвет;

Begin

pop(stack,x);

while not empty(stack) and (x=последний цвет) do pop(stack,x);

if not empty(stack) then push(succ(x));

End;

Дополнить раскраску=push(stack,первый цвет)

Кончились раскраски – empty(stack)

Упражнение. Завершить реализацию перебора с возвратом, написав процедуру «Правильная».

c₁…c_k+1 – правильная, то c₁…с_k – правильная.

"iÎ[1,k] (соседи(c_k,c_k+1))

раскраска(1)¹раскраска(k+1)

(Выходим за пределы стековых операций).

Стек – динамический тип данных – количество элементов, которое можно положить в стек, не ограничено (в идеале), но во многих случаях, в том числе в задаче о раскраске карты, известна максимальная глубина стека, то есть стек можно понимать статически. Стандартный приём оперировать с такими типами (абстрактными, но статическими) – моделировать их массивами и переменными стандартных типов.

top heap

¯ ¯ nMax

Куча

type index=1..nMax{ };

T={базовый тип стека};

tStack= record

content:array[index] of T;

heap:index;{указатель на начало «кучи», первую свободную компоненту массива}

end;

procedure push(var stack:tStack;x:T);

begin

with Stack do

begin

content[heap]:=x;

inc(heap);

end;

end;

Реализация не защищена от ошибки – переполнения стека. Предполагается, что ситуацию контролирует пользователь.

procedure pop(stack:tStack;var x:T);

begin

with stack do

begin

dec(heap);

x:=content[heap];

end;

end;

Снова незащищённая реализация: контроль за пустотой стека возлагается на пользователя.

function empty(stack:tStack):boolean;

begin

empty:=stack.heap=1;

end;

procedure init(stack:tStack);{инициализация стека}

begin

stack.heap:=1;

end;

// финализация? – возврат в начальное состояние

Дата добавления: 2014-01-05