Очередь

Очередь (Queue) является одной из основных структур данных во многих алгоритмах. Она очень похожа на реальную очередь. Первый элемент, добавленный в очередь, будет обслужен и удалён первым.

Представьте себе очередь муравьёв, стоящих за кофе. Первый муравей в очереди получит кофе и выйдет из неё, затем следующий получит кофе и тоже покинет очередь, и так будет продолжаться до тех пор, пока очередь не опустеет и не останется ни одного муравья в ожидании кофе.

Объявление и использование очереди в большинстве языков программирования упрощено – многие универсальные языки (например, Python, C++, Java и т.д.) уже реализовали структуру данных «очередь» для удобства. Мы можем реализовать очередь и самостоятельно, используя связный список. Может, вы придумаете, как это сделать? 🤔

from queue import Queue

q = Queue()    # Создаем новую очередь
q.put(1)       # Добавляем 1 в начало очереди
q.put(2)       # Затем добавляем 2
q.put(3)       # Добавляем 3 после 2

# Извлекаем элементы из очереди с помощью get()
print(q.get()) # выводит 1
print(q.get()) # выводит 2
print(q.get()) # выводит 3

Задача: Симуляция очереди

Вам нужно реализовать систему, которая будет учитывать покупателей в магазине. Она должна уметь добавлять клиента в очередь и убирать первого клиента из очереди, когда он обслужен. Каждый раз, когда вы убираете клиента, необходимо выводить его имя.

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

Первая строка входных данных содержит одно целое число n (1 ≤ n ≤ 100 000).

Следующие n строк содержат операции — либо add, либо pop:

• Операция add сопровождается именем, и вам нужно добавить клиента в очередь.

• Операция pop указывается без имени.

Гарантируется, что перед каждой операцией pop в очереди уже есть хотя бы один человек, поэтому операции будут корректными.

Имена гарантированно не превышают 20 символов.

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

Для каждой операции pop программа должна вывести имя клиента, который находится в начале очереди.

Примеры