13,8 тыс подписчиков

Для чего нужны стеки?

2 минуты

241 прочтение

31 марта 2020

Когда я узнал, что такое стек, мне стало интересно его практическое применение. Оказалось, что чаще всего эта структура используется для имплементации операции “Отмена” ( то есть, ⌘+Z или Ctrl+Z).

Чтобы понять, как это работает, разберемся с определением стека.

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

Стек — список элементов, который может быть изменён лишь с одной стороны, называющейся вершиной стека.

Представьте приспособление для раздачи тарелок, в котором тарелки стоят в стопке. Новые тарелки можно добавлять только поверх уже имеющихся, а брать можно лишь сверху. Таким образом, чем позже тарелку положат в стопку, тем раньше её оттуда возьмут. В рамках структур данных это называется LIFO-принципом (последним пришёл — первым ушёл).

Если использовать терминологию, то стек поддерживает операции добавления (push) и удаления (pop) элементов на его вершине.

Зачем использовать стек для отмены?

Потому что обычно мы хотим отменить последнее действие.

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

Что произойдёт, если ни одно действие не будет отменено? Стек ведь станет огромным!

Верно. Если не удалять элементы из стека отмены, то есть не использовать операцию отмены, то он станет очень большим. Именно поэтому такие приложения, как Adobe Photoshop, с увеличением времени работы над файлом используют всё больше и больше оперативной памяти. Стек отмены хранит все действия, произведённые над файлом, в памяти до тех пор, пока вы не сохраните и не закроете файл.

Имплементация стека

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

Стек на связном списке:

Стек на массиве:

Что лучше?

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

Однако есть некоторые нюансы, которые стоит учесть.

Массив

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

Связный список

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

Заключение

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

Как видим, между этими двумя реализациями стека практически нет различий — используйте ту, что нравится вам.