Що таке стек і де він застосовується
Давайте обговоримо, що таке стек, а також де він застосовується.
Що таке стек
Коли я починав знайомитися з інформатикою, комп'ютера у мене не було, і я Новомосковскл книжки. Так і наткнувся на це нове для мене слово. У книжці говорилося, що англійське слово "stack" означає стопку - як правило, стопку тарілок. Оскільки це слово я прочитав, а не почув, то було важко зрозуміти, як саме його вимовляти - "стек", "стек" або взагалі "стік" (з тарілок же стікала вода при сушінні). Логічно. Тільки через роки виявилося, що правильно говорити - "стек".
Стек - це структура даних, тобто, принцип, за яким однорідні елементи даних зберігаються і обробляються. Розуміння структури даних дозволяє уявляти собі в голові те, як ці дані переміщаються і змінюються.
Незрозуміло, що таке однорідні елементи і структура даних? Подивіться на малюнок.
Тут однорідних елементів - це, звичайно, тарілки. Запхнувши їх в такий дерев'яний стек, ми можемо розглядати всю купу тарілок як єдиний предмет, як єдину структуру даних. Так про неї простіше говорити і думати ( "принеси стек, будь ласка"), так її простіше обробляти.
Зверніть увагу, що в це спеціальне тарілкові пристрій можна покласти і вийняти тарілку тільки зверху. Якщо в стосі 4 тарілки, і ви помістили зверху п'яту, то вийняти можна спочатку тільки її. Це і є принцип роботи стека.
Очевидно, що у стека є всього три операції: додати тарілку (так звана операція "push"), витягти ( "pop") і прочитати значення верхнього елементу (подивитися, залишилися тарілки або вже порожньо).
Де застосовується стек
Магазин з обоймою патронів - справжнісінький стек.
Коли лікар на прийомі говорить вам "Зачекайте поки що за дверима", ви виходите, але не стаєте в в кінець черги пацієнтів, а стаєте як би найпершим ( "сказали почекати!") - відсуваючи назад, в натовп того, хто був уже ось-ось у заповітних дверей, затьмарюючи його щастя. Вітаю: тепер ви - вершина стека.
Ви застосовуєте стек, коли починаєте кидати одні справи заради більш термінових - "потім дороблю!". Через те, що на зберігання елементів стека витрачається пам'ять, ви втомлюєтеся сильно швидше, ніж якби закінчували кожну задачу до того, як хапатися за наступну.
Лоток принтера з папером, гра "Ханойські вежі" - прості приклади стека.
Більш витончені приклади застосування стека - будь-яка рекурсивна завдання ( "так, стару ітерацію поки відкладу в стопку, а зараз треба обробляти нову ітерацію!"), Наприклад, перебір маршрутів дослідного робота в печері невідомої конфігурації.
Найперші калькулятори були безпосередньо зроблені як стеки. Замість "2 + 2" потрібно було ввводіть "2 + 2 +". Перші два елементи ( "операнди") клалися в стек, поки не буде введений плюс ( "оператор").
Удачі, і стежте, щоб ваш стік не переповнявся!
У наступній статті поговоримо про більш цікавою структурі даних: ви дізнаєтеся, що таке чергу.Leave a Reply
You must be logged in to post a comment.