Page 55 - 4656

Алгоритми і структури даних. Лабораторний практикум.

Лабораторна робота № 7.
Стек

Мета: ознайомитись із поняттям стеку у програмуванні.
Алгоритм роботи стеку. Застосування індексів і з’єднань.

Теоретичні відомості

Стек в інформатиці та програмуванні - різновид лінійного
списку, структура даних, яка працює за принципом
(дисципліною) «останнім прийшов - першим пішов» (LIFO, англ.
last in, first out). Всі операції (наприклад, видалення елементу) в
стеку можна проводити тільки з одним елементом, який
знаходиться на верхівці стеку та був введений в стек останнім.
Стек можна розглядати як певну аналогію до стопки
тарілок, з якої можна взяти верхню, і на яку можна покласти
верхню тарілку (інша назва стеку — «магазин», за аналогією з
принципом роботи магазину в автоматичній зброї.
Операції зі стеком:
- push («заштовхнути елемент»): елемент додається в стек
та розміщується в його верхівці. Розмір стеку збільшується на
одиницю. При перевищенні розміру стека граничної величини,
відбувається переповнення стека (англ. stack overflow).
- pop («виштовхнути елемент»): отримує елемент з
верхівки стеку. При цьому він видаляється зі стеку і його місце в
верхівці стеку займає наступний за ним відповідно до правила
LIFO, а розмір стеку зменшується на одиницю. При намаганні
«виштовхнути» елемент з вже пустого стеку, відбувається
ситуація «незаповнення» стеку (англ. stack underflow).
Кожна з цих операцій зі стеком виконується за фіксований
час O(1) і не залежить від розміру стеку.
Додаткові операції (присутні не у всіх реалізаціях стеку):
1. isEmpty: перевірка наявності елементів в стеку;
результат: істина (true), коли стек порожній.
53