# 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

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.