stack.md

Стек

| Главная | Структуры данных |

Стек (англ. stack) — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять тарелку, которая лежит на самом верху.

Реализация

• На основе списка (динамический контейнер)

Время (push)	Время (pop)	Время (is_empty)
O(n)	O(n)	O(n)

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

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

    def pop(self):
        if self.is_empty():
            raise ValueError()
        return self.store.pop()
    
    def is_empty(self):
        return self.store == []

    
n = 5
stack = Stack()
print(stack.is_empty())

for num in range(n):
    stack.push(num)
print(stack.is_empty())

for _ in range(n):
    print(stack.pop())
print(stack.is_empty())