Have you ever been to a grocery store and noticed the lines at the checkout? Chances are, you’d notice that the lines are organized in a particular way- the first person in the line gets to check out first.
This is an example of a queue, a data structure that follows the First-In, First-Out (FIFO) principle. Queues are used in various computer algorithms to manage resources, process tasks, and handle data.
In this article, we will learn about the different types of queues and how to implement them in Python. We will also cover the corner cases and how to handle them efficiently.
Types of Queues
1. FIFO Queue
FIFO or First-In-First-Out is a queue type that follows the principle of processing the items in the order they were inserted.
In a FIFO queue, items are added at the end of the queue, and the item at the front of the queue is processed first. The operations on a queue are enqueue (adding an item at the end) and dequeue (removing an item at the front).
2. LIFO Queue
LIFO or Last-In-First-Out is a queue type that follows the principle of processing the items in reverse order of their insertion.
In a LIFO queue or stack, items are added and removed from the top. The operations on a stack are push (adding an item) and pop (removing the topmost item).
3. Deque
A Deque or Double-Ended Queue is a type of queue that combines the principles of both FIFO and LIFO.
In a Deque, items can be added and removed from both ends. The operations on a deque are enqueue from the rear, dequeue from the front, push from the front, pop from the front, push from the rear, and pop from the rear.
4. Priority Queue
A Priority Queue is a type of queue that processes items in order of their priority.
The priority of an item is specified during insertion, and the highest priority item is processed first. The operations on a priority queue are insertion and deletion.
Implementing Queues in Python
Python provides built-in support for implementing stacks and queues using the deque module from the collections library. We can import the deque module and initialize the deque object using the deque() function.
1. Creating a FIFO Queue using a Deque
We can implement the FIFO queue using the deque object by adding items to the rear and removing items from the front.
Here is an example of the implementation:
“`
from collections import deque
fifo_queue = deque()
# Insert items to queue
fifo_queue.append(“apple”)
fifo_queue.append(“banana”)
fifo_queue.append(“cherry”)
# Remove items from queue
fifo_queue.popleft() # “apple”
fifo_queue.popleft() # “banana”
“`
2. Creating a LIFO Queue using a Deque
We can implement the LIFO queue using the deque object by adding items to the top and removing items from the top.
Here is an example of the implementation:
“`
from collections import deque
lifo_queue = deque()
# Insert items to queue
lifo_queue.append(“apple”)
lifo_queue.append(“banana”)
lifo_queue.append(“cherry”)
# Remove items from queue
lifo_queue.pop() # “cherry”
lifo_queue.pop() # “banana”
“`
3. Creating a Deque
We can implement the deque using the deque object and add or remove items from the front or the rear.
Here is an example of the implementation:
“`
from collections import deque
deque_object = deque()
# Insert items to deque
deque_object.append(“apple”) # rear
deque_object.appendleft(“banana”) # front
deque_object.append(“cherry”) # rear
# Remove items from deque
deque_object.popleft() # “banana”
deque_object.pop() # “cherry”
“`
4. Creating a Priority Queue using a Heap
We can implement a priority queue using a heap where items are sorted based on their priority.
Python provides the heapq module to create and manipulate the heap. “`
import heapq
priority_queue = []
# Insert items to priority queue
heapq.heappush(priority_queue, (5, “apple”))
heapq.heappush(priority_queue, (2, “banana”))
heapq.heappush(priority_queue, (3, “cherry”))
# Remove items from priority queue
heapq.heappop(priority_queue) # (2, “banana”)
heapq.heappop(priority_queue) # (3, “cherry”)
“`
5. Handling Corner Cases in a Priority Queue
There are certain corner cases to consider when implementing a priority queue where items have the same priority.
In such cases, we can use the item’s insertion order to break the tie and maintain data consistency. Here is an example of the implementation:
“`
import heapq
import itertools
priority_queue = []
counter = itertools.count()
# Insert items to priority queue
heapq.heappush(priority_queue, (5, next(counter), “apple”))
heapq.heappush(priority_queue, (2, next(counter), “banana”))
heapq.heappush(priority_queue, (3, next(counter), “cherry”))
heapq.heappush(priority_queue, (2, next(counter), “date”))
# Remove items from priority queue
heapq.heappop(priority_queue) # (2, 2, “banana”)
heapq.heappop(priority_queue) # (2, 4, “date”)
“`
6. Refactoring the Code Using a Mixin Class
We can refactor our code by using a mix-in class to avoid code redundancy and improve code productivity.
In Python, a mix-in class is a class that provides functionality to be inherited by other classes. Here is an implementation example:
“`
from collections import deque
class QueueMixin:
def enqueue(self, item):
self.append(item)
def dequeue(self):
return self.popleft()
class StackMixin:
def push(self, item):
self.append(item)
def pop(self):
return self.pop()
class DequeMixin(QueueMixin, StackMixin):
def __init__(self):
self = deque()
class PriorityQueue:
def __init__(self):
self = []
def insert(self, item):
heapq.heappush(self, item)
def delete(self):
return heapq.heappop(self)
“`
Conclusion
In this article, we have learned about the different types of queues and how to implement them in Python. We have also covered corner cases and how to handle them efficiently.
With the code examples provided, it should be easy for you to implement these queues in your own Python programs. By mastering these data structures, you can greatly improve the efficiency and performance of your code.
Queues are a fundamental data structure that plays an essential role in various computer science algorithms, including pathfinding and graph traversal algorithms. In this article, we will discuss the practical applications of queues, including examples of how they can be used to solve real-world problems.
We will also explore using thread-safe queues and how they can be utilized in multi-threaded applications.
Using Queues for Pathfinding and Graph Traversal
A perfect example of using queues in practice is pathfinding and graph traversal algorithms. These algorithms rely heavily on the properties of the queue data structures, such as First-In, First-Out (FIFO) and Last-In, First-Out (LIFO), to traverse graphs and identify paths.
Sample Data: Road Map of the United Kingdom
Let us consider a realistic scenario where we want to find the shortest path between two cities in the United Kingdom. We can represent the road map as a graph where cities are nodes in the graph, and roads are the edges connecting the nodes.
Let us consider this simple representation of the UK road map below:
Object Representation of the Cities and Roads
We can represent this graph using objects in Python. Each node (city) in the graph can be represented as an object with a label attribute that identifies the city.
The object can also include an adjacency list attribute that maintains a list of the edges (roads) that connect the node (city) to other nodes (cities) in the graph. Here is an example of the code implementation:
“`
class Node:
def __init__(self, label):
self.label = label
self.adj_list = []
def __repr__(self):
return self.label
“`
We can now create instances of the Node class for each city in the UK and add the edges (roads) to their adjacency lists.
“`
london = Node(“London”)
manchester = Node(“Manchester”)
liverpool = Node(“Liverpool”)
newcastle = Node(“Newcastle”)
leeds = Node(“Leeds”)
birmingham = Node(“Birmingham”)
glasgow = Node(“Glasgow”)
cardiff = Node(“Cardiff”)
london.adj_list.append(manchester)
london.adj_list.append(birmingham)
manchester.adj_list.append(liverpool)
manchester.adj_list.append(newcastle)
manchester.adj_list.append(london)
liverpool.adj_list.append(manchester)
newcastle.adj_list.append(manchester)
newcastle.adj_list.append(glasgow)
leeds.adj_list.append(birmingham)
leeds.adj_list.append(glasgow)
birmingham.adj_list.append(london)
birmingham.adj_list.append(leeds)
birmingham.adj_list.append(cardiff)
glasgow.adj_list.append(newcastle)
glasgow.adj_list.append(leeds)
cardiff.adj_list.append(birmingham)
“`
Breadth-First Search Using a FIFO Queue
Breadth-First Search (BFS) is a pathfinding algorithm that traverses a graph in breadth-first order, starting from a given node. In this traversal, it tries to visit all the nodes at the current depth level before moving to their respective children.
BFS uses a FIFO queue to keep track of all the nodes to visit. Here is the implementation of BFS using a FIFO queue to find the shortest path between two cities, London and Glasgow.
“`
from collections import deque
start_node = london
end_node = glasgow
visited = set()
queue = deque([start_node])
parents = {}
while queue:
current_node = queue.popleft()
if current_node == end_node:
# reconstruct path from parent dictionary and return it
path = []
while current_node != start_node:
path.append(current_node)
current_node = parents[current_node]
path.append(start_node)
return reversed(path)
visited.add(current_node)
for neighbor in current_node.adj_list:
if neighbor not in visited:
queue.append(neighbor)
parents[neighbor] = current_node
“`
The above BFS implementation starts the traversal from the start node (london) and checks all of its neighbors at the current level (manchester and birmingham) before moving on to their respective children (liverpool, newcastle, and leeds). This algorithm repeats this until it finds the end node (glasgow) and reconstructs the shortest path using the parent dictionary.
Shortest Path Using Breadth-First Traversal
The shortest path finding algorithm with BFS is not efficient in large and complex graphs. It takes a lot of time, especially when the algorithm does not find the target node close to the start node.
This search method would apply in cases when the graph will have few nodes or edges. In real-world applications, Shortest Path using Breadth-First Traversal is used to find the shortest path between nodes in a graph.
Here is the implementation of the Shortest Path using Breadth-First Traversal algorithm. “`
from collections import defaultdict, deque
def shortest_path(start, target, graph):
visited = set()
queue = deque([(start, 0)])
while queue:
current, distance = queue.popleft()
visited.add(current)
if current == target:
return distance
for neighbor in graph[current]:
if not neighbor in visited:
queue.append((neighbor, distance + 1))
return -1
“`
The above function takes in three parameters: the start node, target node, and graph (altered adjacency list to represent the graph).
It starts the traversal from the start node and checks all its neighbors at the current level before moving to their respective children. Along the way, the nodes are visited and their distances from the source are calculated.
The algorithm repeats this until it finds the target node and returns the shortest distance.
Depth-First Search Using a LIFO Queue
Depth-First Search (DFS) is another pathfinding algorithm that traverses a graph in the depth direction. DFS uses a LIFO queue (a stack) to store all the nodes to visit, and it explores as far as possible along each branch before backtracking.
To implement DFS, we need to use a stack instead of a queue. Here is an implemention using the DFS algorithm.
“`
def DFS(start, graph):
visited, stack = set(), [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(set(graph[vertex])-visited)
return visited
“`
The above function takes two parameters; the start node, and the graph. It starts the traversal from the start node and checks all its children at the current depth before moving to their respective children.
Along the way, the nodes are visited and marked as visited before backtracking to the next node. Dijkstra’s Algorithm Using a Priority Queue
Dijkstra’s algorithm for pathfinding is an efficient algorithm that finds the shortest path between nodes in a graph.
It works by repeatedly selecting the node with the smallest tentative distance and finding its neighbors. This algorithm finds the shortest path between two nodes in a graph, where all edges’ costs are non-negative.
Here is an implemention
“`
import heapq
from collections import defaultdict
def dijkstra(start, target, graph):
visited = set()
heap = [(0, start, [])]
while heap:
(cost, current_city, path) = heapq.heappop(heap)
if current_city not in visited:
visited.add(current_city)
path = path + [current_city]
if current_city == target:
return path, cost
for neighbor, c in graph[current_city].items():
if neighbor not in visited:
heapq.heappush(heap, (cost+c, neighbor, path))
return [], 0
“`
The above function takes three parameters; the start node, target node, and altered adjacency list graph. It starts the traversal from the start node and selects the node with the smallest distance from the start node.
The algorithm repeats this until it finds the target node and returns the shortest path and its cost.
Using Thread-safe Queues
When working with multi-threaded applications, it is essential to use thread-safe data structures to avoid data races or deadlocks in the code. Python provides three types of thread-safe queues: queue.Queue, queue.LifoQueue, and queue.PriorityQueue.
1. queue.Queue
The queue.Queue class is a thread-safe queue implementation that follows the FIFO principle.
It provides useful methods like put and get that can be used to add elements to the queue and get elements from the queue, respectively. “`
import queue
q = queue.Queue()
# Add elements to the queue
q.put(‘a’)
q.put(‘b’)
q.put(‘c’)
# Get elements from the queue
print(q.get()) # ‘a’
print(q.get()) # ‘b’
“`
2. queue.LifoQueue
The queue.LifoQueue class is another thread-safe queue implementation that follows the LIFO principle.
It provides useful methods like put and get that can be used to add elements to the queue and get elements from the queue, respectively. “`
import queue
q = queue.LifoQueue()
# Add elements to the queue
q.put(‘a’)
q.put(‘b’)
q.put(‘c’)
# Get elements from the queue
print(q.get()) # ‘c’
print(q.get()) # ‘b’
“`
3. queue.PriorityQueue
The queue.PriorityQueue class is a thread-safe queue implementation that follows the priority principle.
It provides useful methods like put and get that can be used to add elements to the queue and get elements from the queue, respectively. “`
import queue
q =