Стек

Стек — одна из самых распространённых структур данных, используемых в алгоритмах. В стеке элемент, добавленный последним, будет удалён первым. Это похоже на стопку тарелок: можно убрать только ту тарелку, которая лежит сверху, пока не будут убраны все тарелки, находящиеся над ней.

Стек можно применять во множестве реальных ситуаций. Например, когда вы просматриваете сайты в веб-браузере, у вас есть кнопка «Назад», позволяющая перейти к предыдущей странице. История страниц может храниться в виде стека: при нажатии «Назад» вы возвращаетесь к верхнему элементу стека. Если нажать «Назад» снова, верхняя страница удаляется из стека, и вы переходите к странице, которая теперь стала верхней.

1. С использованием list — верхним элементом стека будет последний элемент списка. Добавление производится с помощью append, удаление — через pop, а получить элемент можно по индексу [-1].

2. С использованием deque из модуля collections — он поддерживает добавление и удаление элементов как с начала, так и с конца.

3. LifoQueue из модуля queue — очередь с принципом «последний пришёл — первый ушёл» (Last-in-first-out), что по сути и есть определение стека.

from queue import LifoQueue
stack = LifoQueue()

# push
stack.put(1)
stack.put(2)
stack.put(3)

# pop
print(stack.get())      # prints 3
print(stack.get())      # prints 2

# peek
print(stack.queue[-1])  # prints 1
print(stack.empty())    # check if empty -> prints False

# Using a simple list
stack = []

# push
stack.append(1)
stack.append(2)
stack.append(3)

# pop
print(stack.pop())      # prints 3
print(stack.pop())      # prints 2

# peek
print(stack[-1])        # prints 1
print(len(stack) == 0)  # check if empty -> prints False

Задание: проверить корректность скобочной последовательности

Входные данные

Выходные данные

Примеры