Что такое стек

Посте­пен­но осва­и­ва­ем спо­со­бы орга­ни­за­ции и хра­не­ния дан­ных. Уже было про дере­вья, попро­бу­ем про сте­ки. Это для тех, кто хочет в буду­щем серьёз­но рабо­тать в ИТ: одна из фун­да­мен­таль­ных кон­цеп­ций, кото­рая вли­я­ет на каче­ство ваше­го кода, но не каса­ет­ся какого-то кон­крет­но­го язы­ка программирования. 

👉 Стек — это одна из струк­тур дан­ных. Струк­ту­ра дан­ных — это то, как хра­нят­ся дан­ные: напри­мер, свя­зан­ные спис­ки, дере­вья, оче­ре­ди, мно­же­ства, хеш-таблицы, кар­ты и даже кучи (heap). 

Как устроен стек

Стек хра­нит после­до­ва­тель­ность дан­ных. Свя­за­ны дан­ные так: каж­дый эле­мент ука­зы­ва­ет на тот, кото­рый нуж­но исполь­зо­вать сле­ду­ю­щим. Это линей­ная связь — дан­ные идут друг за дру­гом и нуж­но брать их по оче­ре­ди. Из сере­ди­ны сте­ка брать нельзя.

👉 Глав­ный прин­цип рабо­ты сте­ка — дан­ные, кото­рые попа­ли в стек недав­но, исполь­зу­ют­ся пер­вы­ми. Чем рань­ше попал — тем поз­же исполь­зу­ет­ся. После исполь­зо­ва­ния эле­мент сте­ка исче­за­ет, и верх­ним ста­но­вит­ся сле­ду­ю­щий элемент.

После использования элемент стека исчезает, и верхним становится следующий элемент.

Клас­си­че­ский спо­соб объ­яс­не­ния прин­ци­пов сте­ка зву­чит так: пред­ставь­те, что вы мое­те посу­ду и скла­ды­ва­е­те оди­на­ко­вые чистые тарел­ки стоп­кой друг на дру­га. Каж­дая новая тарел­ка — это эле­мент сте­ка, а вы про­сто добав­ля­е­те их по одной в стек.

Когда кому-то пона­до­бит­ся тарел­ка, он не будет брать её сни­зу или из сере­ди­ны — он возь­мёт первую свер­ху, потом сле­ду­ю­щую и так далее. 

🤔 Есть струк­ту­ра дан­ных, похо­жая на стек, — назы­ва­ет­ся оче­редь, или queue. Если в сте­ке кто послед­ний при­шёл, того пер­вым забе­рут, то в оче­ре­ди наобо­рот: кто рань­ше при­шёл, тот рань­ше ушёл. Мож­но пред­ста­вить оче­редь в мага­зине: кто рань­ше её занял, тот пер­вый дошёл до кас­сы. Оче­редь — это тоже линей­ный набор дан­ных, но обра­ба­ты­ва­ет­ся по-другому. 

Стек вызовов

В про­грам­ми­ро­ва­нии есть два вида сте­ка — стек вызо­вов и стек данных. 

Когда в про­грам­ме есть под­про­грам­мы — про­це­ду­ры и функ­ции, — то ком­пью­те­ру нуж­но пом­нить, где он пре­рвал­ся в основ­ном коде, что­бы выпол­нить под­про­грам­му. После выпол­не­ния он дол­жен вер­нуть­ся обрат­но и про­дол­жить выпол­нять основ­ной код. При этом если под­про­грам­ма воз­вра­ща­ет какие-то дан­ные, то их тоже нуж­но запом­нить и пере­дать в основ­ной код.

Что­бы это реа­ли­зо­вать, ком­пью­тер исполь­зу­ет стек вызо­вов — спе­ци­аль­ную область памя­ти, где хра­нит дан­ные о точ­ках пере­хо­да меж­ду фраг­мен­та­ми кода. 

Допу­стим, у нас есть про­грам­ма, внут­ри кото­рой есть три функ­ции, при­чём одна из них внут­ри вызы­ва­ет дру­гую. Нари­су­ем, что­бы было понятнее:

Допустим, у нас есть программа, внутри которой есть три функции, причём одна из них внутри вызывает другую.

Про­грам­ма запус­ка­ет­ся, потом идёт вызов синей функ­ции. Она выпол­ня­ет­ся, и про­грам­ма про­дол­жа­ет с того места, где оста­но­ви­лась. Потом выпол­ня­ет­ся зелё­ная функ­ция, кото­рая вызы­ва­ет крас­ную. Пока крас­ная не закон­чит рабо­ту, все осталь­ные ждут. Как толь­ко крас­ная закон­чи­лась — про­дол­жа­ет­ся зелё­ная, а после её окон­ча­ния про­грам­ма про­дол­жа­ет свою рабо­ту с того же места.

