стек # 151; динамічна структура даних, що являє собою упорядкований набір елементів, в якій додавання нових елементів і видалення існуючих проводиться з одного кінця, званого вершиною стека.
За визначенням, елементи витягуються з стека в порядку, зворотному їх додавання в цю структуру, тобто діє принцип "останній прийшов # 151; перший пішов ".
Найбільш наочним прикладом організації стека служить дитяча пірамідка, де додавання і зняття кілець здійснюється саме згідно з визначенням стека.
Стек можна організувати на базі будь-якої структури даних, де можливо зберігання декількох однотипних елементів і де можна реалізувати визначення стека: лінійний масив, типізований файл, односпрямований або двонаправлений список. У нашому випадку найбільш підходящим для реалізації стека є односпрямований список, причому в якості вершини стека виберемо початок цього списку.
Виділимо типові операції над стеком і його елементами:
Реалізуємо ці операції, використовуючи розроблений раніше модуль для односпрямованих списків (див. Матеріал "Динамічні структури даних: списки").
Використовуючи розроблені тут бібліотеки, вирішимо завдання.
Приклад. Написати програму, яка обчислює як ціле число значення виразів (без змінних), записаних (без помилок) в постфіксной формі в текстовому файлі. Кожен рядок файлу містить рівно один вислів.
Алгоритм рішення. Вираз проглядається зліва направо. Якщо зустрічається число, то його значення (як ціле) заноситься в стек, а якщо зустрічається знак операції, то з стека витягуються два останніх елементу (це операнди даної операції), над ними виконується операція і її результат записується в стек. В кінці в стеці залишається тільки одне число # 151; значення всього виразу.
Контрольні питання і завдання- Яку структуру даних називають стеком?
- На базі яких структур може бути організований стек?
- Наведіть з життя приклади організації чого-небудь за принципом стека.
- Використовуючи стек, надрукуйте символи цього рядка в зворотному порядку.
Сайт створено в системі uCoz