Стек: що це таке і застосування

Стек - це феномен програмування і природне рішення. Стек відразу прийшов у комп'ютерне справу і став таким «рідним», як ніби саме з нього все починалося. Без стека не працює процесор, немає рекурсії та ефективні виклики функцій організувати неможливо. Будь-який алгоритм може обійтися без черги, списку, колекції, масиву або системи організованих об'єктів, але без пам'яті і стека не працює нічого, в тому числі все перераховане.

На зорі початку: процесор, пам'ять і стек

Ідеальна пам'ять забезпечує адресацію прямо до значення - це рівні машини та мови високого ступеня. У першому випадку процесор послідовно перебирає адреси пам'яті та виконує команди. У другому випадку програміст маніпулює масивами. В обох епізодах є: адреса = значення; індекс = значення. Адреса може бути абсолютним і відносним, індекс може бути цифровим і асоціативним. За адресою та індексу може перебувати іншу адресу, а не значення, але це деталі непрямої адресації. Без пам'яті процесор працювати не може, а без стека команд і даних - він, як човен без весел. Стос тарілок - традиційна новела про суть стека: поняття stack і переклад в общебытовом свідомості. Можна взяти тарілку знизу, можна брати тільки зверху, і тоді всі тарілки будуть цілі. Все, що останнім приходить в стек, йде першим. Ідеальне рішення. По суті, stack, як переклад однієї дії до іншого, трансформує уявлення про алгоритм як послідовність операцій.

Суть та поняття стеку

Процесор і пам'ять - основні конструктивні елементи комп'ютера. Процесор виконує команди, маніпулює адресами пам'яті, витягує і змінює значення за цими адресами. На мові програмування все це трансформується в змінні та їх значення. Суть стека і поняття last in first out " (LIFO) залишається незмінним.


Абревіатура LIFO вже не використовується так часто, як раніше. Ймовірно тому, що списки трансформувалися в об'єкти, а черги first in first out (FIFO) застосовуються по мірі необхідності. Динаміка типів даних втратила свою актуальність в контексті опису змінних, але придбала свою значимість на момент виконання виразів: тип даного визначається в момент його використання, а до цього моменту можна описувати що завгодно і як завгодно. Так, стек - що це таке? Тепер ви знаєте, що це питання недоречне. Адже без стека немає сучасного програмування. Будь виклик функції - це передача параметрів і адреси повернення. Функція може викликати іншу функцію - це знову передача параметрів і адреси повернення. Налагодити механізм виклику значень без стека - це зайва робота, хоча досяжне рішення, безумовно, можливе.

Багато запитують: "Стек - що це таке?". У контексті виклику функції він складається з трьох дій: збереження адреси повернення; збереження всіх переданих змінних або адреси на них; виклику функції. Як тільки викликана функція виконає свою місію, вона просто поверне управління за адресою повернення. Функція може викликати будь-яку кількість інших функцій, так як обмеження накладається тільки розміром стека.

Властивості стека

Стек - це не абстрактний тип даних, а реальний механізм. На рівні процесора - це «движок», який уточнює і доповнює роботу основного циклу процесора. Як бітова арифметика, стек фіксує прості і очевидні правила роботи. Це надійно і безпечно.
Характерні властивості стека - це його розмір та довжина елементів. На рівні процесора все визначається розрядністю, адресацією пам'яті і фізикою доступу до неї. Цікава особливість і традиція: стек росте вниз, тобто в бік зменшення адрес пам'яті, а пам'ять програм і даних - вгору. Це зазвичай, але не обов'язково. Тут важливий зміст - прийшов останнім, а пішов першим. Це дивно просте правило дозволяє будувати цікаві алгоритми роботи насамперед на мовах високого рівня. Тепер ви не будете питати, стек - що це таке. Бездоганна робота апаратного забезпечення вже дуже давно є нормою, але на передовому краї інформаційних технологій ідея стека знаходить нові та перспективні застосування. По суті не важливо, що таке стек на рівні процесора. Це природна складова архітектури комп'ютера. Але в програмуванні стек залежить від конкретного застосування і здібностей програміста.

Масиви, колекції, списки, черги Стек!

Часто люди задають питання: "Стек - що це таке?". "Програмування" та "систематизація" - цікаві поняття: вони не синоніми, але так тісно пов'язані. Програмування пройшло дуже швидко такий тривалий шлях, що досягнуті вершини здаються ідеальними. Швидше за все, це не так. Але очевидно інше.

Ідея стека стала звичною не тільки на рівні різних мов програмування, але і на рівні їх конструкцій і можливостей по створенню типів даних. Будь масив має push і pop, а поняття "перший і останній елементи масиву" стали традиційними. Раніше були просто елементи масиву, а сьогодні є: елементи масиву; перший елемент масиву; останній елемент масиву. Операція приміщення елемента в масив переміщує вказівник, а вилучення елемента з початку масиву або з його кінця має значення. По суті це той же стек, але в застосуванні до інших типів даних. Особливо примітно, що популярні мови програмування не мають конструкції stack. Але вони надають його ідею розробнику в повному обсязі.