А вот как стек помо­га­ет это реа­ли­зо­вать на практике:

Как работает стек

Про­грам­ма дошла до синей функ­ции, сохра­ни­ла точ­ку, куда ей вер­нуть­ся после того, как закон­чит­ся функ­ция, и если функ­ция вер­нёт какие-то дан­ные, то про­грам­ма тоже их полу­чит. Когда синяя функ­ция закон­чит­ся и про­грам­ма полу­чит верх­ний эле­мент сте­ка, он авто­ма­ти­че­ски исчез­нет. Стек сно­ва пустой.

Когда синяя функция закончится и программа получит верхний элемент стека, он автоматически исчезнет. Стек снова пустой.

С зелё­ной функ­ци­ей всё то же самое — в стек зано­сит­ся точ­ка воз­вра­та, и про­грам­ма начи­на­ет выпол­нять зелё­ную функ­цию. Но внут­ри неё мы вызы­ва­ем крас­ную, и вот что происходит:

При вызове красной функции в стек помещается новый элемент с информацией о данных, точке возврата и указанием на следующий элемент.

При вызо­ве крас­ной функ­ции в стек поме­ща­ет­ся новый эле­мент с инфор­ма­ци­ей о дан­ных, точ­ке воз­вра­та и ука­за­ни­ем на сле­ду­ю­щий эле­мент. Это зна­чит, что когда крас­ная функ­ция закон­чит рабо­ту, то ком­пью­тер возь­мёт из сте­ка адрес воз­вра­та и вер­нёт управ­ле­ние сно­ва зелё­ной функ­ции, а крас­ный эле­мент исчез­нет. Когда и зелё­ная закон­чит рабо­ту, то ком­пью­тер из сте­ка возь­мёт новый адрес воз­вра­та и про­дол­жит рабо­ту со ста­ро­го места.

Переполнение стека

Почти все­гда стек вызо­вов хра­нит­ся в опе­ра­тив­ной памя­ти и име­ет опре­де­лён­ный раз­мер. Если у вас будет мно­го вло­жен­ных вызо­вов или рекур­сия с очень боль­шой глу­би­ной вло­жен­но­сти, то может слу­чить­ся такая ситуация:

  • рекур­сия всё рабо­та­ет и работает;
  • при каж­дом новом вит­ке рекур­сии в стек добав­ля­ют­ся новый элемент;
  • когда эле­мен­тов будет слиш­ком мно­го, память закон­чит­ся, новые эле­мен­ты неку­да будет скла­ды­вать и про­изой­дёт пере­пол­не­ние стека.

Пере­пол­не­ние — это пло­хо: дан­ные могут зале­зать в чужую область памя­ти и запи­сы­вать себя вме­сто преж­них дан­ных. Это может при­ве­сти к сбою в рабо­те дру­гих про­грамм или само­го ком­пью­те­ра. Ещё таким обра­зом мож­но внед­рить в опе­ра­тив­ную память вре­до­нос­ный код: если про­грам­ма пло­хо рабо­та­ет со сте­ком, мож­но спе­ци­аль­но вызвать пере­пол­не­ние и запи­сать в память что-нибудь вредоносное.

Стек данных

Стек дан­ных очень похож на стек вызо­вов: по сути, это одна боль­шая пере­мен­ная, похо­жая на спи­сок или мас­сив. Его чаще все­го исполь­зу­ют для рабо­ты с дру­ги­ми слож­ны­ми типа­ми дан­ных: напри­мер, быст­ро­го обхо­да дере­вьев, поис­ка всех воз­мож­ных марш­ру­тов по гра­фу, — и для ана­ли­за раз­ветв­лён­ных одно­тип­ных данных.

Стек дан­ных рабо­та­ет по тако­му же прин­ци­пу, как и стек вызо­вов — эле­мент, кото­рый доба­ви­ли послед­ним, дол­жен исполь­зо­вать­ся первым.

Что дальше

А даль­ше пого­во­рим про тип дан­ных под назва­ни­ем «куча». Да, такой есть, и с ним тоже мож­но эффек­тив­но рабо­тать. Стей тюнед.

Текст и иллю­стра­ции:
Миша Поля­нин

Редак­тор:
Мак­сим Ильяхов

Кор­рек­тор:
Ира Михе­е­ва

Иллю­стра­тор:
Даня Бер­ков­ский

Вёрст­ка:
Маша Дро­но­ва

Достав­ка:
Олег Веш­кур­цев