Динамічні
структури даних: стеки
Стек - динамічна структура даних, що представляє із себе
упорядкований набір елементів, в якій додавання нових елементів і видалення
існуючих проводиться з одного кінця, званого вершиною стека.
За визначенням,
елементи витягуються з стека в порядку, зворотному їх додавання в цю
структуру, тобто діє принцип "останній прийшов - перший пішов".
Найбільш
наочним прикладом організації стека служить дитяча пірамідка, де додавання і
зняття кілець здійснюється саме згідно з визначенням стека.
Стек можна
організувати на базі будь-якої структури даних, де можна зберігати декількох
однотипних елементів і де можна реалізувати визначення стека: лінійний
масив, типізований файл, односпрямований або двонаправлений список. У
нашому випадку найбільш відповідним для реалізації стека є односпрямований
список, причому як вершини стека виберемо початок цього списку.
Виділимо типові
операції над стеком і його елементами:
додавання
елемента в стек;
видалення
елемента з стека;
перевірка, порожній
Чи стек;
перегляд
елемента в вершині стека без видалення;
очищення стека.
Реализуем ці
операції, використовуючи розроблений раніше модуль для односпрямований списків
(див. матеріал "Динамічні структури даних: списки
").
(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]
