Динамічні структури даних: стеки

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

За визначення, елементи витягуються з стека в порядку, зворотному їх додаванню в цю структуру, тобто діє принцип "останній прийшов - перший пішов ".

Найбільш наочним прикладом організації стека служить дитяча пірамідка, де додавання і зняття кілець здійснюється саме згідно з визначенням стека.

Стек можна організувати на базі будь-якої структури даних, де можна зберігати кількох однотипних елементів і де можна реалізувати визначення стека: лінійний масив, типізований файл, односпрямований або двонаправлений список. У нашому випадку найбільш відповідним для реалізації стека є односпрямований список, причому як вершини стека виберемо початок цього списку.

Виділимо типові операції над стеком і його елементами:

додавання елемента в стек;

видалення елемента з стека;

перевірка, чи порожній стек;

перегляд елемента в вершині стека без видалення;

очищення стека.

Реалізуємо ці операції, використовуючи розроблений раніше модуль для односпрямований списків (див. матеріал "Динамічні структури даних: списки").        

(Turbo Pascal, файл STACK.PAS)   

Unit Stack;   

Interface   

Uses Spisok;   

Procedure V_Stack (Var   Versh: U; X: BT);   

Procedure   Iz_Stack (Var Versh: U; Var X: BT);   

Function Pust (Versh:   U): Boolean;   

Function   V_Vershine (Versh: U): BT;   

Procedure   Ochistka (Var Versh: U);   

Implementation   

Procedure V_Stack;   

Begin   

V_Nachalo (Versh, X)   

End;   

Procedure Iz_Stack;   

Begin   

Iz_Nachala (Versh, X)   

End;   

Function Pust;   

Begin   

Pust: = Versh = Nil   

End;   

Function V_Vershine;   

Begin   

V_Vershine: = Versh ^. Inf   

End;   

Procedure Ochistka;   

Begin   

Spisok.Ochistka (Versh)   

End;   

Begin   

End.         

        

/* C + +, файл STACK.CPP */   

# include   "SPIS.CPP"   

Zveno * V_Stack (Zveno   * Versh, BT X)   

(   

return   V_Nachalo (Versh, X);   

)   

Zveno * Iz_Stack (Zveno   * Versh)   

(   

return   Iz_Nachala (Versh);   

)   

int SPust (Zveno   * Versh)   

(   

return! Versh;   

)   

BT V_Vershine (Zveno   * Versh)   

(   

return Versh-> Inf;   

)   

Zveno * Chistka (Zveno   * Versh)   

(   

while (! Pust (Versh))   Versh = Iz_Stack (Versh);   

return Versh;   

)     

Використовуючи розроблені тут бібліотеки, вирішимо завдання.

Приклад. Написати програму, яка обчислює як ціле число значення виразів (без змінних), записаних (без помилок) в постфіксной формі в текстовому файлі. Кожен рядок файлу містить рівно один вислів.

Алгоритм рішення. Вираз проглядається зліва направо. Якщо зустрічається число, то його значення (як ціле) заноситься в стек, а якщо встечаются знак операції, то з стека витягуються два останніх елементу (це операнди даної операції), над ними виконується операція і її результат записується в стек. Наприкінці в стеку залишається тільки одне число - значення всього виразу.        

(Turbo Pascal, файл ST2.PAS)   

Program St2;   

Uses Spisok, Stack;   

Const Znak = ['+',   '-', '*','/'];   

Var S, S1: String;   

T: Text;   

I, N: Byte;   

X, Y: BT; Code: Integer;   

NS: U;   

Begin   

Write ( 'Введіть ім'я файлу:   '); ReadLn (S1);   

Assign (T, S1); ReSet (T);   

NS: = Nil;   

While Not Eof (T) Do   

Begin   

ReadLn (T, S); I: = 1;   

While I <= Length (S) Do   

Begin   

If S [I] In ['0 '.. '9']   

Then   

Begin   

N: = I;   

While S [I] In ['0 '.. '9'] Do   

I: = I + 1;   

Val (Copy (S, N, I - N), X, Code);   

V_Stack (NS, X);   

End   

Else   

If S [I] In Znak   

Then   

Begin   

Iz_Stack (NS, X);   

Iz_Stack (NS, Y);   

Case S [I] Of   

'+': X: = X + Y;   

'-': X: = Y - X;   

'*': X: = X * Y;   

'/': X: = Y Div X   

End;   

V_Stack (NS, X)   

End;   

I: = I + 1   

End;   

Iz_Stack (NS, X);   

WriteLn (S, '=', X);   

End   

End.         

        

/* C + +, файл ST2.CPP */   

# include   "STACK.CPP"   

# include <   string.h>   

# include   

void main (void)   

(   

char S [255];   

FILE * T;   

int I; BT X, Y;   

Zveno * NS;   

clrscr ();   

cout << "Введіть ім'я файлу:   "; Cin>> S;   

T = fopen (S, "r");   

NS = NULL;   

while (! feof (T))   

(   

fgets (S, 255, T);   

I = 0;   

while (I <= strlen (S) -1)   

(   

if (S [I]> = '0 '& & S [I] <= '9')   

(   

X = 0;   

while (S [I]> = '0 '& & S [I] <= '9')   (X = X * 10 + (S [I] - '0 '); I + +;)   

NS = V_Stack (NS, X);   

)   

else   

if   (S [I ]=='+'|| S [I ]=='-'|| S [I ]=='/'|| S [I ]=='*')   

(   

X = V_Vershine (NS);   

NS = Iz_Stack (NS);   

Y = V_Vershine (NS);   

NS = Iz_Stack (NS);   

switch (S [I]) (   

case '+': X + = Y; break;   

case '-': X = Y - X; break;   

case '*': X *= Y; break;   

case '/': X = Y/X; break;)   

NS = V_Stack (NS, X);   

)   

I + +;   

)   

X = V_Vershine (NS);   

NS = Iz_Stack (NS);   

cout <"   <   

)     

Список літератури

Для підготовки даної роботи були використані матеріали з сайту http://comp-science.narod.ru