Queue in Python

Queue

Queue is a linear data structure that implements the first-in-first-out (FIFO) principle, meaning that new elements can be added to the back of the queue, while removing an element is only possible from its head. Queue is really just like any real-life line in a supermarket: customers who come first are attended first, while the others are waiting for their turn.

Typically queue supports the following two basic operations:

• enqueue, that adds a new element to the back of the queue
• dequeue, that removes the first element of the queue.

Sometimes, operations front and rear are also supported. They return the first and the last element of the queue respectively without removing them.

In practice, queues are especially useful in threaded programming when information must be exchanged between multiple threads. Queues are at the heart of job schedulers, helping to schedule delayed tasks efficiently while preserving the order in which they must be performed.

In this topic, you will get familiar with a data structure called queue and how to implement it in Python.

Deque

Before we learn how to implement queue in Python, we should get familiar with one more data structure that is closely related, namely deque. Deque stands for 'double-ended queue' and allows for the elements to be added and removed from either side.

In Python, you can find deque implementation in the collections module. The essential methods are append(element) and appendleft(element), which add a new element to the right or left side of the deque respectively, as well as pop() and popleft(), which remove the first element from the corresponding side of the deque.

Let's take a look at the example:

from collections import deque

my_deque = deque()

my_deque.append('Middle')
my_deque.append('Right')

my_deque.appendleft('Left')

print(my_deque)

# deque(['Left', 'Middle', 'Right'])

print(my_deque.pop())

# Right

print(my_deque)

# deque(['Left', 'Middle'])

print(my_deque.popleft())

# Left

print(my_deque)

# deque(['Middle'])

Deque is implemented as a doubly linked list, meaning that its elements aren't stored next to each other in memory like the elements of the conventional list. By contrast, only smaller chunks of elements are stored together, and each such chunk stores the references to the previous chunk and to the next one. This architecture enables quicker append and pop operations from both ends of the deque.

Using collections.deque() as a queue

Of course, deque can be used as a simple queue. You just need to ignore the fact that you can add elements to the head and remove them from the back.

Here is an example:

my_queue = deque()

my_queue.appendleft('First')
my_queue.appendleft('In')
my_queue.appendleft('First')
my_queue.appendleft('Out')

print(my_queue)

# Deque(['Out', 'First', 'In', 'First'])

print(my_queue.pop())

# First

print(my_queue.pop())

# In

print(my_queue.pop())

# First

print(my_queue.pop())

# Out

So, as you can see, we get the elements in the same order as we put them in the queue. Note that if you call pop() one more time, you will get an exception because there are no more elements in the queue to be popped:

my_queue.pop()

# IndexError: pop from an empty deque

To avoid this, you can always check if the queue is non-empty before trying to get the next element from it. This can be done with the help of the len() method:

len(my_queue)

# 0

my_queue.append('a')
len(my_queue)

# 1

Conclusions

• Queue is a first-in-first-out data structure.
• Queue is at the heart of job scheduling in parallel computing.
• Deque stands for a double-ended queue. You can add and retrieve elements to/from both sides of the deque.
• In Python, deque is implemented in the collections module.
• You can use deque as a queue.