Deque or double-ended queue is an extension of the queue that allows insertion and deletion from both ends of the queue. In this article, we’re going to learn about queues, different types of queues, deque in-depth, and finally, how to check if a deque is empty. Let’s get started!
What is a queue?
A queue is a linear data structure that follows the FIFO rule. The FIFO rule is also known as the first in first out rule. In a queue, data enters from the front and exits from the back. It has a ton of applications in file IO, sockets, etc.
Related: Learn about the queue in Python in depth.
There are mainly 4 types of queues:
- simple queue
- circular queue
- priority queue (heapq)
- double ended queue
simple queue
A simple queue is a classic queue, which follows the FIFO rule. In this type of queue, we track the element at the front and the back of the queue. The simple queue has a lot of limitations, it being the most basic form of a queue.
One of the limitations is that if the queue is full and we delete an element from the queue then there will be some empty space available at the front of the queue but we won’t be able to insert new elements. This leads to a waste of memory. To avoid this problem we use a circular queue.
circular queue
In a circular queue, when the queue is full it starts appending elements at the front. A circular queue leads to no memory wastage as it utilizes all the space allocated for the queue. It only shows the queue is full when there is genuinely no space left in the queue, neither at the back nor at the front.
The insertion formula for the circular queue is (rear+1)%size where the rear is the index of the last element and size is the size of the queue.
priority queue
The priority queue is a queue in which the elements are stored in the queue as per their priority. In the priority queue, the element with the highest priority will be popped first. It can be implemented using a heap. Heap is a complete binary tree in which the leaf nodes have low priority whereas the root node has the highest priority. There are two types of – min heap and max heap.
double-ended queue
In a simple queue, we can append and pop only on one end. This restriction is what makes a queue a queue. But sometimes we need to append or pop from the same ends or even both ends. In those cases, a double-ended queue also known as deque can be used. Deque is a linear data structure that allows append and pop from both ends in O(1) time.
Related: Learn double-ended queues in depth.
Why do we need deque?
Deque allows insertion and deletion from both ends. It has easy implementation but leads to a pool of possibilities. It can be used as a queue or stack at the same time. The ability to perform deletion from both ends in O(1) time makes it easier and faster to perform a palindrome check. It also has applications in memory management and some graph-based problems. Deque opens the gate for a lot of applications.
How to implement a deque?
As we know, Python is enriched with modules and libraries. Python has a module named collections which provides us with the deque data structure. Using the deque from collections we can implement deque easily.
The deque class takes a list as the parameter and converts the given list into a deque.
Python Implementation of Deque
from collections import deque #importing deque
dq = deque([1,2,3,4,5]) #using deque to create a deque of a list
print(dq)
Outputdeque([1, 2, 3, 4, 5])
Functions for deque
Append function
The append function appends the given element at the end of the deque.
Syntax:- deque.append(6)
Output:- deque([1,2,3,4,5,6])
Appendleft function
The append function appends the given element at the start of the deque.
Syntax:- deque.appendleft(0)
Output:- deque([0,1,2,3,4,5,6])
Pop function
The pop function removes the last element of the deque.
Syntax:- deque.pop()
Output:- deque([1,2,3,4,5])
Popleft function
The pop function removes the first element of the deque.
Syntax:- deque.popleft()
Output:- deque([2,3,4,5])
Can a deque be empty?
It is possible for a deque to be empty. A deque is said to be empty if there is no element present in the deque.
There are two ways in which a deque can be empty:
- We pass an empty list as an argument of the deque.
- We pop all the elements of the deque using the pop or popleft functions of the deque.
Creating an empty deque in Python
from collections import deque #importing deque
dq = deque([]) #using deque to create a deque of a list
print(dq)
OUTPUT:- deque([])
In the above code, we just passed an empty list as the argument of the deque. This way we’ll have an empty deque.
How to check if a deque is empty?
We learned how to create an empty deque. But what if we have a deque and we have to check if it is empty or not? An empty deque refers to a deque with no elements in it. If a deque has no elements in it then as a consequence it will have a length of 0. So to check if a deque is empty, we’ll have to check its length. If the length of the deque is 0, it’s an empty deque.
Let’s see how we can do this in code.
Python code to check if a deque is empty
from collections import deque #importing deque
dq = deque([]) #using deque to create a deque of a list
#creating an if-else block to check the length of the deque and output the result
if len(dq)==0:
print("The deque is empty!")
else:
print(f"There is/are {len(dq)} elements in the deque.")
In the above code, first, we imported a deque from collections and then created a deque with an empty list as an argument. Then we wrote an if-else structure to check if the deque is empty. We set the condition of the if statement as len(dq)==0. The “len” function gives the length of the deque as output. So it basically means, if dq has a length of 0, output empty deque else output the no. of elements in the deque.
from collections import deque #importing deque
dq = deque([1,2,3]) #using deque to create a deque of a list
#creating an if-else block to check the length of the deque and output the result
if len(dq)==0:
print("The deque is empty!")
else:
print(f"There is/are {len(dq)} elements in the deque.")
This time we passed the list [1,2,3] as the argument. This list has 3 elements in it. So len(dq)==0 will be false and henceforth the interpreter will execute the else block. So the output will be “There is/are 3 elements in the deque.”
Why do we need to check if a deque is empty?
Deque is commonly used in graph questions or dfs/bfs. While working with them, we constantly need to check the status of the deque. So it is necessary to learn to check if a deque is empty.
Conclusion
Deque is an important data structure that has a lot of applications. It is very simple to implement and has great functionalities. It is faster and way more flexible than a simple queue or a stack. Make sure you understand it completely and learn how to apply it. The deque has its own drawbacks but also has a ton of advantages. Keep exploring and be open to learning new things. Make sure you also check how to use other types of queues like circular queues and priority queues.