Queues

What are Queues?

Queues are a simple but useful Data Structure. They're used in Programming Competitions and Job Interviews, so it is a good idea to learn about them.

In Programming, Queues are similar to line-ups of people in real life. For example, let's say that some people are lining up to go on a rollar coaster:

These people don't want to get out of line because they've been lining up for a long time. So, you can only add to then end of the Queue/line and the people get out of the line at the front. We call this a "First In Last Out" (FILO) rule.

Queue Implementation

In Python, we actually have a built-in module called queue that comes with a Queue class. We can use this class to represent a Queue. As an example, type the following code into your file:

from queue import Queue

my_queue = Queue()
print(my_queue.empty())
    

In this example, we create an empty Queue using the Queue class. We first import it from the queue module and then we assign an empty Queue to the variable q. After we do this, we call the empty method on q and we print out the result. The empty function returns a Boolean which indicates whether or not the Queue is empty. Since we haven't actually added anything to the Queue yet, it is still empty so our program will print out True.

Then, type the following code into your program:

q.put(5)
q.put("hi")
q.put("more stuff")
q.put(True)
print(q.queue)
print(type(q.queue))
    

After running the code, you'll get
deque([5, 'hi', 'more stuff', True])
<class 'collections.deque'>
printed out into the terinal.

Notice how the type of q.queue is of collections.deque. This is a seperate class that implements a Deque, which we'll learn about in the next tutorial.

Enqueuing

With Queues, we can add items, and we can remove items. As we already know, by adding to a Queue, it goes to the end. We call this enqueuing to the Queue.

With the Queue class, we use the put method on the queue to do this.

q.put("item goes to the end")
    

Dequeuing

With Queues, we can also remove items. As we already know, by removing from a Queue, it takes the item at the start of the Queue. We call this dequeuing from the Queue.

With the Queue class, we use the get method on the queue to do this.

q.put("item goes to the end")
print(q.get()) # prints out "item goes to the end"
print(q.empty()) # True
    

Queues in Competition

We've already gone over how Queues work and how to implement one. So, now, let's go over using Queues in Programming Competitions and Job Interview problems.