Стек – що це таке і як він влаштований? Які види стеків бувають

Стек - що це таке і як він влаштований. Які види стеків бувають Визначення

Сьогодні розповім, що таке стек у програмуванні, як він влаштований та яких видів буває.

Це буде корисно для тих, хто в майбутньому планує серйозно працювати у сфері IT, адже це одна з основних концепцій програмування, що впливають на якість коду, але не стосуються конкретної мови.

Що таке стек простими словами

За традицією розповідь почну з визначення. Термін прийшов з англійської: слово stack перекладається як «пробка».

Стек – це один із способів організації та зберігання інформації в програмуванні. Якщо говорити професійною мовою, це одна із структур даних.

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

Термін виник у середині XX століття завдяки Алану Тьюрингу. У таких мовах програмування як Python та Lisp стеком називають будь-який список, тому що для них доступні операції виштовхування (pop англійською) та проштовхування (push). Для стека характерна ще одна операція – читання головного елемента (англійською – peek).

Як влаштований стек

Програмісти часто порівнюють стек зі стопкою однакових тарілок, адже він працює за схожим принципом: поставлена пізніше за всіх тарілка буде використовуватися першою. Навряд чи хтось намагатиметься витягувати тарілку із середини чи низу стоси. А щоб взяти другу тарілку зверху, потрібно обов’язково спочатку зняти першу.

У стеку важлива послідовність даних і тут застосовується лінійний зв’язок:

Дані йдуть один за одним, брати їх із довільного місця не можна.

Додавання або проштовхування (англійською – push) елемента можливе лише у вершину стека. Як тільки елемент стека використаний, він видаляється (процес називається виштовхуванням, або pop англійською), а верхнім елементом (top) стає наступним.

Виходячи з вищесказаного, виокремлю головний принцип роботи стека: дані, які потрапили останніми, використовуються першими. А якщо інформація потрапила першою, то вона має використовуватись останньою.

Схожим чином реалізована інша структура даних – черга (queue англійською). Але різниця лише в тому, що в черзі першим використовується найчастіше потрапив до неї елемент, а останнім — той, що пізніше за всіх. Для наочності уявіть чергу на касі супермаркету: хто першим посів місце, той першим розплатився. Все, як і у реальному житті.

Види стеків

Розрізняють два різновиди стеків:

стек викликів;

стек даних.

Розкажу докладніше про кожного з них.

Стек викликів

Стек дзвінків — це область пам’яті, де зберігається інформація про точки переходу між фрагментами програмного коду.

Цей вид використовується, коли в програмі є підпрограми і комп’ютеру потрібно запам’ятати місце, де програмний код переривався для виконання підпрограми, щоб повернутися до виконання основного коду. Якщо підпрограма також повернула певну інформацію, комп’ютер повинен запам’ятати і її, а потім ще й передати в код основної програми.

Стек практично завжди зберігається в оперативній пам’яті.

Оскільки кожен стек займає в ОЗУ певне місце, у разі занадто великої кількості подібних елементів може статися така ситуація, як переповнення. Чому це погано? Тому що в цьому випадку дані можуть потрапити в область пам’яті іншого елемента і перезаписати себе замість інформації, яка там повинна бути.

Це може призвести до таких проблем:

  • збоєм у роботі інших програм;
  • збоєм у роботі ПК;
  • використанням шкідливого коду в оперативну пам’ять.

Стек даних

Стек даних дуже схожий зі стеком викликів і працює з ним за тим же принципом: першим використовується останній доданий елемент, а останнім – той елемент, який потрапив туди раніше інших.

Стек даних зазвичай використовується для роботи зі складними типами інформації:

  • швидкого обходу дерев;
  • пошуку можливих маршрутів за графом;
  • аналізу розгалужених однотипних даних;
  • і так далі.

Ось і все, дорогі друзі. Тепер ви маєте уявлення про таке поняття, як стек, як він улаштований і які його різновиди існують. Сподіваюся, що вам все було зрозуміло і після прочитання статті питання відпадуть самі собою.

Я повернуся до вас із новою статтею вже зовсім скоро. Не забудьте також переглянути корисне відео на тему, яку ви знайдете під цією статтею.

Оцініть статтю