Algorithms and Data Structures

Queue

The Queue is one of the core data structures in many algorithms. It’s very similar to a real-life queue. The first element added to a queue will be the first to be “served” and removed from it.
Imagine a line of ants standing in a queue waiting for a coffee. The first ant in the queue will get coffee and leave the queue, then the next ant will get a coffee and leave the queue, and this process will continue until the queue is empty and there are no ants waiting for a coffee.
notion image
Declaring and using a queue is made straightforward in most languages - as most general-purpose languages (like Python, C++, Java, etc.) have implemented the queue data structure for easier use. We can still implement the queue ourselves using a linked list. Can you think of how to do that 🤔?
from queue import Queue

q = Queue()    # Create a new queue
q.put(1)       # Add 1 to the front of the queue
q.put(2)       # Add 2 next
q.put(3)       # Add 3 after 2

# Remove elements from the queue using get()
print(q.get()) # prints 1
print(q.get()) # prints 2
print(q.get()) # prints 3

Challenge: Queue Simulation

You are implementing a system that should keep track of the customers in the store. There are two things that your system should be capable of - it should be able to add a customer to the waiting line, and it should be able to remove the first customer from the waiting line when they are satisfied. Each time you remove a customer, you should print their name.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000).
The next n lines contain the operations - either add or pop:
  • add operation is followed by a name, where you should add the customer to the waiting line.
  • pop operation only contains the operation name and nothing else.
It’s guaranteed that there’s always someone in the line before a pop operation, so the operations are valid.
The names are guaranteed to not exceed 20 symbols.

Output

For each pop operation, the program should print the name of the customer at the front of the line.

Examples

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