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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

from LinkedList import LinkedList
# LinkedList.py можно найти здесь: https://gist.github.com/nsafai/01395dc3d5fb48680fc0f14686f4b24e

class LinkedStack(object):

    def __init__(self, iterable=None):
        """Инициализация стека и добавление в него элементов, если они есть."""
        self.list = LinkedList() # Инициализация связного списка для наследования методов
        if iterable is not None:
            for item in iterable:
                self.push(item)

    def push(self, item):
        """"Добавление элементов в вершину стека
        Сложность: O(1), потому что мы меняем первый элемент списка"""
        self.list.prepend(item)
    
    def peek(self):
        """Возвращает верхний элемент стека, не удаляя его,
        или None, если стек пустой."""
        head = self.list.head
        return None if head is None else head.data
    
    def pop(self):
        """Удаляет и возвращает верхний элемент, если он есть, иначе выдаёт ValueError
        Сложность: O(1), потому что мы меняем первый элемент списка"""
        head = self.peek()
        self.list.delete(head)
        return head

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

class ArrayStack(object):

    def __init__(self, iterable=None):
        """Инициализация стека и добавление в него элементов, если они есть."""
        self.list = list() # Инициализация списка (встроенного в Python динамического массива) для хранения элементов
        if iterable is not None:
            for item in iterable:
                self.push(item)
    
    def push(self, item):
        """"Добавление элементов на вершину стека
        Сложность: O(1), пока мы не заполним всю выделенную память, затем O(n)"""
        self.list.append(item)

    def peek(self):
        """Возвращает верхний элемент стека, не удаляя его,
        или None, если стек пустой."""
        last_item_idx = len(self.list) - 1
        return None if last_item_idx < 0 else self.list[last_item_idx]
    
    def pop(self):
        """Удаляет и возвращает верхний элемент, если он есть, иначе выдаёт ValueError
        Сложность: O(1), так как нужно удалить лишь последний элемент"""
        if self.peek() == None:
            raise ValueError("list is empty")
        else:
            return self.list.pop()

Что лучше?

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

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

Массив

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

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

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

Заключение

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

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

Перевод статьи Nicolai Safai: What are Stacks useful for?

Поделиться статьей:

Вернуться к статьям