Page 36 - 6110

Не менш важливим окремим випадком лінійного списку є
зв'язаний список, в якому кожний елемент окрім поля даних
зберігає також вказівник на наступний. Така структура дозволяє
зняти обмеження на зберігання лінійного списку в безперервній
області пам'яті.

9.2 Стек
Стек в інформатиці та програмуванні – це різновид лінійного
списку, структура даних, яка працює за принципом “останнім
прийшов - першим пішов” (LIFO: last in, first out). Всі операції
(наприклад, видалення елементу) в стеку можна проводити тільки з
одним елементом, який знаходиться на верхівці стеку та був
введений в стек останнім.
Стек можна розглядати як певну аналогію до стопки тарілок, з
якої можна взяти верхню, і на яку можна покласти верхню тарілку
(інша назва стеку – “магазин”, за аналогією з принципом роботи
магазину в автоматичній зброї).

9.2.1 Операції зі стеком
Push (“заштовхнути елемент”): елемент додається в стек та
розміщується в його верхівці. Розмір стеку збільшуеться на
одиницю. При перевищенні розміра стека граничної величини,
відбувається переповнення стека (stack overflow)
Pop (“виштовхнути елемент”): отримує елемент з верхівки
стеку. При цьому він видаляється зі стеку і його місце в верхівці
стеку займає наступний за ним елемент (відповідно до правила
LIFO), а розмір стеку зменшується на одиницю. При намаганні
“виштовхнути” елемент з вже пустого стеку, відбувається ситуація
“незаповнення” стеку (stack underflow).
Кожна з вищевказаних операцій зі стеком виконується за
фіксований час Т(1) і не залежить від розміру стеку.

9.2.2 Додаткові операції зі стеком (присутні не у всіх
реалізаціях стеку)
ІsEmpty - це перевірка наявності елементів в стеку. Результат:
істина (true), коли в стеку немає елементів.
ІsFull - це перевірка заповненості стека. Результат: істина, коли
додавання нового елементу неможливе.
Сlear: звільнити стек (видалити усі елементи).
Тop: отримати верхній елемент (без виштовхування).
Size: отримати розмір (кількість елементів) стека.
Swap: поміняти два верхніх елементи місцями.

35