Что такое стек и зачем он нужен?

Стек (stack) - это структура данных, которая поддерживает две основные операции: добавление элемента в конец стека и удаление элемента с конца стека. Стек можно представить как стопку тарелок, где можно добавлять только сверху или удалять только с вершины.

Рассмотрим пример кода на языке Python, который реализует стек:

class Stack:
    def __init__(self):
        self.stack = []
    def push(self, item):
        self.stack.append(item)
    def pop(self):
        if self.is_empty():
            return None
        return self.stack.pop()
    def is_empty(self):
        return len(self.stack) == 0
    def size(self):
        return len(self.stack)

В этом примере создается класс `Stack`, который имеет следующие методы:

• `__init__(self)`: конструктор, который создает пустой стек.
• `push(self, item)`: метод, который добавляет элемент на вершину стека.
• `pop(self)`: метод, который удаляет последний элемент с вершины стека и возвращает его.
• `is_empty(self)`: метод, который проверяет, пуст ли стек.
• `size(self)`: метод, который возвращает количество элементов в стеке.

Например, мы можем создать стек с помощью следующего кода:

my_stack = Stack()

Затем мы можем добавить несколько элементов с помощью метода `push()`:

my_stack.push(10)
my_stack.push(20)
my_stack.push(30)

Теперь мы можем удалить элементы с помощью метода `pop()`:

print(my_stack.pop()) # 30
print(my_stack.pop()) # 20
print(my_stack.pop()) # 10

Метод `pop()` удаляет последний элемент с вершины стека и возвращает его. Если стек пуст, метод `pop()` возвращает `None`.

Таким образом, стек - это структура данных, которая используется для хранения элементов, где последний добавленный элемент хранится на вершине стека, и последний добавленный элемент удаляется с вершины стека. Эта структура данных широко используется в программировании, например, для реализации системы отката (undo/redo), выполнения рекурсивных функций, обработки выражений и т.д.