What is a Queue Data Structure in Python? Queues are a fundamental data structure in Python that follows the First In First Out (FIFO) principle. Python provides several ways to implement and use queues, such as job scheduling, and event handling. In this article, we’ll explore the different types of queues, their characteristics, and how to implement them in Python.
We will also explain the operations that can perform on a queue. By the end of this article, you’ll have a better understanding of how queues work and how to use them in Python.
Table of contents
- 1. Queue Data Structure in Python
- 2. Different types of queues
- 3. Implementation of Queue in Python
- 4. Implementation of Double Ended Queue
- 5. Implementation of Circular Queue
- 6. Implementation of Priority Queue
- 7. Operations on Queue in Python
- 8. Use of Queue in Python
- 9. Summary and Conclusion
- Related Articles
1. Queue Data Structure in Python
A queue is a data structure in Python that allows the ordered processing of data. A queue is a collection of elements. The first element added to the queue is the first element to be removed from the queue, known as the First In First Out (FIFO) principle. We store the elements in such a way to ensure this behavior.
Programmers often use queues to manage various types of data, such as events, messages, or tasks. Typically, they implement them as a simple linear data structure, where they add elements to the back of the queue and remove them from the front of the queue.
1.1 Characteristics of a queue
Below are some characteristics of a queue in Python:
- Follows the First In First Out (FIFO) principle.
- Has a size, front and rear pointers, and can be empty or full.
- Size is determined by the number of elements it can hold.
- Adding an element to a full queue results in an overflow error.
- Removing an element from an empty queue results in an underflow error.
- Front and rear pointers keep track of the first and last elements in the queue.
2. Different types of queues
There are multiple types of queues in Python, each with unique characteristics and use cases. We will discuss Simple Queues, Double-ended Queues, Circular Queues, and Priority Queue.
2.1 Simple Queues
A Simple Queue, also known as a FIFO Queue, is a linear data structure that follows the FIFO principle. A simple queue inserts elements at the rear end and removes them from the front end of the queue.
Developers commonly use simple queues in scenarios where they need to maintain the order of elements, such as in job scheduling, message passing, or network processing.
Below is an example of a Simple Queue in Python:
# Creating a simple queue
queue = []
# Adding items to the queue
queue.append('Python')
queue.append('Java')
queue.append('C++')
print("Initial queue:", queue)
# Removing items from the queue
print("Removing items from the queue:")
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))
print("Queue after removal:", queue)
Yields the following output:
# Output:
Initial queue: ['Python', 'Java', 'C++']
Removing items from the queue:
Python
Java
C++
Queue after removal: []
2.2 Double-ended Queue
A double-ended queue also called deque is a data structure that allows the insertion and deletion of elements from both ends of the queue.
It allows you to add and remove elements from the front and back of the queue in constant time, making it an efficient data structure for many applications.
from collections import deque
# Create a deque
my_deque = deque(['Python', 'Java', 'C++', 'JavaScript'])
# Add a new item to the front of the deque
my_deque.appendleft('Go')
# Add a new item to the back of the deque
my_deque.append('Ruby')
# Remove a item from the front of the deque
first_item = my_deque.popleft()
# Remove a item from the back of the deque
last_item = my_deque.pop()
print(my_deque) # deque(['Java', 'C++', 'JavaScript'])
print(first_item) # 'Go'
print(last_item) # 'Ruby'
2.3 Circular Queue
Circular Queue is a type of queue in which the last element is connected to the first element to make a circular data structure. In other words, a circular queue wraps around and reuses the space that the first element took up after the last element.
This type of queue is useful when we want to store data in a circular manner and treat the data structure as a circular list. In a circular queue, there are two pointers, front and rear. You can dequeue elements using the front pointer and enqueue elements using the rear pointer in a circular queue.
See the following Example:
# Import deque from collections module
from collections import deque
# Create a deque with maximum size 3
my_circular_queue = deque(maxlen=3)
# Add items circular queue
my_circular_queue.append("Python")
my_circular_queue.append("Java")
my_circular_queue.append("C++")
# The queue is now full
print(my_circular_queue)
# deque(['Python', 'Java', 'C++'], maxlen=3)
# Add one more item to the queue
my_circular_queue.append("JavaScript")
# The oldest item is removed from the queue
print(my_circular_queue)
# deque(['Java', 'C++', 'JavaScript'], maxlen=3)
# Add two more items to the queue
my_circular_queue.append("Go")
my_circular_queue.append("Ruby")
# The two items are removed from the queue
print(my_circular_queue)
# deque(['JavaScript', 'Go', 'Ruby'], maxlen=3)
2.4 Priority Queue
A Priority Queue is a special type of queue where each element has a priority assigned to it, and the elements are dequeued in order of their priority. The element with the highest priority is dequeued first, followed by the element with the second highest priority, and so on.
Python’s queue
module provides an implementation of the Priority Queue data structure. See it in the following example:
import queue
# Create an empty priority queue
my_priority_queue = queue.PriorityQueue()
# Add tasks to the priority queue with their priority
my_priority_queue.put((2, "Task 1"))
my_priority_queue.put((1, "Task 2"))
my_priority_queue.put((3, "Task 3"))
# Process tasks in order of priority
while not my_priority_queue.empty():
priority, task = my_priority_queue.get()
print("Processing task:", task, "with priority:", priority)
Yields the following Output:
# Output:
Processing task: Task 2 with priority: 1
Processing task: Task 1 with priority: 2
Processing task: Task 3 with priority: 3
3. Implementation of Queue in Python
There are two common ways to implement a queue: using a list or using the queue class from the built-in queue module. Let’s see them one by one.
3.1 Python Queue with Queue Class
In Python, a queue can be implemented using a class with methods for enqueue, dequeue, size, and isEmpty.
# Create queue class
class Queue:
def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.is_empty():
return self.items.pop(0)
def size(self):
return len(self.items)
Now you can use this Queue in the following way:
# Create Queue object
my_queue = Queue()
# Add Items to queue
my_queue.enqueue(1)
my_queue.enqueue(2)
my_queue.enqueue(3)
# Check the size
print(my_queue.size()) # 3
# Remove Items
print(my_queue.dequeue()) # 1
print(my_queue.dequeue()) # 2
print(my_queue.size()) # 1
3.2 Python Queue with List
Implementing a queue using a list in Python is fairly simple. In this approach, we can use a list to represent the queue and use its built-in methods such as append()
to add elements to the back of the queue and pop()
to remove elements from the front of the queue.
# Initialize an empty queue
my_queue = []
# Add elements to the queue
my_queue.append(1)
my_queue.append(2)
my_queue.append(3)
# Remove elements from the front of the queue
first_item = my_queue.pop(0)
second_item = my_queue.pop(0)
# The queue now contains only one element (3)
print(my_queue) # [3]
4. Implementation of Double Ended Queue
Double-ended queue, also known as deque, can be implemented in Python using the collections
module. The module provides a class called deque
, which allows you to create a double-ended queue of any length. You can see the simple example below.
5. Implementation of Circular Queue
In Python, there is no built-in implementation of a circular queue. However, you can implement a circular queue using the built-in deque
class from the collections
module.
But let’s see how we can create a Custom class for our Circular Queue:
# Create Circular Queue class
class CircularQueue:
def __init__(self, k):
self.queue = [None] * k
self.head = self.tail = -1
self.size = 0
self.k = k
def enqueue(self, val):
if self.is_full():
return False
if self.is_empty():
self.head = 0
self.tail = (self.tail + 1) % self.k
self.queue[self.tail] = val
self.size += 1
return True
def dequeue(self):
if self.is_empty():
return False
if self.head == self.tail:
self.head, self.tail = -1, -1
else:
self.head = (self.head + 1) % self.k
self.size -= 1
return True
def front(self):
if self.is_empty():
return None
return self.queue[self.head]
def rear(self):
if self.is_empty():
return None
return self.queue[self.tail]
def is_empty(self):
return self.size == 0
def is_full(self):
return self.size == self.k
Let’s see how we can use this Circular queue in our Program:
# Create a circular queue with capacity of 4
my_circular_queue = CircularQueue(4)
# Add elements to the circular queue
my_circular_queue.enqueue(1)
my_circular_queue.enqueue(2)
my_circular_queue.enqueue(3)
my_circular_queue.enqueue(4)
# This should return False since the queue is full
my_circular_queue.enqueue(5)
# Check the front and rear elements of the queue
print(my_circular_queue.front()) # 1
print(my_circular_queue.rear()) # 4
# Remove elements from the circular queue
my_circular_queue.dequeue()
my_circular_queue.dequeue()
# Check the front and rear elements of the queue after dequeue
print(my_circular_queue.front()) # 3
print(my_circular_queue.rear()) # 4
6. Implementation of Priority Queue
Priority Queue in Python can be implemented using the queue
module. It provides the PriorityQueue
class in Python. We have seen it in the example above.
It allows the items to be added to the queue in any order, and they will be sorted and retrieved based on their priority value. The queue will retrieve the items with the highest priority first.
7. Operations on Queue in Python
Various operations can be performed on a Queue in Python, such as adding elements to the back of the queue, removing elements from the front of the queue, and checking the size of the queue.
7.1 Enqueue
The enqueue
is an operation in a queue data structure that adds an element to the rear or tail of the queue.
# Enqueue some elements
my_queue.append(1)
7.2 Dequeue
Dequeue is a method that removes and returns an element from the front of the queue. We use this method when we want to remove elements from the queue in the order in which we added them.
# Remove the first element from the queue
my_queue.popleft()
7.3 Status of Queue
Some commonly used methods to check the status of a queue include Peek, Size, Empty, and Full.
# Check the current size of the queue
print(my_queue.qsize()) # Output: 3
# Check if the queue is empty
print(my_queue.empty()) # Output: False
# Check if the queue is full
print(my_queue.full())
8. Use of Queue in Python
In Python, you can use queues for different purposes, below are a few use cases where you would like to use the queue data structure.
- Job scheduling: We can use queues to manage tasks that we schedule to execute in the future.
- Event handling: A program can use queues to handle events and ensure that it processes them in the correct order.
- Message queues: Different parts of a distributed system can use queues to manage the flow of messages between them.
- Network processing: Network processing applications use queues to manage incoming requests and outgoing responses.
9. Summary and Conclusion
We have discussed the Python Queue and its various implementations in Python, including the Queue, Double-ended Queue, Circular Queue, and Priority Queue. We have also covered the various operations on the Queue, such as enqueue, dequeue, peek, and size. If you have any questions please feel free to leave a comment below.
Happy coding!
Related Articles
- Get First and Last Elements of Deque in Python
- Python queue.priorityqueue Methods
- Python Stack LifoQueue Methods
- Python Deque Methods
- Python Queue Methods
- Python String Methods
- Python Random Module Methods Explained
- Static Methods in Python Explained
- Python List of Tuples into Dictionary
- Python List Unpacking with Examples
- Get substring of a string in Python
- Queue in Python with Examples
- How to Delete Item from Deque in python