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

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

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

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

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

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

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

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

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

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

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

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

(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   

# include   

void main (void)   

(   

char S [255];   

FILE * T;   

int I; BT X, Y;   

Zveno * NS;   

clrscr ();   

cout> S;   

T = fopen (S, "r");   

NS = NULL;   

while (! feof (T))   

(   

fgets (S, 255, T);   

I = 0;   

while (I = '0 '& & S [I] = '0' & & S [I]