How to Queue Implementation in Python

1. Queue Implementation in Python
2. Add an Element to the Queue: The Enqueue Operation
3. Remove an Element From the Queue: The Dequeue Operation
4. Other Operations on Queues in Python
5. Queue Implementation Using Lists in Python
6. Queue Implementation Using Linked Lists in Python
7. Queue Implementation Using the Collections Module in Python
8. Most Efficient Queue Implementation in Python

We use queues in Python to perform first-in, first-out (FIFO) operations.

This article will discuss three different ways for queue implementation in Python.

Queue Implementation in Python

In a queue, we can perform different operations. Let us first discuss the general concept behind all the operations, and after that, we will implement the queue operations using various constructs.

The first element in the queue is called the front element. Similarly, the last element of the queue is called the rear element.

For instance, consider the following sequence of numbers as a queue. 1 is the front element, while 6 is the rear element.

1,2,3,4,5,6

Add an Element to the Queue: The Enqueue Operation

In the enqueue operation, we add the element into the queue just like a person joins a queue at a ticket counter. The newly added element always becomes the rear element.

For instance, if we add the number 7 to the queue given above, the queue will look like the below.

1,2,3,4,5,6,7

It is essential to note that we can add elements only at the rear of a queue.

Remove an Element From the Queue: The Dequeue Operation

In the dequeue operation, we remove the front element of the queue just like a person gets out of the queue after receiving their ticket from the ticket counter.

After a dequeue operation, the front element is removed from the queue, and the element behind the front element becomes the new front element. For instance, after the dequeue operation, the queue used in the previous example will look like this.

2,3,4,5,6,7

You can only remove the front element in a dequeue operation. Queues always follow the first-in, first-out order. Hence, the element added to the queue first also gets removed first.

Other Operations on Queues in Python

If a queue has no element, it is said to be empty. We can use different approaches to determine if a queue is empty in different implementations.

Sometimes, we might also need to find the length of the queue. We will also discuss the implementation of this operation.

Queue Implementation Using Lists in Python

We can implement queues in Python using lists most simply. To create a queue using lists,

1. We define a class Queue with three attributes.
2. We define an empty list data that will store the elements of the list.
3. We initialize two variables, front and rear.
4. We initialize the variables to -1 to show that the queue is empty.

Code:

class Queue:
    def __init__(self):
        self.data = list()
        self.front = -1
        self.rear = -1

An empty list is created and assigned to the attribute data when creating a Queue object. The list then stores the elements of the queue.

After creating the empty queue, we will implement different operations on the queue.

Check if Queue Is Empty in Python

To check if the queue is empty, we can check if the attributes, front and rear, are initialized to -1. For this, we will define a method isEmpty().

The isEmpty() method, when invoked on a queue, will check whether the front and rear attributes have the value -1. If yes, it will return True, denoting that the queue is empty; otherwise, it will return False.

Code:

def isEmpty(self):
    if self.rear == -1 and self.front == -1:
        return True
    else:
        return False

Enqueue Operation Using Lists in Python

To insert an element into the queue, we will check first if the queue is empty. We can use the isEmpty() method defined above.

1. If the queue is empty, we will append an element to the list contained in the data attribute using the append() method. When invoked on a list, the append() method takes an element as its input argument and adds it to the list.
2. Now that there is only one element in the list, we will update the values of the attributes front and rear to 0. Both the front and rear elements are present at index 0 in the list data.
3. If the list is not empty, we will first add the element to the list using the append() method.
4. After that, we will increment the value in the rear attribute showing that an extra element has been added to the queue.

In the enqueue operation, the value of the front attribute will not be changed as we are not removing any element from the queue.

The entire operation can be implemented in Python as follows.

Code:

def enQueue(self, element):
    if self.isEmpty():
        self.data.append(element)
        self.front = 0
        self.rear = 0
    else:
        self.data.append(element)
        self.rear += 1

Dequeue Operation Using Lists in Python

We will first check if the queue is empty for the dequeue operation. If yes, we cannot operate; otherwise, we will perform the following.

1. We will check if there is only one element in the queue. We can check if the front and rear attributes have the same value, and none of them are -1.
2. If the queue has only one element, we will remove the element at the front index of the queue using the pop() method and return it to the user. Then, we will update the attributes front and rear to -1, showing that the queue has become empty.
3. If none of the above conditions are True, the queue has two or more elements. We will store the element at the front index in a temporary variable in such a case.
4. After that, we will increment the value in the attribute front, denoting that the next element in the list has become the front element.
5. Finally, we will return the value stored in the temporary variable.

Code:

def deQueue(self):
    if self.isEmpty():
        print("Queue is Empty. Cannot remove element")
    elif self.front == self.rear and self.front != -1:
        element = self.data[self.front]
        self.front = -1
        self.rear = -1
        return element
    else:
        element = self.data[self.front]
        self.front = self.front + 1
        return element

Find the Length of the Queue in Python

To find the length of a queue in Python, we can perform the following steps.

1. If the queue is empty, the length of the queue will be 0. Therefore, we will first check if the queue is empty using the isEmpty() method.
2. If the isEmpty() method returns True, we will return 0 as the queue length.
3. Otherwise, the length of the list will be calculated as rear-front+1.

As shown below, we have implemented this in the length() method.

Code:

def length(self):
    if self.isEmpty():
        return 0
    return self.rear - self.front + 1

We have implemented all the methods. Let us now execute all the operations once.

Complete code:

class Queue:
    def __init__(self):
        self.data = list()
        self.front = -1
        self.rear = -1

    def isEmpty(self):
        if self.rear == -1 and self.front == -1:
            return True
        else:
            return False

    def enQueue(self, element):
        if self.isEmpty():
            self.data.append(element)
            self.front = 0
            self.rear = 0
        else:
            self.data.append(element)
            self.rear += 1

    def deQueue(self):
        if self.isEmpty():
            print("Queue is Empty. Cannot remove element")
        elif self.front == self.rear and self.front != -1:
            element = self.data[self.front]
            self.front = -1
            self.rear = -1
            return element
        else:
            element = self.data[self.front]
            self.front = self.front + 1
            return element

    def length(self):
        return self.rear - self.front + 1


myQueue = Queue()
print("Enqueuing element 10")
myQueue.enQueue(10)
print("Queue Length is:", myQueue.length())
print("Enqueuing element 20")
myQueue.enQueue(20)
x = myQueue.deQueue()
print("dequeued element:", x)
print("Queue Length is:", myQueue.length())
y = myQueue.deQueue()
print("dequeued element:", y)
z = myQueue.deQueue()

Output:

Enqueuing element 10
Queue Length is: 1
Enqueuing element 20
dequeued element: 10
Queue Length is: 1
dequeued element: 20
Queue is Empty. Cannot remove element

In the example, we executed a few methods after the queue implementation in Python using lists. You can copy the code, paste it into your IDE, and experiment with the code to better understand the code’s working.

Queue Implementation Using Linked Lists in Python

We have already discussed different operations on linked lists in Python. We can also use linked list operations for queue implementation in python.

We will first define a node with two attributes, namely data and next.

Code:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

Where:

• The data attribute will be used to store elements of the queue.
• The next attribute will be used to point to the element ahead of the current element in the queue.

After defining the Node, we will define the Queue class, where we will have the front and rear attributes.

The front attribute will point to the node containing the front element in the queue’s linked list. Similarly, the rear attribute will point to the node containing the rear element in the linked list containing the queue.

The front and rear attributes will be initialized to None as the queue will be empty.

Code:

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

When the Queue class is initialized, it only contains the front and rear attributes, with the value None.

Check if Queue Is Empty in Python

To check if the queue is empty, we can check if the front and the rear attributes are None. If yes, we can say that the queue is empty.

We will define the isEmpty() method for this operation. When invoked on a queue, the isEmpty() method will return True if the queue is empty; otherwise, it will return False.

Code:

def isEmpty(self):
    if self.front is None:
        return True
    return False

Enqueue Operation Using Linked Lists in Python

To perform the enqueue operation, we will first check if the queue is empty. If yes, we will assign the node with the new element to both the front and rear attributes.

Otherwise, we will add the new element to the next node of the rear node. After that, we will make the new node the rear node.

In this way, the new element will be added to the queue.

Code:

def enQueue(self, data):
    newNode = Node(data)
    if self.isEmpty():
        self.front = newNode
        self.rear = newNode
    else:
        self.rear.next = newNode

Dequeue Operation Using Linked Lists in Python

We will first check if the queue is empty for the dequeue operation. If yes, we will say that underflow has occurred, and we cannot remove any element.

Otherwise, we will first store the data in a temporary variable in the front node.

After that, we will make the next node of the front node as the new front node. Then, we will delete the front node stored in the temporary variable using the del statement.

In this way, the previous front node will be deleted from the queue. Finally, we will return the value stored in the temporary node.

Code:

def deQueue(self):
    if self.isEmpty():
        print("Queue is empty. Cannot remove element.")
    else:
        element = self.front
        nextFront = self.front.next
        self.front = nextFront
        value = element.data
        del element
        return value

Find the Length of the Queue in Python

1. To find the length of the queue, we will first initialize a variable count to 0.
2. After that, we will start traversing the queue from the front node using a while loop. We will increment the count by 1 when moving to the next node.
3. Once we reach the end of the queue, i.e., None, we will exit from the while loop.
4. Finally, we will return the value of count, showing the length of the queue.

Code:

def length(self):
    count = 0
    if self.front is None:
        return count
    else:
        temp = self.front
        while temp is not None:
            count += 1
            temp = temp.next
        return count

We have implemented all the queue methods using linked lists. Let us now execute the operations to understand the working in a better manner.

Complete code:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def isEmpty(self):
        if self.front is None:
            return True
        return False

    def enQueue(self, data):
        newNode = Node(data)
        if self.isEmpty():
            self.front = newNode
            self.rear = newNode
        else:
            self.rear.next = newNode

    def deQueue(self):
        if self.isEmpty():
            print("Queue is empty. Cannot remove element.")
        else:
            element = self.front
            nextFront = self.front.next
            self.front = nextFront
            value = element.data
            del element
            return value

    def length(self):
        count = 0
        if self.front is None:
            return count
        else:
            temp = self.front
            while temp is not None:
                count += 1
                temp = temp.next
            return count


myQueue = Queue()
print("Enqueuing element 10")
myQueue.enQueue(10)
print("Queue Length is:", myQueue.length())
print("Enqueuing element 20")
myQueue.enQueue(20)
x = myQueue.deQueue()
print("dequeued element:", x)
print("Queue Length is:", myQueue.length())
y = myQueue.deQueue()
print("dequeued element:", y)
z = myQueue.deQueue()

Output:

Enqueuing element 10
Queue Length is: 1
Enqueuing element 20
dequeued element: 10
Queue Length is: 1
dequeued element: 20
Queue is empty. Cannot remove element.

Queue Implementation Using the Collections Module in Python

We can also use the collections module for queue implementation in Python.

The Collections module provides the deque (doubly ended queue) class to implement queues and stacks in Python. You can import the deque class in your program using the import statement below.

from collections import deque

We will create a class, Queue, to implement the queue. As shown below, we will create a deque object within the class.

Code:

class Queue:
    def __init__(self):
        self.data = deque()

When the Queue class is instantiated, an empty deque object is created to store the elements of the queue.

Check the Length of the Queue in Python

To check the length of the queue, we will define a length() method. Inside the length() method, we will calculate the length of the deque object using the len() function.

The len() function will take the deque object as input and return the deque length. We will return the value of the len() function as the length of the queue, as shown below.

Code:

def length(self):
    return len(self.data)

Check if the Queue Is Empty in Python

If the length of the queue is 0, we will say that the queue is empty. We can define the isEmpty() method as shown below.

Code:

def isEmpty(self):
    if self.length() == 0:
        return True
    return False

Enqueue an Element in Python

We will define the enQueue() method to enqueue an element. The enQueue() method will take the new element as its input argument.

Inside the enQueue() method, we will use the append() method to add the element to the deque object. The append() method, when invoked on the deque object, takes the new element as its input argument and adds it to the deque object.

Code:

def enQueue(self, x):
    self.data.append(x)

Dequeue Operation in Python

We will define the deQueue() method to remove an element from the queue. Inside the deQueue() method, we will invoke the popleft() method on the deque object of the queue.

The popleft() method, when invoked on a deque object, removes the front element of the deque. It also returns the element that is removed from the queue.

We will also return the value returned by the popleft() method from the deQueue() method using a return statement.

Code:

def deQueue(self):
    if self.isEmpty():
        print("Queue is empty. Cannot remove element.")
    else:
        return self.data.popleft()

Now we have implemented all the methods for queue implementation in Python using the collections module. Let us observe the entire execution.

Complete code:

from collections import deque


class Queue:
    def __init__(self):
        self.data = deque()

    def length(self):
        return len(self.data)

    def isEmpty(self):
        if self.length() == 0:
            return True
        return False

    def enQueue(self, x):
        self.data.append(x)

    def deQueue(self):
        if self.isEmpty():
            print("Queue is empty. Cannot remove element.")
        else:
            return self.data.popleft()


myQueue = Queue()
print("Enqueuing element 10")
myQueue.enQueue(10)
print("Queue Length is:", myQueue.length())
print("Enqueuing element 20")
myQueue.enQueue(20)
x = myQueue.deQueue()
print("dequeued element:", x)
print("Queue Length is:", myQueue.length())
y = myQueue.deQueue()
print("dequeued element:", y)
z = myQueue.deQueue()

Output:

Enqueuing element 10
Queue Length is: 1
Enqueuing element 20
dequeued element: 10
Queue Length is: 1
dequeued element: 20
Queue is empty. Cannot remove element.

Most Efficient Queue Implementation in Python

This article has discussed three approaches for queue implementation in Python.

Among all the approaches discussed here, using lists to store the queue elements is the worst. In this approach, the elements are never deleted from the list.

Therefore, we suggest you never use it in your programs. Use it only if you are a beginner in Python and don’t know anything about linked lists.

If you are not allowed to use external modules, you can use the Python queue implementation that uses linked lists as it is time and memory efficient. However, it is slower than the approach using deque.

You should use the deque module approach for Python’s most efficient queue implementation. It has the best efficiency in terms of time and memory because the source code for the module is written in C, and the implementation uses doubly-ended linked lists to implement the deque object.

We hope this article helped you understand queue implementation in Python. Stay tuned for more informative articles.