Стек

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

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

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

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

Разновидности стеков

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

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

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

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

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

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

  1. безостановочная работа рекурсии;
  2. добавление новых элементов в стек после очередного витка рекурсии;
  3. переполнение из-за большого количества новых элементов и отсутствия места для их складирования.

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

Реализация стека

Стек можно реализовать на массиве, на динамическом массиве и на списке.

Реализация на массиве. Стек состоит из цепи элементов с обозначением [s1…s.top]. s1 — это начальный элемент в очереди, s.top — последний. Если s.top равен нулю, то такой стек считается пустым. Протестировать на наличие пустых элементов можно с помощью команды stackEmpty. Если данные будут сниматься с пустого стека, то это может приводить к ошибке.

Реализация на динамическом массиве. При таком способе исчезает риск выйти за границы массива при выполнении вставки нового элемента: операция push.

Реализация на списке. Для выполнения реализации нужно создать сам список и перечень операций на нем. Добавляться элементы к нему будут через привязку к верхнему — команды head.data (текущий головной элемент) и head.next (добавляемый элемент, который становится головным).

Освойте новую профессию

(рейтинг: 5, голосов: 5)
Добавить комментарий