Стеки

Стеком называется одномерная структура данных, загрузка или увеличение элементов для которой осуществляется с помощью указателя стека в соответствии с правилом LIFO ("last-in, first-out" "последним введен,первым выведен").

Указатель стека sp (stack pointer) содержит в любой момент времени индекс (адрес) текущего элемента, который является единственным элементом стека, доступным в данный момент времени для обработки.

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

1. Начальная установка:

Sp:=1;

1. Загрузка элемента x в стек:

Stack[sp]:=x; Sp:=sp+1;

1. Извлечение элемента из стека:

Sp:=sp-1; X:=stack[sp];

1. Проверка на переполнение и загрузка элемента в стек:

If sp<=sd then Begin stack[sp]:=x; sp:=sp+1 end Else \{ переполнение \}; Здесь sd - размерность стека.

1. Проверка наличия элементов и извлечение элемента стека:

If sp>1 then Begin sp:=sp-1; x:=stack[sp] end Else \{ антипереполнение \}

1. Чтение данных из указателя стека без извлечения элемента:

x:=stack[sp-1].

Программа 1. Работа со стеком.

{Реализованы основные базисные операции для работы со стеком. Программа написана на языке программирования Turbo-Pascal }

uses crt,graph; type PEl=^El; El=record n:byte; next:PEl; end;

var ster:array[1..3] of PEl; number: byte; p:PEl; th,l: integer; i:integer; nhod:word; s:string;

procedure hod(n,f,t:integer); begin if n>1 then begin hod(n-1,f,6-(f+t)); hod(1,f,t); hod(n-1,6-(f+t),t); end else begin p:=ster[f]; ster[f]:=ster[f]^.next; p^.next:=ster[t]; ster[t]:=p; inc(nhod); str(nhod,s); {**********************************************************} setfillstyle(1,0);bar(0,0,50,10); setcolor(2);outtextxy(0,0,s); setfillstyle(1,0);setcolor(0);p:=ster[f];i:=1; while p<>nil do begin p:=p^.next;inc(i);end; fillellipse(160*f,460-(i-1)*th,(number-ster[t]^.n+1)*l,10); setfillstyle(1,4);setcolor(4);p:=ster[t];i:=1; while p<>nil do begin fillellipse(160*t,460-(i-1)*th,(number- ster[t]^.n+1)*l,10);inc(i);p:=p^.next;end; {**********************************************************} { readkey;}{delay(50);} end; end;