Что такое структура данных стека? Это реализация в Pythonic Way.

Прежде чем приступить к изучению чего-либо, давайте немного мотивируемся:

«Плохие программисты беспокоятся о коде. Хорошие программисты беспокоятся о структурах данных и их взаимосвязях».

Линус Торвальдс

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

К концу блога вы будете знать:

Что, черт возьми, означает стек?
Как можно выполнять операции со стеком?
Как это реализовать на Python?
Каковы реальные приложения стека?

В этом блоге предполагается, что вы знаете, как определять классы Python и работать со списками и словарями.

1. Что такое структура данных?

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

В этой статье мы будем изучать структуру данных стека.

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

Стек — это линейная структура данных, которая следует принципу «последним пришел — первым обслужен» (LIFO). Это похоже на физическую стопку объектов, где последний объект, помещенный сверху, удаляется первым.

3. Операции, выполняемые в стеке

Основные операции над стеком приведены ниже:

Толкать
Поп

Давайте разберемся с ними один за другим.

а. Толкать

В структуре данных стека операция push относится к процессу добавления элемента на вершину стека. Новый элемент становится последним добавленным элементом и размещается над всеми существующими элементами.

б. Поп

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

4. Реализация на Python

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

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

Давайте сначала создадим класс с именем Stack, а также создадим конструктор этого класса:

# simplestack.py
class Stack:
    def __init__(self, maxsize):
        self.maxsize = maxsize
        self.items = []

Как видно из приведенного выше фрагмента кода, внутри конструктора мы инициализируем две переменные: одна — maxsize — для установки максимального размера стека, а другая — items — список для хранения элементов стека.

Теперь все операции, которые можно выполнять над стеком, реализованы с помощью методов класса Stack.

а) Толчок

Сначала мы проверяем, заполнен ли стек или нет, если стек не полон, то мы вставляем элемент в стек. Итак, сначала мы собираемся реализовать метод, который проверяет, заполнен ли стек или нет. Мы собираемся продолжить с приведенным выше кодом simplestack.py:

# simplestack.py
class Stack:
    def __init__(self, maxsize):
        self.maxsize = maxsize
        self.items = []

    def isFull(self):
        '''To check whether the stack is full or not'''
        if len(self.items) == self.maxsize:
            return True
        else:
            return False

Метод isFull() сначала проверяет, равна ли длина item list maxsize стека. Если они равны, возвращается True, в противном случае возвращается False.

Мы можем вызвать ошибку во время операции push, если стек заполнен. Для этого мы собираемся добавить класс с именем StackFullError внутри simplestack.py файла:

# simplestack.py
class StackFullError(Exception):
    def __init__(self, msg):
        super().__init__(msg)

class Stack:
    def __init__(self, maxsize):
        self.maxsize = maxsize
        self.items = []

    def isFull(self):
        '''To check whether the stack is full or not'''
        if len(self.items) == self.maxsize:
            return True
        else:
            return False

Теперь мы готовы реализовать метод push внутри класса Stack:

# simplestack.py
class StackFullError(Exception):
    def __init__(self, msg):
        super().__init__(msg)

class Stack:
    def __init__(self, maxsize):
        self.maxsize = maxsize
        self.items = []

    def isFull(self):
        '''To check whether the stack is full or not'''
        if len(self.items) == self.maxsize:
            return True
        else:
            return False

    def push(self, data):
        '''Push operation'''
        if self.isFull():
            raise StackFullError("Oops! Stack is full")

        self.items.append(data)
        return data

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

б) поп

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

# simplestack.py
class StackFullError(Exception):
    def __init__(self, msg):
        super().__init__(msg)

class Stack:
    def __init__(self, maxsize):
        self.maxsize = maxsize
        self.items = []

    def isFull(self):
        '''To check whether the stack is full or not'''
        if len(self.items) == self.maxsize:
            return True
        else:
            return False

    def isEmpty(self):
        '''To check whether the stack is empty or not'''
        if len(self.items) == 0:
            return True
        else:
            return False

    def push(self, data):
        '''Push operation'''
        if self.isFull():
            raise StackFullError("Oops! Stack is full")

        self.items.append(data)
        return data

Метод isEmpty() сначала проверяет, равна ли длина item list 0. Если он равен 0, возвращается True, в противном случае возвращается False.

Мы можем вызвать ошибку во время операции извлечения, если стек пуст. Для этого мы собираемся добавить класс с именем EmptyStackError внутри simplestack.py файла:

# simplestack.py
class StackFullError(Exception):
    def __init__(self, msg):
        super().__init__(msg)

class EmptyStackError(Exception):
    def __init__(self, msg):
        super().__init__(msg)

class Stack:
    def __init__(self, maxsize):
        self.maxsize = maxsize
        self.items = []

    def isFull(self):
        '''To check whether the stack is full or not'''
        if len(self.items) == self.maxsize:
            return True
        else:
            return False

    def isEmpty(self):
        '''To check whether the stack is empty or not'''
        if len(self.items) == 0:
            return True
        else:
            return False

    def push(self, data):
        '''Push operation'''
        if self.isFull():
            raise StackFullError("Oops! Stack is full")

        self.items.append(data)
        return data

Теперь мы готовы реализовать метод pop внутри класса Stack:

# simplestack.py
class StackFullError(Exception):
    def __init__(self, msg):
        super().__init__(msg)

class EmptyStackError(Exception):
    def __init__(self, msg):
        super().__init__(msg)

