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