Как создать стек в Python с нуля

В этом уроке мы шаг за шагом создадим стек в Python. Стек представляет собой структуру данных LIFO (Last-in First-out).

Для создания стека в Python можно использовать класс с одним атрибутом типа list. Элементы стека сохраняются в списке с помощью метода push и извлекаются с помощью метода pop. Дополнительные методы позволяют получить размер стека и значение элемента наверху стека.

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

Давайте начнем строить!

Как начать создавать класс для стека

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

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

При работе со списком у вас есть свобода добавлять и удалять элементы в начале, в середине и в конце списка. То же самое не относится к стеку.

При работе со стеком вы можете только добавлять элемент на вершину стека и удалять элемент с вершины стека. Это потому, что по определению стек — это структура данных Last-in First-Out.

Начнем с создания класса Stack, имеющего атрибут списка elements.

Конструктор класса стека инициализирует элементы атрибута пустым списком.

class Stack:
    def __init__(self):
        self.elements = []

Первые две операции, которые мы хотим поддерживать в нашем стеке, — это push и pop:

• Push добавляет элемент наверх стека.
• Pop удаляет последний элемент с вершины стека.

Добавьте в наш класс два метода для поддержки операций push и pop:

def push(self, data):
    self.elements.append(data)

Для помещения данных наверх стека мы используем метод добавления списка.

def pop(self):
    return self.elements.pop()

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

Использование операций Push и Pop в нашем стеке

Давайте проверим класс, который мы создали на данный момент.

class Stack:
    def __init__(self):
        self.elements = []

    def push(self, data):
        self.elements.append(data)

    def pop(self):
        return self.elements.pop()

Создайте экземпляр стека и используйте __dict__ для просмотра атрибутов экземпляра.

stack = Stack()
print(stack.__dict__)

[output]
{'elements': []}

Как и ожидалось, единственным атрибутом экземпляра являются пустые элементы списка.

Затем вызовите метод push, а затем метод pop.

stack.push(3)
stack.push('test')
print(stack.pop())
print(stack.pop())

[output]
test
3

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

Примечание: обратите внимание, что первый элемент, возвращаемый pop(), — это строка «test», которая является вторым элементом, который мы поместили в стек. Это связано с природой стека LIFO.

Обработка ошибок при использовании Pop на пустом стеке

После двойного вызова метода pop в предыдущем разделе наш стек пуст.

Интересно, что произойдет, если мы снова вызовем операцию pop:

print(stack.pop())

Мы получаем следующее исключение:

Traceback (most recent call last):
   File "/opt/Python/Tutorials/create_stack.py", line 17, in 
     print(stack.pop())
   File "/opt/Python/Tutorials/create_stack.py", line 9, in pop
     return self.elements.pop()
 IndexError: pop from empty list

Это исключение не имеет полного смысла…

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

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

Давайте лучше разберемся с этой ошибкой…

Мы проверим, пуст ли внутренний список, прежде чем пытаться «извлечь» из него элемент:

def pop(self):
    if self.elements:
        return self.elements.pop()
    else:
        return None

Если список пуст, операция извлечения, выполненная над объектом стека, вернет None.

stack = Stack()
print(stack.pop())

Убедитесь, что приведенный выше оператор печати возвращает None.

Получить количество элементов в стеке Python

На данный момент мы не можем определить количество элементов в стеке.

Давайте добавим еще один метод, который возвращает количество элементов в стеке.

def size(self):
    return len(self.elements)

Новый метод просто возвращает длину элементов внутреннего списка с помощью функции len(). Давайте проверим это…

stack = Stack()
stack.push(3)
stack.push('test')
print("Number of elements in the stack: {}".format(stack.size()))

[output]
Number of elements in the stack: 2

Выглядит хорошо 🙂

Я также хотел бы знать, пуст ли стек. Вот новый метод, который это делает:

def empty(self):
    return True if self.size() == 0 else False

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

Обратите внимание, как метод empty() вызывает метод size().

Давайте проверим новый метод:

stack = Stack()
print(stack.empty())
stack.push(3)
print(stack.empty())

[output]
True
False

Мы получаем правильный ответ от метода empty().

Получить значение элемента наверху стека

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

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

Операция извлечения элемента из вершины стека называется peek.

def peek(self):
    return self.elements[-1]

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

stack = Stack()
stack.push('cat')
stack.push(3)
stack.push(1.2)
print(stack.peek())

[output]
1.2

Этот метод делает именно то, что мы хотели сделать.

Заключение

В этом уроке мы рассмотрели, как шаг за шагом реализовать стек в Python с помощью пользовательского класса.

Мы реализовали пять операций для нашего пользовательского стека:

• Push: чтобы добавить элемент наверх стека.
• Pop: извлечь элемент из верхней части стека.
• Size: для получения размера стека.
• Empty: для проверки того, пуст ли стек.
• Peek: получить значение элемента наверху стека.

Надеюсь, вам было полезно 🙂