DSA — Queues

What is a Queue?

A First-In-First-Out (FIFO) data structure.

class Queue:
    def __init__(self):
        self.items = []
    
    def enqueue(self, item):
        self.items.append(item)
    
    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)
    
    def front(self):
        if not self.is_empty():
            return self.items[0]
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)

Operations

Operation	Time Complexity
enqueue	O(1)
dequeue	O(n)
front	O(1)
is_empty	O(1)

Circular Queue

class CircularQueue:
    def __init__(self, capacity):
        self.queue = [None] * capacity
        self.front = 0
        self.rear = -1
        self.size = 0
        self.capacity = capacity
    
    def enqueue(self, item):
        if self.size == self.capacity:
            return False
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = item
        self.size += 1
        return True
    
    def dequeue(self):
        if self.size == 0:
            return None
        item = self.queue[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return item

Mini Practice

1. Implement a queue
2. Implement a circular queue
3. Use queue for BFS
4. Implement a priority queue

Up Next

Continue with Deques — double-ended queue.