Стеки на стеки на стеки... но не слишком много.

Как начинающий программист, я всегда находил ошибку системного стека в ruby ​​одним из самых забавных сообщений об ошибках. «SystemStackError: слишком глубокий уровень стека». Было что-то забавное в идее, что компьютерная программа завершает работу, потому что что-то «слишком глубоко». Я и не подозревал, что это вряд ли имеет какое-либо отношение к абстрактному «глубокому», на которое ссылаются люди, когда говорят: «это слишком глубоко, я выхожу».

Вместо этого эта глубина предназначалась для совершенно другого типа данных. Нечто, называемое «стеком», переполняется, и это означало, что мой метод снова и снова вызывал сам себя в бесконечном цикле рекурсии. Почему это происходит и что означает переполнение стека? Оказывается, ответ начинается с понимания того, что такое «стек» на самом деле.

Итак, что такое стек?

В самой абстрактной форме стек относится к чему-то более широкому, чем программирование в целом. Стек — это абстрактный тип данных, который позволяет пользователю извлекать и помещать данные только в одну точку его структуры. В качестве альтернативы стек называется LIFO (последним пришел, первым ушел). Стек — это просто структура данных, содержащая целую кучу элементов, которыми можно манипулировать только из одной точки, имея только две основные операции: push и pop.

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

Итак, как это применимо к программированию?

Механизм выполнения Javascript состоит из двух блоков: кучи памяти и стека вызовов (где находятся все функции). А стек вызовов — вы уже догадались! — просто стопка! Почему? Подумайте о том, как кто-то будет читать книгу. Они не стали бы перескакивать через несколько страниц, анализируя то, что происходит в середине главы 5 сразу после завершения главы 2, а затем возвращаясь к главе 3, чтобы узнать, что происходит с тем-то и тем-то. Это не будет хорошей историей! Точно так же Javascript читает программу сверху вниз, как мы читаем книгу, страницу за страницей, и добавляет каждый элемент один за другим в стек для нас.

Но как он переливается?

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

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

Стопки на стеллажи на стеллажи... но не слишком много.

Итак, у вас есть это! Оказывается, эта забавная ошибка, с которой я столкнулся как начинающий программист, ссылалась на что-то большее, чем просто программирование. Концепция стека существует повсюду вокруг нас. Как только я узнал о том, что такое стек, я мог видеть их повсюду! Когда мы читаем книги, мы перемещаемся по стопке. Когда мы нажимаем кнопку «Назад» в нашем браузере несколько раз, мы складываемся. Когда мы нажимаем «Отменить/Повторить» в текстовом документе, мы складываемся! Даже пока я пишу этот блог, я складываю! И это тоже не случайность.

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

По правде говоря, стеки были сделаны для нас!

Ресурсы: