3 Ways to Implement Queue in Python

Summary: In this tutorial, we will learn three different ways to implement queue data structure in Python.

A queue is a collection of elements that maintains a sequence in which the element can be inserted from one end and removed from the other end.

When an element enters a queue it makes its way to the other end to get popped.

In short, the queue is FIFO (First In First Out) data structure i.e. the first element added to the queue will be the first one to be removed and the following elements in the same order they were inserted.

In Python, we can implement the queue data structure in three following ways:

Method 1: Implement Queue using List

List in Python is mutable i.e. it allows addition and removal of items. We can use this feature as an advantage to use it as a queue.

To implement queue using list, we add items to the list using list.append() and remove items using list.pop(0).

>>> queue = []
>>>
>>> #adding items to queue
>>> queue.append(1)
>>> queue.append(2)
>>> queue.append(3)
>>> 
>>> #popping queue items
>>> queue.pop(0)
1
>>> queue.pop(0)
2
>>> queue.pop(0)
3

The queue.append() adds items to the last while queue.pop(0) removes the first item from the queue. This is to ensure that the queue only allows FIFO operations.

Method 2: Implement Queue using queue.Queue

If we don’t want to use the list as a queue, we can use the Queue class of the queue module.

We initialize the object of Queue by passing the value for the maxsize argument. The maxsize is an integer that sets the limit on the number of items that can be placed in the queue.

On this object, we add and remove items using the put() and get() method respectively.

>>> from queue import Queue
>>>
>>> #initalize the Oueue object
>>> q = Queue(maxsize=3)
>>>
>>> #adding items
>>> q.put(1)
>>> q.put(2)
>>> q.put(3)
>>>
>>> #popping items
>>> q.get()
1
>>> q.get()
2
>>> q.get()
3

If we do not provide the value for maxsize or it is less than or equal to zero, the queue size becomes infinite.

Method 3: Implement Queue using collections.deque

Alternatively, we can use the deque class of the collections module to create a queue in Python.

It is similar to the Queue but allows addition and removal operations from both sides.

To use it as a queue, we will only use its append() method to add the items to the right (i.e last) and popleft() method to remove items from the left.

>>> from collections import deque
>>>
>>> #initalize the deque object
>>> q = deque(maxlen=3)
>>>
>>> #adding items to the end
>>> q.append(4)
>>> q.append(1)
>>> q.append(9)
>>>
>>> #popping items from the start
>>> q.popleft()
4
>>> q.popleft()
1
>>> q.popleft()
9

The maxlen argument limits the size of the deque to the specified number. If we do not specify its value or is None, the deque may grow to any arbitrary length.

In summary, we can implement the queue data structure in Python by using the built-in list or by using the Queue and deque classes of the external modules.