Алгоритмы и структуры данных

Очередь

Очередь (Queue) является одной из основных структур данных во многих алгоритмах. Она очень похожа на реальную очередь. Первый элемент, добавленный в очередь, будет обслужен и удалён первым.
Представьте себе очередь муравьёв, стоящих за кофе. Первый муравей в очереди получит кофе и выйдет из неё, затем следующий получит кофе и тоже покинет очередь, и так будет продолжаться до тех пор, пока очередь не опустеет и не останется ни одного муравья в ожидании кофе.
notion image
Объявление и использование очереди в большинстве языков программирования упрощено – многие универсальные языки (например, 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 программа должна вывести имя клиента, который находится в начале очереди.

Примеры

Input
Output
9 add Steven add Sam pop add Sergio add Don pop add John pop pop
Steven Sam Sergio Don
4 add John Ford add Tom Ford pop pop
John Ford Tom Ford
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue