Учебное пособие по структуре данных стека Python

Реализуйте стек LIFO на Python. Запустите наш пример кода интерактивного стека, чтобы узнать ограничения по push, pop, peek и емкости.

Попробуйте в редакторе

Обзор

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

Стек поддерживает две основные операции: push (добавляет элемент вверх) и pop (удаляет последний добавленный элемент). Кроме того, операции просмотра или сверху позволяют осмотреть верхний элемент, не удаляя его.

В Python стеки можно легко создавать с помощью списка с методами .append() и .pop() или с помощью объектаcollections.deque, который предлагает оптимизированные операции двусторонней очереди за время O(1).

Код и вывод выполнения

Пользовательская реализация стека, использующая структуру списка Python для эмуляции функций push, pop и peek.

stack.py

Попробуйте в редакторе

class Stack:
    def __init__(self):
        self.items = []
        
    def is_empty(self):
        return len(self.items) == 0
        
    def push(self, item):
        self.items.append(item)
        print(f"Pushed: {item}")
        
    def pop(self):
        if self.is_empty():
            return "Underflow: Stack is empty"
        popped = self.items.pop()
        print(f"Popped: {popped}")
        return popped
        
    def peek(self):
        if self.is_empty():
            return "Stack is empty"
        return self.items[-1]
        
    def size(self):
        return len(self.items)

# Initialize stack
stack = Stack()
stack.push("Apples")
stack.push("Bananas")
stack.push("Cherries")

print(f"Current Stack Size: {stack.size()}")
print(f"Top Element (Peek): {stack.peek()}")

stack.pop()
print(f"Stack after Pop: {stack.items}")

Терминальный выход

Pushed: Apples
Pushed: Bananas
Pushed: Cherries
Current Stack Size: 3
Top Element (Peek): Cherries
Popped: Cherries
Stack after Pop: ['Apples', 'Bananas']

Пошаговая реализация

Управление функциями отмены в программных системах
Синтаксический анализ и проверка круглых скобок в компиляторах
Отслеживание стеков вызовов выполнения во время рекурсии в движках

Часто задаваемые вопросы

Почему Collections.deque предпочтительнее обычного списка для стеков?

Хотя списки удобны, на самом деле они представляют собой динамические массивы. При изменении размера перераспределение памяти может занять время O(n). Объект deque использует архитектуру двусвязного списка, гарантирующую операции отправки и извлечения O(1).

Могут ли стеки переполняться в Python?

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

Связанные темы

Учебное пособие по структуре данных очереди Python

Освойте операции с очередью FIFO в Python. Выполните и запустите наш пример интерактивной очереди, демонстрирующий методы постановки и удаления из очереди.

Реализация односвязного списка Python

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