Queues
Simple Queue
A simple queue is a data structure that follows the First In First Out (FIFO) principle. It allows for the addition of elements at the back and removal of elements from the front.
Space Complexity: O(n)
Time Complexity: O(1) for enqueue/dequeue
Best Case: Ω(1)
Average Case: Θ(1)
Worst Case: O(1)
class SimpleQueue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.items:
return None
return self.items.pop(0)
def front(self):
if not self.items:
return None
return self.items[0]
def is_empty(self):
return len(self.items) == 0
def display(self):
return ' -> '.join(map(str, self.items))
# Example Usage
queue = SimpleQueue()
for i in range(20):
queue.enqueue(random.randint(0, 100))
print(queue.display())
Priority Queue
A priority queue is a special type of queue where each element is associated with a priority. Elements are dequeued based on their priority, rather than their order in the queue.
Space Complexity: O(n)
Time Complexity: O(log n) for enqueue (insertion)
Best Case: Ω(1)
Average Case: Θ(log n)
Worst Case: O(log n)
class PriorityQueue:
def __init__(self):
self.items = []
def enqueue(self, item, priority):
queue_element = {"element": item, "priority": priority}
added = False
for i in range(len(self.items)):
if queue_element["priority"] < self.items[i]["priority"]:
self.items.insert(i, queue_element)
added = True
break
if not added:
self.items.append(queue_element)
def dequeue(self):
if not self.items:
return None
return self.items.pop(0)["element"]
def front(self):
if not self.items:
return None
return self.items[0]["element"]
def is_empty(self):
return len(self.items) == 0
def display(self):
return ' -> '.join([f'{item["element"]}({item["priority"]})' for item in self.items])
# Example Usage
priority_queue = PriorityQueue()
for i in range(20):
priority_queue.enqueue(random.randint(0, 100), random.randint(1, 10))
print(priority_queue.display())
Deque (Double-Ended Queue)
A deque (double-ended queue) is a linear data structure that allows insertion and removal of elements from both ends. It is a more generalized form of queue.
Space Complexity: O(n)
Time Complexity: O(1) for operations on both ends
Best Case: Ω(1)
Average Case: Θ(1)
Worst Case: O(1)
class Deque:
def __init__(self):
self.items = []
def add_front(self, item):
self.items.insert(0, item)
def add_rear(self, item):
self.items.append(item)
def remove_front(self):
if not self.items:
return None
return self.items.pop(0)
def remove_rear(self):
if not self.items:
return None
return self.items.pop()
def front(self):
if not self.items:
return None
return self.items[0]
def rear(self):
if not self.items:
return None
return self.items[-1]
def is_empty(self):
return len(self.items) == 0
def display(self):
return ' -> '.join(map(str, self.items))
# Example Usage
deque = Deque()
for i in range(20):
deque.add_rear(random.randint(0, 100))
print(deque.display())