Стек и его реализация

Стек работает по принципу LIFO: последним положенный выходит первым. Три основные операции — push, pop, peek — касаются только вершины и выполняются за O(1). Это пример ADT: его можно реализовать на разных структурах.

Стек на list

Самый простой стек в Python — list: append кладёт наверх, pop() снимает. Вершина — конец списка, потому что insert(0, x) / pop(0) в начале сдвигают все элементы (O(n)). Когда ёмкость list кончается, он расширяется, поэтому push — O(1) лишь амортизированно (амортизационный анализ). На пустом стеке pop и peek должны бросать IndexError: молчаливый None прячет ошибку.

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

    def push(self, item):
        self._items.append(item)

    def pop(self):
        if not self._items:
            raise IndexError("pop from empty stack")
        return self._items.pop()