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