class Stack:
    def __init__(self, maxsize):
        self.maxsize = maxsize
        self.items = []

    def isFull(self):
        '''To check whether the stack is full or not'''
        if len(self.items) == self.maxsize:
            return True
        else:
            return False

    def isEmpty(self):
        '''To check whether the stack is empty or not'''
        if len(self.items) == 0:
            return True
        else:
            return False

    def push(self, data):
        '''Push operation'''
        if self.isFull():
            raise StackFullError("Oops! Stack is full")

        self.items.append(data)
        return data

    def pop(self):
        '''Pop operation'''
        if self.isEmpty():
            raise EmptyStackError("Oops! Stack is empty: cannot pop         an empty stack")

        item = self.items[len(self.items) - 1]
        del self.items[len(self.items) - 1]
        print(f'Top element {item} is deleted')
        return item

Как и выше, мы можем видеть внутри метода pop, если стек пуст, он вызывает пользовательское исключение, созданное нами, иначе он сначала сохраняет верхний элемент стека в переменной item и удаляет верхний элемент, а метод возвращает элемент, который мы просто удалили.

в) Верхний элемент

Если вы хотите получить верхний элемент текущего стека, вы также можете получить его, давайте добавим метод с именем top_element внутри класса Stack в файле simplestack.py:

# simplestack.py
class StackFullError(Exception):
    def __init__(self, msg):
        super().__init__(msg)

class EmptyStackError(Exception):
    def __init__(self, msg):
        super().__init__(msg)

class Stack:
    def __init__(self, maxsize):
        self.maxsize = maxsize
        self.items = []

    def isFull(self):
        '''To check whether the stack is full or not'''
        if len(self.items) == self.maxsize:
            return True
        else:
            return False

    def isEmpty(self):
        '''To check whether the stack is empty or not'''
        if len(self.items) == 0:
            return True
        else:
            return False

    def push(self, data):
        '''Push operation'''
        if self.isFull():
            raise StackFullError("Oops! Stack is full")

        self.items.append(data)
        return data

    def pop(self):
        '''Pop operation'''
        if self.isEmpty():
            raise EmptyStackError("Oops! Stack is empty: cannot pop         an empty stack")
        item = self.items[len(self.items) - 1]
        del self.items[len(self.items) - 1]
        print(f'Top element {item} is deleted')
        return item

    def top_element(self):
        ''' Returns top element of the stack '''
        if self.isEmpty():
            raise EmptyStackError("Oops! Stack is empty")
        top = self.items[len(self.items) - 1]
        return top

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

г) Все элементы

Чтобы распечатать все элементы стека, мы собираемся добавить метод с именем all_elements внутри класса Stack в файле simplestack.py:

# simplestack.py
class StackFullError(Exception):
    def __init__(self, msg):
        super().__init__(msg)

class EmptyStackError(Exception):
    def __init__(self, msg):
        super().__init__(msg)

class Stack:
    def __init__(self, maxsize):
        self.maxsize = maxsize
        self.items = []

    def isFull(self):
        '''To check whether the stack is full or not'''
        if len(self.items) == self.maxsize:
            return True
        else:
            return False

    def isEmpty(self):
        '''To check whether the stack is empty or not'''
        if len(self.items) == 0:
            return True
        else:
            return False

    def push(self, data):
        '''Push operation'''
        if self.isFull():
            raise StackFullError("Oops! Stack is full")

        self.items.append(data)
        return data

    def pop(self):
        '''Pop operation'''
        if self.isEmpty():
            raise EmptyStackError("Oops! Stack is empty: cannot pop an empty stack")
        item = self.items[len(self.items) - 1]
        del self.items[len(self.items) - 1]
        print(f'Top element {item} is deleted')
        return item

    def top_element(self):
        ''' Returns top element of the stack '''
        if self.isEmpty():
            raise EmptyStackError("Oops! Stack is empty")
        top = self.items[len(self.items) - 1]
        return top

    def all_elements(self):
        print("The elements of the stack are:")
        for item in self.items:
            print(item)

Теперь давайте воспользуемся этим классом Stack для выполнения операции со стеком:

# simplestack.py
# add it in the above code

s = Stack(5) # Stack with 5 elements

s.push(2)
s.push(12)
s.push(15)
s.push(14)

top1 = s.top_element()
print("Top element before poping: ", top1)

s.pop()

top2 = s.top_element()
print("Top element after poping: ", top2)

s.all_elements()

В приведенном выше коде мы видим, что мы создаем экземпляр класса Stack с 5 в качестве аргумента, который говорит нам, что он может хранить максимум 5 элементов. После этого мы поместили в стек четыре элемента: 2, 12, 15, 14. Затем мы получаем верхний элемент стека и печатаем его на терминале, затем извлекаем элемент из стека, вызывая метод pop(), чтобы увидеть эффект всплывающего окна, мы снова получаем верхний элемент стека и, наконец, печатаем все элементы текущего стека.

Окончательный полный код

Результат, который мы получили, запустив simplestack.py, приведен ниже:

$ python simplestack.py
Top element before poping:  14
Top element 14 is deleted
Top element after poping:  15
The elements of the stack are:
2
12
15

5. Реальные приложения

Применять, применять, применять любое понятие без практического применения просто бесполезно.

Структуры данных стека имеют несколько реальных приложений. Вот несколько примеров:

а. Вызовы функций

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

б. Отменить/Повторить операции

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

в. История веб-браузера

Веб-браузеры используют стек для хранения истории посещенных веб-страниц. Когда вы нажимаете кнопку «Назад», браузер извлекает самую последнюю страницу из стека, позволяя вам вернуться к предыдущей странице.

д. Оценка выражения

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

е. Анализ синтаксиса компилятора

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

6. Заключение

Если у вас все еще есть вопросы, не стесняйтесь обращаться к ним в разделе комментариев ниже! Чтобы узнать больше о стеке и его реализации в Python, вы также можете проверить другие материалы о стеке в Интернете.

Это на сегодня; увидимся в следующем блоге. Заботиться! Ваше здоровье!