Стек
Стек — це абстрактні структури даних, які дають нам змогу динамічно зберігати та отримувати дані. Абстрактний тип даних означає щось, що існує в думках або як ідея, але не має фізичного чи конкретного існування. Ми не можемо фактично представити стек у фізичній пам’яті, як здатні це зробити за допомогою масиву, тому він й абстрактний.
Стек — це структура даних LIFO (Last In, First Out), що означає: останній увійшов — перший вийшов.
Одним із прикладів, який люди використовують стеки, є стос тарілок. Якщо ви вирішите зняти тарілку зі стосу тарілок, ви, очевидно, оберете найновішу, яку покладете зверху.
Є 2 засоби реалізації стека:
-
використання масиву;
-
використання однозв’язного списку.
Приклади методів стека:
-
push() — процедура додавання елемента до стека;
-
empty() — функція, яка перевіряє, чи пустий стек;
-
pop() — процедура видалення верхнього елемента стека;
-
size() — функція, яка перевіряє кількість елементів у стеку.
Застосування стека у реальному житті
-
Книги та одяг. Нагромаджені одна на одну книги — це чудовий приклад стека.
-
Поверхи в будівлі. Людина живе на верхньому поверсі й хоче вийти на вулицю. Для цього їй спочатку потрібно спуститися на перший поверх.
-
Браузери. Веббраузери використовують стек для відстеження історії вебсайтів. Якщо ви клацнете назад, то попередній сайт одразу відкриється.
-
Мобільний телефон. Журнал викликів у мобільних телефонах також використовує стек: щоб отримати журнал викликів від першої особи, потрібно погортати.