The Queue in Python

In this post, we learn how to implement a queue in Python using Python’s list data structure, the collections module, and a custom wrapper class

What is a Queue in Python?

A queue is a data structure that is based on the first-in, first-out principle when adding and removing items. Elements are added to the end of the queue in an operation referred to as “enqueue”. They are removed from the beginning of the queue using the “dequeue” operation. In Python, a queue is usually implemented using the in-built list, Queue from the queue module, or deque from the collections module.

A queue supports the following operations:

• Enqueue: Add an element to the end of the queue
• Dequeue: Remove an element from the beginning of the queue
• First: Get the first element in a queue without removing it
• Last: Get the last element in a queue without removing it

How to Create a Queue in Python?

The simplest way to implement a Python queue is through a list. You can dequeue items from a list using the pop method. For enqueue you can use the append method.

To add items to the end of the queue we append them to the list.

queue = []

#appending 2 elements to the empty queue
queue.append(1)
queue.append(2)
print(queue) #[1, 2]

Items can be dequeue with the pop method. But you have to be careful here. Pop by default removes the last element from the list. Since a queue follows the first-in, first-out principle, we need to remove the first element. Therefore, we have to pass 0 to the pop function telling Python to remove the element at the zeroth index.

queue = [1, 2, 3]
queue.pop(0) #0

#Printing the queue after removing the first element
print(queue) #[2, 3]

To obtain the first element and the last element in the queue, the most straightforward way is to use indices.

The first element in the queue has an index of 0. For the last item in the queue, we can use the -1 index. The minus sign indicates to Python to start counting items backward from the end of the queue.

queue = [1, 2, 3]

print(queue[0]) #1
print(queue[-1]) #3

However, this comes with the same problem we have with the Python implementation of the stack. We cannot rely on methods that we call on the data structure, and indexing does not account for empty lists. If there are no items in the list, we will run into a “list index out of range” error. But as a consumer of the list, we just want to interact with its interface and not deal with an internal error.
To resolve this problem, we can create a wrapper class that has the desired interface and handles errors for us.

class Queue:
    def __init__(self, elements = None):
      if(elements == None):
        self.elements = list()
      else:
        self.elements = elements
    
    def enqueue(self, item):
        self.elements.append(item)
    
    def dequeue(self):
      if(len(self.elements) > 0):
        return self.elements.pop(0)
      
    def get_first(self):
      if(len(self.elements) > 0):
        return self.elements[0]
      
    def get_last(self):
      if(len(self.elements) > 0):
        return self.elements[-1]
    
    def get_size(self):
        return len(self.elements)

    def is_empty(self):
        return len(self.elements) == 0
      
    def __str__(self):
        return str(self.elements)
      

In the constructor we check if the caller has passed a list of initial items. If not we just assign an emtpy list. We have implemented a toString method in the end of the class which simply prints out the stack when we pass the queue to the print function.

# creating an empty queue
queue = Queue()
print(queue) # []

# creating a queue with initial values
queue = Queue([1,2])
print(queue) #[1, 2]

We can enqueue and dequeue items without having to worry about index out of range errors and the queue being empty. The dequeue method simply does nothing when called on an empty queue.

queue = Queue()
queue.enqueue(2)
print(queue) #[2]

print(queue.dequeue()) #2
print(queue.dequeue()) #None
print(queue) #[]

Lastly, we check that we can retrieve the first and the last entries as well as the size of the queue and whether it is empty.

queue = Queue([1,2,3])

print(queue.getFirst()) #1
print(queue.getLast()) #3

print(queue.getSize()) #3
print(queue.isEmpty() #False

Python Queue using Deque

Building queue on the basis of Python’s list might lead to slow enqueue and dequeue operations once the list becomes sufficiently large. The reason is that lists are based on contiguous memory where items are stored adjacent to each other in the same memory block. This works well until the memory block is full. Further items are stored in a new block without an exact reference. So Python has no idea where to find them. It has to inefficiently search for them once you are calling the method.

The deque (not to be confused with dequeue) is a data structure that comes with Python’s collections package and is based on a doubly linked list. Items are each stored in a different memory block but each element also has an explicit reference to the location of the next item as well as the previous item. This makes finding items much faster.

The interface of deque is similar to that of the list. You can initialize a deque with or without values.

from collections import deque

# queue with initial values
queue = deque([1,2,3])
print(queue)

# queue without initial values
queue = deque()
print(queue)

The deque also supports an append function which you can use to enqueue items. Deque also supports a pop function. You have to be careful, though, since pop removes elements from the end of the queue. This is appropriate for a stack that operates based on the first-in, first-out principle. For a queue, you use the popleft method.

queue = deque([1,2,3])

#enqueue
queue.append(4)
print(queue) #deque([1, 2, 3, 4])

#dequeue
queue.popleft() #1

Python Queue Using the Queue Module?

Python also offers a “Queue” module with a queue implementation. The purpose of a queue from the “Queue” module is to handle multithreaded code without locking. When items are manipulated on several threads you run into the problem of race conditions. Unintended consequences are likely to ensue because individual threads don’t know whether an item has been manipulated by other threads. To handle this problem manually, you need intricate locking strategies that can lead to your code getting stuck in a deadlock. The queue abstracts away these problems for you.

The interface differs a bit from that of the deque. Instead of append and pop you use put and get. It is also good practice to specify a maximum size.

from queue import Queue

queue = Queue(maxsize = 3)
queue.put(1)

queue.get() # 1

In Summary: the queue from the module of the same name is useful when you want thread safety in a multithreaded environment. For programs that run on a single thread, the deque is your best bet.