Проблема: вызов `stack.pop(0)` на Python-списке удаляет первый элемент и сдвигает все последующие элементы влево — это требует копирования/перемещения примерно $n-1$ элементов для списка длины $n$. Поэтому одна такая операция имеет сложность $\mathcal{O}(n)$.
Исправление (если нужен стек — LIFO): использовать конец списка как вершину стека:
```
def pop(stack):
return stack.pop() # удаление с конца — амортизированно O(1)
# добавление: stack.append(x)
```
Сложность: каждая операция `append`/`pop()` амортизированно $\mathcal{O}(1)$. Для $m$ операций общая сложность $\mathcal{O}(m)$.
Если нужен очередь (FIFO): используйте collections.deque и `popleft()`:
```
from collections import deque
q = deque()
q.append(x) # добавление справа — O(1)
q.popleft() # удаление слева — O(1)
```
Сложность: `popleft()` и `append()` — $\mathcal{O}(1)$ каждая; для $m$ операций общая сложность $\mathcal{O}(m)$.
Сравнение: последовательность из $m$ вызовов `pop(0)` на списке может потребовать суммарно $\mathcal{O}(m^2)$ времени, тогда как эквивалентное число операций с `append`/`pop()` или с `deque` — $\mathcal{O}(m)$.