Что такое Стек — определение, базовые понятия, как он устроен стек, виды и переполнение стека

Здравствуйте, уважаемые читатели блога KtoNaNovenkogo.ru. Продолжаю объяснять сложные компьютерные термины простыми словами. Сегодня расскажу, что такое стек в программировании, как он устроен и каких видов бывает.

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

Определение понятия «стек» простыми словами

Стек (от англ. stack — стопка) — структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел — первым вышел» (last-in, first-out — LIFO).

По традиции рассказ начну с определения. Термин пришел из английского языка: слово stack переводится как «пробка».

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

Википедия дает определение стеку как абстрактному типу данных, представленному в виде организованного по принципу LIFO списка элементов. В свою очередь, аббревиатура LIFO расшифровывается как last in — first out, то есть «пришел последним, а вышел первым».

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

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

Программисты часто сравнивают стек со стопкой одинаковых тарелок, ведь он работает по схожему принципу: поставленная позже всех тарелка будет использоваться первой. Вряд ли кто-то будет пытаться вытягивать тарелку из середины или низа стопки. А чтобы взять вторую тарелку сверху, нужно в обязательном порядке сначала снять первую.

В стеке важна последовательность данных и здесь применима линейная связь:

Данные следуют друг за другом, брать их из произвольного места нельзя.

Добавление или проталкивание (на английском — push) элемента возможно только в вершину стека. Как только элемент стека использован, он удаляется (процесс называется выталкиванием, или pop на английском), а верхним элементом (top) становится следующий.

Исходя из вышесказанного, выделю главный принцип работы стека: данные, которые попали последними, используются первыми. А если информация попала первой, то она должна использоваться последней.

Похожим образом реализована другая структура данных — очередь (queue на английском). Но разница лишь в том, что в очереди первым используется раньше всех попавший в нее элемент, а последним — тот, что позже всех. Для наглядности представьте очередь на кассе супермаркета: кто первым занял место, тот первым и расплатился. Все, как и в реальной жизни.

Виды стеков

Различают две разновидности стеков:

стек вызовов;
стек данных.

Расскажу подробнее о каждом из них.

Стек вызовов

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

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

Стек практически всегда хранится в оперативной памяти. Так как каждый стек занимает в ОЗУ определенное место, в случае слишком большого количества подобных элементов может случиться такая ситуация как переполнение. Почему это плохо? Потому что в этом случае данные могут попасть в область памяти другого элемента и перезаписать себя вместо той информации, которая там должна быть.

Это чревато следующими проблемами:

сбоем в работе других программ;
сбоем в работе ПК;
внедрением вредоносного кода в оперативную память.

Стек данных

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

Стек данных обычно используется для работы со сложными типами информации:

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

Вот и все, дорогие друзья. Теперь вы имеете представление о таком понятии, как стек, как он устроен и каковы его разновидности существуют. Надеюсь, что вам все было понятно и после прочтения статьи вопросы отпадут сами собой. Если нет, то спускайтесь в комментарии к публикации, спрашивайте, что было непонятно, а другие читатели блога KtoNaNovenkogo.ru помогут найти ответы.

Я вернусь к вам с новой статьей уже совсем скоро. Не забудьте также посмотреть полезное видео по теме, которое вы найдете под этой статьей.