Понятие стека, принципы работы, примеры использование, временные сложности операций

Стек - это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной. LIFO - Last In First Out (Последний вошел, первый вышел).

Операции над текстовыми строками часто выполняются с использованием стеков.

Пример реализации стека:

stack = []


def push(s, val):
    s.append(val)


def pop(s):
    return s[len(s) - 1]


push(stack, 1)
push(stack, 2)
push(stack, 3)
push(stack, 4)
pop(stack) //Вернет 4
pop(stack) //Вернет 3