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.
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.
The first line of the input contains a single integer
n(1 ≤ n ≤ 100 000).
nlines contain the operations - either
addoperation is followed by a name, where you should add the customer to the waiting line.
popoperation only contains the operation name and nothing else.
It’s guaranteed that there’s always someone in the line before a
popoperation, so the operations are valid.
The names are guaranteed to not exceed 20 symbols.
popoperation, the program should print the name of the customer at the front of the line.
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
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB