Стек

Цель: изучение фундаментальной абстрактной структуры - стека.

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

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

В структуре стека важнейшее место занимают операции, добавляющие и удаляющие элементы. Операция Push добавляет в вершину стек, а операция Pop извлекает элемент с вершины стека.

type
link = ^node;
node = record
key: integer;
next: link;
end;

Var
head, z: link;

procedure stackinit;
begin
new(head);
new(z);
head^.next:=z;
z^.next:=z;
end;

procedure push(v: integer);
var
t: link;
begin
new(t);
t^.key:=v;
t^.next:=head^.next;
head^.next:=t;
end;

function pop: integer;
var
t: link;
begin
t:=head^.next;
pop:=t^.key;
head^.next:=t^.next;
dispose(t);
end;

Давайте решим задачу с использованием стека.

Нужно так расставить 8 ферзей на шахматной доске, чтобы ни один из них не угрожал другому.

Эта задача демонстрирует очень интересный прием в программировании - поиск с возвращениями.

Хотя на доске 64 клетки, взять 8 из них можно 64!/(56!*8!)=4 426 165 368 способами. Проверять все эти комбинации - большая работа даже для ЭВМ.

Поставим одного ферзя, затем ("безопасно") второго, третьего и т.д.

Для указанного размещения 5 ферзей вы не найдете подходящей позиции для 6-го ферзя. Наступил черед рационализации. Не будем отбрасывать достигнутое! Сделаем лишь один шаг назад - изменим позицию ферзя Ф5, вновь попытаемся поставить Ф6 и лишь при безуспешной попытке сделаем второй шаг назад и т.д. Это стратегия планомерного отступления и прорыва вперед при первой возможности.

Кто бы мог подумать, что будет столько тупиков! К первому полному решению приходим, побывав в 42 тупиках! На месте остается лишь Ф1! Тем не менее перебор резко сокращается и в ЭВМ нахождением 96 полных решений займет краткий миг.

Для маркировки вертикалей вместо букв А..H используем цифры 1..8. Это значения переменной Х. Аналогично переменная Y обозначает текущую горизонталь. Занятые горизонтали отмечаем значениями R[Y]=1; если снимаем ферзя (делаем шаг назад) - R[Y]=0. Для идентификации диагоналей, направленных как главная диагональ, используем значения X+Y, для прочих - значение Y-X. Эти значения суммы и разности одинаковы для всех клеток лежащих на диагонали.

program Stack;
uses
crt;
Const N=8;
type
link = ^node;
node = record
key: integer;
next: link;
end;
Var
R: Array[1..N] of byte;
j,Y,X:Integer;
R1: Array[2..N+N] of Byte;
R2: Array[1-N..N-1] of Byte;
head, z: link;

procedure stackinit;
begin
new(head);
new(z);
head^.next:=z;
z^.next:=z;
end;

procedure push(v: integer);
var
t: link;
begin
new(t);
t^.key:=v;
t^.next:=head^.next;
head^.next:=t;
end;

function pop: integer;
var
t: link;
begin
t:=head^.next;
pop:=t^.key;
head^.next:=t^.next;
dispose(t);
end;

procedure st_print;
var
t: link;
str1, s: string;
i: integer;
begin
str1:='';
t:=head^.next;
while t<>z do
begin
str(t^.key, s);
str1:=str1+s;
t:=t^.next;
end;
for i:=1 to N do
write(str1[N-i+1]+' ');
readln;
end;

procedure stackdestroy;
begin
dispose(head);
dispose(z);
end;

Function Uspeh:Boolean;
Var
j: byte;
usp: Boolean;
Begin
usp:=false;
While (Y < N) And Not usp do
Begin
Y:= Y+1;
If R[Y] + R1[X+Y] + R2[Y-X] = 0 Then
usp:= true
Else
usp:= false
End;
Uspeh:= usp
End;

BEGIN
clrscr;
For Y:= 1 to N do
R[Y]:= 0;
For j:= 2 to N+N do
R1[j]:= 0;
For j:= 1-N to N-1 do
R2[j]:= 0;
stackinit;
j:= 0;
X:= 1;
Y:= 0;
Repeat
If Uspeh Then
Begin
push(Y);
If X < N Then
Begin
R[Y]:=1;
R1[X+Y]:=1;
R2[Y-X]:=1;
X:= X+1;
Y:=0;
End
Else
begin
st_print;
pop;
end;
End
Else
Begin
X:= X-1;
If X > 0 Then
Begin
y:=pop;
R[Y]:= 0;
R1[X+Y]:= 0;
R2[Y-X]:= 0;
End
End
Until X = 0;
Stackdestroy;
Readln;
END.

Заметим, что в основной программе шахматами и "не пахнет". Действительно, метод универсален, он применяется на графах и в других областях.

Итак, на сегодняшнем занятии Вы познакомились с абстрактной структурой данных - стеком.