Сьогодні розповім, що таке стек у програмуванні, як він влаштований та яких видів буває.
Це буде корисно для тих, хто в майбутньому планує серйозно працювати у сфері IT, адже це одна з основних концепцій програмування, що впливають на якість коду, але не стосуються конкретної мови.
Що таке стек простими словами
За традицією розповідь почну з визначення. Термін прийшов з англійської: слово stack перекладається як «пробка».
Стек – це один із способів організації та зберігання інформації в програмуванні. Якщо говорити професійною мовою, це одна із структур даних.
Вікіпедія дає визначення стеку як абстрактного типу даних, представленого у вигляді організованого за принципом LIFO списку елементів. Своєю чергою, абревіатура LIFO розшифровується як last in – first out, тобто “прийшов останнім, а вийшов першим”.
Термін виник у середині XX століття завдяки Алану Тьюрингу. У таких мовах програмування як Python та Lisp стеком називають будь-який список, тому що для них доступні операції виштовхування (pop англійською) та проштовхування (push). Для стека характерна ще одна операція – читання головного елемента (англійською – peek).
Як влаштований стек
Програмісти часто порівнюють стек зі стопкою однакових тарілок, адже він працює за схожим принципом: поставлена пізніше за всіх тарілка буде використовуватися першою. Навряд чи хтось намагатиметься витягувати тарілку із середини чи низу стоси. А щоб взяти другу тарілку зверху, потрібно обов’язково спочатку зняти першу.
У стеку важлива послідовність даних і тут застосовується лінійний зв’язок:
Дані йдуть один за одним, брати їх із довільного місця не можна.
Додавання або проштовхування (англійською – push) елемента можливе лише у вершину стека. Як тільки елемент стека використаний, він видаляється (процес називається виштовхуванням, або pop англійською), а верхнім елементом (top) стає наступним.
Виходячи з вищесказаного, виокремлю головний принцип роботи стека: дані, які потрапили останніми, використовуються першими. А якщо інформація потрапила першою, то вона має використовуватись останньою.
Схожим чином реалізована інша структура даних – черга (queue англійською). Але різниця лише в тому, що в черзі першим використовується найчастіше потрапив до неї елемент, а останнім — той, що пізніше за всіх. Для наочності уявіть чергу на касі супермаркету: хто першим посів місце, той першим розплатився. Все, як і у реальному житті.
Види стеків
Розрізняють два різновиди стеків:
стек викликів;
стек даних.
Розкажу докладніше про кожного з них.
Стек викликів
Стек дзвінків — це область пам’яті, де зберігається інформація про точки переходу між фрагментами програмного коду.
Цей вид використовується, коли в програмі є підпрограми і комп’ютеру потрібно запам’ятати місце, де програмний код переривався для виконання підпрограми, щоб повернутися до виконання основного коду. Якщо підпрограма також повернула певну інформацію, комп’ютер повинен запам’ятати і її, а потім ще й передати в код основної програми.
Стек практично завжди зберігається в оперативній пам’яті.
Оскільки кожен стек займає в ОЗУ певне місце, у разі занадто великої кількості подібних елементів може статися така ситуація, як переповнення. Чому це погано? Тому що в цьому випадку дані можуть потрапити в область пам’яті іншого елемента і перезаписати себе замість інформації, яка там повинна бути.
Це може призвести до таких проблем:
- збоєм у роботі інших програм;
- збоєм у роботі ПК;
- використанням шкідливого коду в оперативну пам’ять.
Стек даних
Стек даних дуже схожий зі стеком викликів і працює з ним за тим же принципом: першим використовується останній доданий елемент, а останнім – той елемент, який потрапив туди раніше інших.
Стек даних зазвичай використовується для роботи зі складними типами інформації:
- швидкого обходу дерев;
- пошуку можливих маршрутів за графом;
- аналізу розгалужених однотипних даних;
- і так далі.
Ось і все, дорогі друзі. Тепер ви маєте уявлення про таке поняття, як стек, як він улаштований і які його різновиди існують. Сподіваюся, що вам все було зрозуміло і після прочитання статті питання відпадуть самі собою.
Я повернуся до вас із новою статтею вже зовсім скоро. Не забудьте також переглянути корисне відео на тему, яку ви знайдете під цією статтею.