J. Стек

Ещё одной полезной коллекцией является стек реализующий принцип «Последний пришёл – первый ушёл». Его часто представляют как стопку карт или магазин пистолета, где приходящие элементы закрывают выход уже находящимся в коллекции.

Реализуйте класс Stack, который не имеет параметров инициализации, но поддерживает методы:

• push(item) — добавить элемент в конец стека;
• pop() — «вытащить» первый элемент из стека;
• is_empty() — проверяет стек на пустоту.

Примечание

Ваше решение должно содержать только классы и функции.
В решении не должно быть вызовов инициализации требуемых классов.

Пример

Ввод

stack = Stack()
for item in range(10):
    stack.push(item)
while not stack.is_empty():
    print(stack.pop(), end=" ")

Вывод

9 8 7 6 5 4 3 2 1 0 

Ввод

stack = Stack()
for item in ("Hello,", "world!"):
    stack.push(item)
while not stack.is_empty():
    print(stack.pop())

Вывод

world!
Hello,

Решение

Эта задача отличается от предыдущей только тем, что метод pop() удаляет не первый, а последний элемент нашего списка. Поэтому я не буду приводить три варианта, а ограничусь только двумя. За описанием процесса я тоже отправлю к предыдущей задаче. Разница минимальна. Стоит только отметить, что структура Node диктует нам “обратный” порядок присоединения новых элементов в стек. Код написан так, будто мы добавляем элемент в начало списка и удаляем так же элемент из начала списка.
Чтобы понять разницу между стеком и очередью и почему так происходит, можно попробовать представить себе книги. Когда мы говорим об очереди, книги стоят на полке и мы всегда добавляем новые с правой стороны, а забираем с левой. В случае стека книги лежат стопкой и мы не можем взять книгу, которую положили первой – для этого нам надо снять все книги, которые мы положили раньше в обратном порядке. Поэтому с точки зрения банальной эрудиции самый последний добавленный элемент всегда будет самым первым. По сути же мы можем назвать нашу переменную previous вместо next и тогда все встанет на свои места. Мы начнем забирать элементы “с конца”.
Так же стоит обратить внимание, что в случае стека, мы обходимся только одной перменной, указываюшей на текущий элемент.

# решение, базирующееся на встроенных списках

class Stack:
    def __init__(self) -> None:
        self.stack = []

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

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

    def is_empty(self):
        return self.stack == []

# классическое решение без испольщовнаия встроенных списков.

class Node:
    def __init__(self, item) -> None:
        self.item = item
        self.next = None


class Stack:
    def __init__(self) -> None:
        self.head = None

    def push(self, item):
        if self.is_empty():
            self.head = Node(item)
        else:
            new_node = Node(item)
            new_node.next = self.head
            self.head = new_node

    def pop(self):
        if self.is_empty():
            return None
        item = self.head.item
        self.head = self.head.next
        return item

    def is_empty(self):
        return self.head is None