Introduction to Queues
Welcome to Day 12 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore queues, another fundamental data structure that follows the First-In-First-Out (FIFO) principle.
What is a Queue?
A queue is a linear data structure that follows a particular order in which operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first.
Basic Operations of a Queue
- Enqueue: Adds an element to the rear of the queue
- Dequeue: Removes the element from the front of the queue
- Front: Get the front element from the queue without removing it
- Rear: Get the last element from the queue without removing it
- isEmpty: Check if the queue is empty
Implementing a Queue in Python
We can implement a queue using a Python list or create a custom class. Let’s implement both:
Using a Python List
1class Queue:
2 def __init__(self):
3 self.items = []
4
5 def is_empty(self):
6 return len(self.items) == 0
7
8 def enqueue(self, item):
9 self.items.append(item)
10
11 def …
Introduction to Queues
Welcome to Day 12 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore queues, another fundamental data structure that follows the First-In-First-Out (FIFO) principle.
What is a Queue?
A queue is a linear data structure that follows a particular order in which operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first.
Basic Operations of a Queue
- Enqueue: Adds an element to the rear of the queue
- Dequeue: Removes the element from the front of the queue
- Front: Get the front element from the queue without removing it
- Rear: Get the last element from the queue without removing it
- isEmpty: Check if the queue is empty
Implementing a Queue in Python
We can implement a queue using a Python list or create a custom class. Let’s implement both:
Using a Python List
1class Queue:
2 def __init__(self):
3 self.items = []
4
5 def is_empty(self):
6 return len(self.items) == 0
7
8 def enqueue(self, item):
9 self.items.append(item)
10
11 def dequeue(self):
12 if not self.is_empty():
13 return self.items.pop(0)
14 else:
15 raise IndexError("Queue is empty")
16
17 def front(self):
18 if not self.is_empty():
19 return self.items[0]
20 else:
21 raise IndexError("Queue is empty")
22
23 def rear(self):
24 if not self.is_empty():
25 return self.items[-1]
26 else:
27 raise IndexError("Queue is empty")
28
29 def size(self):
30 return len(self.items)
Using a Custom Node Class
1class Node:
2 def __init__(self, data):
3 self.data = data
4 self.next = None
5
6class Queue:
7 def __init__(self):
8 self.front = None
9 self.rear = None
10
11 def is_empty(self):
12 return self.front is None
13
14 def enqueue(self, item):
15 new_node = Node(item)
16 if self.rear is None:
17 self.front = self.rear = new_node
18 return
19 self.rear.next = new_node
20 self.rear = new_node
21
22 def dequeue(self):
23 if self.is_empty():
24 raise IndexError("Queue is empty")
25 dequeued = self.front.data
26 self.front = self.front.next
27 if self.front is None:
28 self.rear = None
29 return dequeued
30
31 def get_front(self):
32 if self.is_empty():
33 raise IndexError("Queue is empty")
34 return self.front.data
35
36 def get_rear(self):
37 if self.is_empty():
38 raise IndexError("Queue is empty")
39 return self.rear.data
40
41 def size(self):
42 count = 0
43 current = self.front
44 while current:
45 count += 1
46 current = current.next
47 return count
Time Complexity
- Enqueue operation: O(1)
- Dequeue operation: O(1) for linked list implementation, O(n) for array implementation
- Front operation: O(1)
- Rear operation: O(1)
Applications of Queues
- CPU Scheduling: Manages processes waiting to be executed
- Breadth-First Search: Used in graph algorithms
- Handling of requests on a single shared resource: Printer, CPU task scheduling
- Buffering: In streaming media, routers, etc.
- Asynchronous data transfer: IO Buffers, pipes, file IO, etc.
Example: Level Order Traversal of a Binary Tree
Let’s implement a function to perform level order traversal of a binary tree using a queue:
1from collections import deque
2
3class TreeNode:
4 def __init__(self, value):
5 self.value = value
6 self.left = None
7 self.right = None
8
9def level_order_traversal(root):
10 if not root:
11 return []
12
13 result = []
14 queue = deque([root])
15
16 while queue:
17 level_size = len(queue)
18 current_level = []
19
20 for _ in range(level_size):
21 node = queue.popleft()
22 current_level.append(node.value)
23
24 if node.left:
25 queue.append(node.left)
26 if node.right:
27 queue.append(node.right)
28
29 result.append(current_level)
30
31 return result
32
33# Test the function
34root = TreeNode(1)
35root.left = TreeNode(2)
36root.right = TreeNode(3)
37root.left.left = TreeNode(4)
38root.left.right = TreeNode(5)
39
40print(level_order_traversal(root)) # Output: [[1], [2, 3], [4, 5]]
Exercise
- Implement a circular queue using an array.
- Create a function to reverse the first K elements of a queue.
- Implement a stack using two queues.
Summary
Today, we explored the queue data structure, its implementation, and a practical application in tree traversal. Queues are essential in many algorithms and real-world applications due to their FIFO nature. Understanding queues will help you solve various problems efficiently, especially in scenarios involving ordered processing or breadth-first algorithms.
Tomorrow, we’ll begin our exploration of trees, starting with an introduction to tree data structures and their properties. Stay tuned!