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

Категория: Что такое?

– Автор: Игорь (Администратор)

В рамках данной статьи, я расскажу вам что такое стек, а так же для чего он нужен и где применяется.

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

Стек (stack) - это метод представления однотипных данных (можно просто называть типом) в порядке LIFO (Last In - First Out, что означает "первый вошел - последний вышел"). Стоит упомянуть, что в русской технике его так же называют "магазином". И речь тут не о продуктовом магазине, а о рожке с патронами для оружия, так как принцип весьма схож - первый вставленный патрон будет использован последним.

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

Чтобы лучше понять, приведу жизненный пример. Допустим у вас есть стопка листов. Каждый исписанный лист вы кладете рядом, а каждый следующий поверх остальных. Чтобы достать к примеру, самый первый лист из полученной стопки, вам необходимо вытащить все остальные листы. Вот по этому же самому принципу и устроен stack. То есть, каждый последний добавленный элемент становится верхним и чтобы достать, к примеру, самый первый элемент необходимо вытащить все остальные.

Для чего нужен стек? Основное предназначение это решение типовых задач, где необходимо поддерживать последовательность состояний чего-либо или где нужно инверсионное представление данных (то есть в обратную сторону).

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

Какие операции у stack? Основных операций всего две:

1. Добавление элемента в вершину стека называется push

2. Извлечения верхнего элемента называется pop

Но, так же периодически можно встретить реализацию операции чтения верхнего элемента без его извлечения - называется peek.

Как организуется стек? Обычно стек реализуется двумя вариантами:

1. С помощью массива и переменной, которая указывает на ячейку с вершиной стека

2. С помощью связанных списков

У каждого из этих 2-х вариантов есть свои плюсы и минусы. Например, связанные списки более безопасны в плане применения, так как каждый добавляемый элемент помещается в динамически созданную структуру (нет проблем с количеством элементов - нет дырок безопасности, позволяющих свободно перемещаться в памяти программы). Однако, в плане хранения и быстроты использования они менее эффективны (требуют дополнительное место для хранения указателей; разбросаны в памяти, а не расположены друг за другом, как в массивах).

Теперь, вы знаете что такое стек, а так же зачем он нужен и для чего применяется.