Queue Data Structure in Python – DSA

      Ankush More

      Table of Contents

      1. Introduction
      2. Queue Fundamentals
      3. Types of Queues
      4. Implementation Methods
      5. Operations and Time Complexity
      6. Practical Applications
      7. Common Problems
      8. Advanced Topics

      Introduction

      A Queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. The first element added to the queue will be the first one to be removed. Think of it like a line of people waiting at a ticket counter.

      Real-World Analogies

      • Queue at a bank or supermarket checkout
      • Print job queue
      • Call center waiting system
      • Traffic at a toll booth
      • Operating system task scheduling

      Key Characteristics

      • FIFO: First In, First Out
      • Two-End Operations: Insert at rear (back), remove from front
      • Linear Structure: Elements are arranged in sequential order
      • Dynamic Size: Can grow or shrink as needed

      Queue Fundamentals

      Basic Operations

      1. Enqueue: Add an element to the rear of the queue
      2. Dequeue: Remove and return the front element
      3. Front/Peek: View the front element without removing it
      4. Rear: View the rear element without removing it
      5. isEmpty: Check if the queue is empty
      6. Size: Get the number of elements in the queue

      Visual Representation

      Initial Queue:              After Enqueue(5):         After Dequeue():
Front → [1, 2, 3] ← Rear    Front → [1, 2, 3, 5] ← Rear    Front → [2, 3, 5] ← Rear
      Python

      FIFO in Action

      Enqueue Order: 1 → 2 → 3 → 4 → 5
Dequeue Order: 1 → 2 → 3 → 4 → 5
      Python

      Types of Queues

      1. Simple Queue (Linear Queue)

      Standard FIFO queue with enqueue at rear and dequeue from front.

      2. Circular Queue

      Last position connects back to the first position, making efficient use of space.

      3. Priority Queue

      Elements are dequeued based on priority, not insertion order.

      4. Double-Ended Queue (Deque)

      Elements can be added or removed from both ends.

      5. Input/Output Restricted Queue

      • Input Restricted: Insertion only at one end, deletion at both ends
      • Output Restricted: Deletion only at one end, insertion at both ends

      Implementation Methods

      Method 1: Using Python List (Simple but Inefficient)

      class QueueList:
    """Queue implementation using Python list"""

    def __init__(self):
        """Initialize an empty queue"""
        self.items = []

    def is_empty(self):
        """Check if queue is empty"""
        return len(self.items) == 0

    def enqueue(self, item):
        """Add item to rear of queue"""
        self.items.append(item)

    def dequeue(self):
        """Remove and return front item"""
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self.items.pop(0)  # O(n) operation!

    def front(self):
        """Return front item without removing"""
        if self.is_empty():
            raise IndexError("front from empty queue")
        return self.items[0]

    def rear(self):
        """Return rear item without removing"""
        if self.is_empty():
            raise IndexError("rear from empty queue")
        return self.items[-1]

    def size(self):
        """Return number of items in queue"""
        return len(self.items)

    def __str__(self):
        return f"Queue({self.items})"


# Example usage
queue = QueueList()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(f"Queue: {queue}")              # Queue([1, 2, 3])
print(f"Front: {queue.front()}")      # 1
print(f"Rear: {queue.rear()}")        # 3
print(f"Dequeue: {queue.dequeue()}")  # 1
print(f"Size: {queue.size()}")        # 2
      Python

      The deque provides O(1) operations for both ends.

      from collections import deque

class Queue:
    """Queue implementation using collections.deque (RECOMMENDED)"""

    def __init__(self):
        self.items = deque()

    def is_empty(self):
        return len(self.items) == 0

    def enqueue(self, item):
        """Add item to rear - O(1)"""
        self.items.append(item)

    def dequeue(self):
        """Remove and return front item - O(1)"""
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self.items.popleft()

    def front(self):
        """Return front item"""
        if self.is_empty():
            raise IndexError("front from empty queue")
        return self.items[0]

    def rear(self):
        """Return rear item"""
        if self.is_empty():
            raise IndexError("rear from empty queue")
        return self.items[-1]

    def size(self):
        return len(self.items)

    def __str__(self):
        return f"Queue({list(self.items)})"

    def __len__(self):
        return len(self.items)


# Example usage
queue = Queue()
for i in range(1, 6):
    queue.enqueue(i)
print(queue)  # Queue([1, 2, 3, 4, 5])

while not queue.is_empty():
    print(f"Dequeued: {queue.dequeue()}")
      Python

      Method 3: Using queue.Queue (Thread-Safe)

      Python’s queue.Queue is thread-safe and suitable for multi-threaded applications.

      from queue import Queue as ThreadSafeQueue

# Create a queue with optional max size
queue = ThreadSafeQueue(maxsize=10)

# Enqueue items
queue.put(1)
queue.put(2)
queue.put(3)

# Dequeue items
print(queue.get())  # 1
print(queue.get())  # 2

# Check if empty
print(queue.empty())  # False

# Check if full
print(queue.full())   # False

# Get approximate size
print(queue.qsize())  # 1

# Non-blocking operations
try:
    queue.get(block=False)  # Get without blocking
except:
    print("Queue is empty")

# Timeout operations
try:
    queue.get(timeout=1)  # Wait max 1 second
except:
    print("Timeout")
      Python

      Method 4: Circular Queue Implementation

      class CircularQueue:
    """Circular Queue implementation using array"""

    def __init__(self, capacity):
        self.capacity = capacity
        self.items = [None] * capacity
        self.front = -1
        self.rear = -1
        self.count = 0

    def is_empty(self):
        return self.count == 0

    def is_full(self):
        return self.count == self.capacity

    def enqueue(self, item):
        """Add item to circular queue"""
        if self.is_full():
            raise OverflowError("Queue is full")

        if self.front == -1:
            self.front = 0

        self.rear = (self.rear + 1) % self.capacity
        self.items[self.rear] = item
        self.count += 1

    def dequeue(self):
        """Remove and return front item"""
        if self.is_empty():
            raise IndexError("Queue is empty")

        item = self.items[self.front]

        if self.front == self.rear:
            self.front = -1
            self.rear = -1
        else:
            self.front = (self.front + 1) % self.capacity

        self.count -= 1
        return item

    def peek(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.items[self.front]

    def size(self):
        return self.count

    def display(self):
        if self.is_empty():
            return "Queue is empty"

        result = []
        i = self.front
        for _ in range(self.count):
            result.append(self.items[i])
            i = (i + 1) % self.capacity
        return f"CircularQueue({result})"


# Example usage
cq = CircularQueue(5)
for i in range(1, 6):
    cq.enqueue(i)
print(cq.display())  # CircularQueue([1, 2, 3, 4, 5])

cq.dequeue()
cq.dequeue()
cq.enqueue(6)
cq.enqueue(7)
print(cq.display())  # CircularQueue([3, 4, 5, 6, 7])
      Python

      Method 5: Priority Queue Implementation

      import heapq

class PriorityQueue:
    """Priority Queue using heapq (min-heap)"""

    def __init__(self):
        self.heap = []
        self.counter = 0  # For tie-breaking

    def is_empty(self):
        return len(self.heap) == 0

    def enqueue(self, item, priority):
        """Add item with priority (lower number = higher priority)"""
        heapq.heappush(self.heap, (priority, self.counter, item))
        self.counter += 1

    def dequeue(self):
        """Remove and return highest priority item"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        return heapq.heappop(self.heap)[2]

    def peek(self):
        """View highest priority item"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.heap[0][2]

    def size(self):
        return len(self.heap)


# Example usage
pq = PriorityQueue()
pq.enqueue("Low priority task", 3)
pq.enqueue("High priority task", 1)
pq.enqueue("Medium priority task", 2)

while not pq.is_empty():
    print(pq.dequeue())
# Output:
# High priority task
# Medium priority task
# Low priority task
      Python

      Method 6: Double-Ended Queue (Deque)

      from collections import deque

class Deque:
    """Double-ended queue implementation"""

    def __init__(self):
        self.items = deque()

    def is_empty(self):
        return len(self.items) == 0

    def add_front(self, item):
        """Add item to front"""
        self.items.appendleft(item)

    def add_rear(self, item):
        """Add item to rear"""
        self.items.append(item)

    def remove_front(self):
        """Remove and return front item"""
        if self.is_empty():
            raise IndexError("Deque is empty")
        return self.items.popleft()

    def remove_rear(self):
        """Remove and return rear item"""
        if self.is_empty():
            raise IndexError("Deque is empty")
        return self.items.pop()

    def peek_front(self):
        if self.is_empty():
            raise IndexError("Deque is empty")
        return self.items[0]

    def peek_rear(self):
        if self.is_empty():
            raise IndexError("Deque is empty")
        return self.items[-1]

    def size(self):
        return len(self.items)

    def __str__(self):
        return f"Deque({list(self.items)})"


# Example usage
dq = Deque()
dq.add_rear(1)
dq.add_rear(2)
dq.add_front(0)
print(dq)  # Deque([0, 1, 2])
      Python

      Method 7: Queue Using Linked List

      class Node:
    """Node for linked list"""
    def __init__(self, data):
        self.data = data
        self.next = None


class QueueLinkedList:
    """Queue implementation using linked list"""

    def __init__(self):
        self.front = None
        self.rear = None
        self._size = 0

    def is_empty(self):
        return self.front is None

    def enqueue(self, item):
        """Add item to rear - O(1)"""
        new_node = Node(item)

        if self.rear is None:
            self.front = self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

        self._size += 1

    def dequeue(self):
        """Remove and return front item - O(1)"""
        if self.is_empty():
            raise IndexError("Queue is empty")

        item = self.front.data
        self.front = self.front.next

        if self.front is None:
            self.rear = None

        self._size -= 1
        return item

    def peek_front(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.front.data

    def peek_rear(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.rear.data

    def size(self):
        return self._size

    def __str__(self):
        items = []
        current = self.front
        while current:
            items.append(current.data)
            current = current.next
        return f"Queue({items})"


# Example usage
queue = QueueLinkedList()
queue.enqueue('A')
queue.enqueue('B')
queue.enqueue('C')
print(queue)  # Queue(['A', 'B', 'C'])
print(queue.dequeue())  # A
      Python

      Operations and Time Complexity

      Time Complexity Comparison

      OperationListDequequeue.QueueCircular QueueLinked List
      EnqueueO(1)*O(1)O(1)O(1)O(1)
      DequeueO(n)O(1)O(1)O(1)O(1)
      FrontO(1)O(1)N/AO(1)O(1)
      RearO(1)O(1)N/AO(1)O(1)
      isEmptyO(1)O(1)O(1)O(1)O(1)
      SizeO(1)O(1)O(1)O(1)O(1)

      *Amortized O(1)

      Space Complexity

      • All implementations: O(n) where n is the number of elements

      Performance Benchmark

      import time
from collections import deque

def benchmark_queue_operations(n=100000):
    """Compare performance of different queue implementations"""

    # List-based queue (inefficient)
    start = time.time()
    list_queue = []
    for i in range(n):
        list_queue.append(i)
    for i in range(n):
        list_queue.pop(0)
    list_time = time.time() - start

    # Deque-based queue (efficient)
    start = time.time()
    deque_queue = deque()
    for i in range(n):
        deque_queue.append(i)
    for i in range(n):
        deque_queue.popleft()
    deque_time = time.time() - start

    print(f"Operations: {n * 2}")
    print(f"List-based:  {list_time:.4f} seconds")
    print(f"Deque-based: {deque_time:.4f} seconds")
    print(f"Speedup: {list_time/deque_time:.2f}x faster with deque")

# Run benchmark
benchmark_queue_operations(10000)
      Python

      Practical Applications

      1. BFS (Breadth-First Search) in Graphs

      from collections import deque

def bfs(graph, start):
    """
    Breadth-first search traversal

    graph: adjacency list representation
    start: starting vertex
    """
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []

    while queue:
        vertex = queue.popleft()
        result.append(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return result


# Example graph
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("BFS traversal:", bfs(graph, 'A'))
# Output: BFS traversal: ['A', 'B', 'C', 'D', 'E', 'F']
      Python

      2. Level Order Tree Traversal

      from collections import deque

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def level_order_traversal(root):
    """Level-by-level tree traversal using queue"""
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(current_level)

    return result


# Create a binary tree
#       1
#      / \
#     2   3
#    / \   \
#   4   5   6

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)

print("Level order:", level_order_traversal(root))
# Output: [[1], [2, 3], [4, 5, 6]]
      Python

      3. Task Scheduling System

      from collections import deque
from datetime import datetime

class Task:
    def __init__(self, name, priority=0):
        self.name = name
        self.priority = priority
        self.created_at = datetime.now()

    def __repr__(self):
        return f"Task({self.name}, priority={self.priority})"


class TaskScheduler:
    """Simple task scheduler using queue"""

    def __init__(self):
        self.queue = deque()

    def add_task(self, task):
        """Add task to queue"""
        self.queue.append(task)
        print(f"Added: {task.name}")

    def process_next_task(self):
        """Process next task in queue"""
        if not self.queue:
            print("No tasks to process")
            return None

        task = self.queue.popleft()
        print(f"Processing: {task.name}")
        return task

    def pending_tasks(self):
        """Get number of pending tasks"""
        return len(self.queue)

    def peek_next(self):
        """View next task without processing"""
        if self.queue:
            return self.queue[0]
        return None


# Example usage
scheduler = TaskScheduler()
scheduler.add_task(Task("Send email"))
scheduler.add_task(Task("Generate report"))
scheduler.add_task(Task("Backup database"))

print(f"\nPending: {scheduler.pending_tasks()}")
print(f"Next task: {scheduler.peek_next()}")

print("\nProcessing tasks:")
while scheduler.pending_tasks() > 0:
    scheduler.process_next_task()
      Python

      4. Print Job Queue

      from collections import deque
import time

class PrintJob:
    def __init__(self, document, pages):
        self.document = document
        self.pages = pages

    def __repr__(self):
        return f"{self.document} ({self.pages} pages)"


class PrintQueue:
    """Printer queue simulation"""

    def __init__(self):
        self.queue = deque()
        self.current_job = None

    def submit_job(self, job):
        """Submit print job"""
        self.queue.append(job)
        print(f"Submitted: {job}")

    def start_printing(self):
        """Process print queue"""
        while self.queue:
            self.current_job = self.queue.popleft()
            print(f"\nPrinting: {self.current_job}")
            # Simulate printing time
            time.sleep(0.5)
            print(f"Completed: {self.current_job}")

        print("\nAll jobs completed!")

    def cancel_job(self, document_name):
        """Cancel a pending job"""
        for i, job in enumerate(self.queue):
            if job.document == document_name:
                removed = self.queue[i]
                del self.queue[i]
                print(f"Cancelled: {removed}")
                return True
        print(f"Job not found: {document_name}")
        return False

    def get_queue_status(self):
        """Show current queue status"""
        if not self.queue:
            print("Queue is empty")
        else:
            print(f"\nJobs in queue ({len(self.queue)}):")
            for i, job in enumerate(self.queue, 1):
                print(f"  {i}. {job}")


# Example usage
printer = PrintQueue()
printer.submit_job(PrintJob("Report.pdf", 10))
printer.submit_job(PrintJob("Invoice.pdf", 2))
printer.submit_job(PrintJob("Contract.pdf", 5))

printer.get_queue_status()
# Uncomment to see printing in action
# printer.start_printing()
      Python

      5. CPU Process Scheduling (Round Robin)

      from collections import deque

class Process:
    def __init__(self, pid, burst_time):
        self.pid = pid
        self.burst_time = burst_time
        self.remaining_time = burst_time

    def __repr__(self):
        return f"P{self.pid}({self.remaining_time})"


def round_robin(processes, quantum):
    """
    Round Robin CPU scheduling algorithm

    processes: list of Process objects
    quantum: time quantum for each process
    """
    queue = deque(processes)
    time = 0
    schedule = []

    while queue:
        process = queue.popleft()

        if process.remaining_time <= quantum:
            # Process completes
            time += process.remaining_time
            schedule.append((process.pid, time))
            print(f"Time {time}: Process {process.pid} completed")
        else:
            # Process needs more time
            time += quantum
            process.remaining_time -= quantum
            queue.append(process)
            print(f"Time {time}: Process {process.pid} paused (remaining: {process.remaining_time})")

    return schedule


# Example processes
processes = [
    Process(1, 10),
    Process(2, 5),
    Process(3, 8)
]

quantum = 3
print("Round Robin Scheduling (quantum=3):")
schedule = round_robin(processes, quantum)
      Python

      6. Cache Implementation (LRU Cache)

      from collections import OrderedDict

class LRUCache:
    """Least Recently Used Cache using OrderedDict"""

    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        """Get value and mark as recently used"""
        if key not in self.cache:
            return -1

        # Move to end (most recently used)
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        """Put key-value pair"""
        if key in self.cache:
            # Update and move to end
            self.cache.move_to_end(key)

        self.cache[key] = value

        # Remove least recently used if over capacity
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

    def display(self):
        """Display cache contents (most recent last)"""
        print(f"Cache: {list(self.cache.items())}")


# Example usage
cache = LRUCache(3)
cache.put(1, "one")
cache.put(2, "two")
cache.put(3, "three")
cache.display()  # [(1, 'one'), (2, 'two'), (3, 'three')]

cache.get(1)     # Access 1
cache.display()  # [(2, 'two'), (3, 'three'), (1, 'one')]

cache.put(4, "four")  # Evicts key 2
cache.display()  # [(3, 'three'), (1, 'one'), (4, 'four')]
      Python

      Common Problems

      1. Implement Queue Using Stacks

      class QueueUsingStacks:
    """Implement queue using two stacks"""

    def __init__(self):
        self.stack1 = []  # For enqueue
        self.stack2 = []  # For dequeue

    def enqueue(self, item):
        """Push to stack1 - O(1)"""
        self.stack1.append(item)

    def dequeue(self):
        """
        Pop from stack2
        If stack2 is empty, transfer all from stack1 to stack2
        Amortized O(1)
        """
        if not self.stack2:
            if not self.stack1:
                raise IndexError("Queue is empty")
            # Transfer all elements from stack1 to stack2
            while self.stack1:
                self.stack2.append(self.stack1.pop())

        return self.stack2.pop()

    def peek(self):
        """View front element"""
        if not self.stack2:
            if not self.stack1:
                raise IndexError("Queue is empty")
            while self.stack1:
                self.stack2.append(self.stack1.pop())

        return self.stack2[-1]

    def is_empty(self):
        return not self.stack1 and not self.stack2


# Test
queue = QueueUsingStacks()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue())  # 1
print(queue.peek())     # 2
queue.enqueue(4)
print(queue.dequeue())  # 2
print(queue.dequeue())  # 3
      Python

      2. Implement Stack Using Queues

      from collections import deque

class StackUsingQueue:
    """Implement stack using single queue"""

    def __init__(self):
        self.queue = deque()

    def push(self, item):
        """
        Push item and rotate queue
        Makes newest element the front - O(n)
        """
        self.queue.append(item)
        # Rotate queue so new element is at front
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())

    def pop(self):
        """Pop from front - O(1)"""
        if not self.queue:
            raise IndexError("Stack is empty")
        return self.queue.popleft()

    def top(self):
        """View top element"""
        if not self.queue:
            raise IndexError("Stack is empty")
        return self.queue[0]

    def is_empty(self):
        return len(self.queue) == 0


# Test
stack = StackUsingQueue()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # 3 (LIFO)
print(stack.top())  # 2
      Python

      3. Generate Binary Numbers from 1 to N

      from collections import deque

def generate_binary_numbers(n):
    """
    Generate binary numbers from 1 to n using queue

    Example: n=5 → ['1', '10', '11', '100', '101']
    """
    result = []
    queue = deque(['1'])

    for _ in range(n):
        # Remove front and add to result
        binary = queue.popleft()
        result.append(binary)

        # Generate next numbers by appending 0 and 1
        queue.append(binary + '0')
        queue.append(binary + '1')

    return result


# Test
n = 10
binary_numbers = generate_binary_numbers(n)
print(f"Binary numbers from 1 to {n}:")
for i, binary in enumerate(binary_numbers, 1):
    print(f"{i:2} = {binary}")
      Python

      4. First Non-Repeating Character in Stream

      from collections import deque, Counter

def first_non_repeating_character(stream):
    """
    Find first non-repeating character in stream

    Example: "aabcc" → ['a', -1, 'b', 'b', -1]
    """
    queue = deque()
    freq = Counter()
    result = []

    for char in stream:
        freq[char] += 1
        queue.append(char)

        # Remove characters with freq > 1 from front
        while queue and freq[queue[0]] > 1:
            queue.popleft()

        # First element in queue is first non-repeating
        if queue:
            result.append(queue[0])
        else:
            result.append(-1)

    return result


# Test
stream = "aabccxb"
result = first_non_repeating_character(stream)
print(f"Stream: {stream}")
print(f"Result: {result}")
      Python

      5. Sliding Window Maximum

      from collections import deque

def sliding_window_maximum(nums, k):
    """
    Find maximum in each sliding window of size k

    Example: nums=[1,3,-1,-3,5,3,6,7], k=3
             → [3, 3, 5, 5, 6, 7]
    """
    if not nums or k == 0:
        return []

    deq = deque()  # Store indices
    result = []

    for i in range(len(nums)):
        # Remove indices outside window
        if deq and deq[0] < i - k + 1:
            deq.popleft()

        # Remove smaller elements from rear
        while deq and nums[deq[-1]] < nums[i]:
            deq.pop()

        deq.append(i)

        # Add to result once window is full
        if i >= k - 1:
            result.append(nums[deq[0]])

    return result


# Test
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
result = sliding_window_maximum(nums, k)
print(f"Array: {nums}")
print(f"Window size: {k}")
print(f"Maximums: {result}")
      Python

      6. Rotten Oranges (LeetCode #994)

      from collections import deque

def oranges_rotting(grid):
    """
    Find minimum time for all oranges to rot
    0 = empty, 1 = fresh orange, 2 = rotten orange

    Example: [[2,1,1],[1,1,0],[0,1,1]] → 4
    """
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh_count = 0

    # Find all rotten oranges and count fresh ones
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))  # (row, col, time)
            elif grid[r][c] == 1:
                fresh_count += 1

    # BFS from all rotten oranges
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    max_time = 0

    while queue:
        row, col, time = queue.popleft()
        max_time = max(max_time, time)

        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc

            if (0 <= new_row < rows and 
                0 <= new_col < cols and 
                grid[new_row][new_col] == 1):

                grid[new_row][new_col] = 2
                fresh_count -= 1
                queue.append((new_row, new_col, time + 1))

    return max_time if fresh_count == 0 else -1


# Test
grid = [
    [2, 1, 1],
    [1, 1, 0],
    [0, 1, 1]
]
print(f"Minimum time: {oranges_rotting(grid)} minutes")
      Python

      7. Perfect Squares (LeetCode #279)

      from collections import deque

def num_squares(n):
    """
    Find minimum number of perfect squares that sum to n
    Using BFS (shortest path problem)

    Example: n=12 → 3 (4 + 4 + 4)
    """
    if n <= 0:
        return 0

    # Generate perfect squares up to n
    squares = []
    i = 1
    while i * i <= n:
        squares.append(i * i)
        i += 1

    # BFS
    queue = deque([(n, 0)])  # (remaining, steps)
    visited = {n}

    while queue:
        remaining, steps = queue.popleft()

        for square in squares:
            next_remaining = remaining - square

            if next_remaining == 0:
                return steps + 1

            if next_remaining > 0 and next_remaining not in visited:
                visited.add(next_remaining)
                queue.append((next_remaining, steps + 1))

    return -1


# Test
for n in [12, 13, 7]:
    print(f"n={n} → {num_squares(n)} perfect squares")
      Python

      Advanced Topics

      1. Circular Tour (Petrol Pump Problem)

      from collections import deque

def circular_tour(petrol, distance):
    """
    Find starting point for circular tour

    petrol[i] = petrol at pump i
    distance[i] = distance to next pump

    Returns index of starting pump, or -1 if impossible
    """
    n = len(petrol)
    total_petrol = sum(petrol)
    total_distance = sum(distance)

    # If total petrol < total distance, tour impossible
    if total_petrol < total_distance:
        return -1

    current_petrol = 0
    start = 0

    for i in range(n):
        current_petrol += petrol[i] - distance[i]

        # If we can't reach next pump, start from next pump
        if current_petrol < 0:
            start = i + 1
            current_petrol = 0

    return start


# Test
petrol = [4, 6, 7, 4]
distance = [6, 5, 3, 5]
start = circular_tour(petrol, distance)
print(f"Start from pump: {start}")
      Python

      2. Interleave First and Second Half of Queue

      from collections import deque

def interleave_queue(queue):
    """
    Interleave first and second half of queue

    Example: [1,2,3,4,5,6] → [1,4,2,5,3,6]
    """
    if len(queue) % 2 != 0:
        raise ValueError("Queue must have even length")

    n = len(queue)
    half = n // 2

    # Transfer first half to temporary queue
    temp = deque()
    for _ in range(half):
        temp.append(queue.popleft())

    # Interleave
    while temp:
        queue.append(temp.popleft())
        queue.append(queue.popleft())

    return queue


# Test
queue = deque([1, 2, 3, 4, 5, 6, 7, 8])
print(f"Original: {list(queue)}")
result = interleave_queue(queue)
print(f"Interleaved: {list(result)}")
      Python

      3. Reverse First K Elements of Queue

      from collections import deque

def reverse_first_k(queue, k):
    """
    Reverse first k elements of queue

    Example: queue=[1,2,3,4,5], k=3 → [3,2,1,4,5]
    """
    if k <= 0 or k > len(queue):
        return queue

    stack = []

    # Push first k elements to stack
    for _ in range(k):
        stack.append(queue.popleft())

    # Pop from stack and enqueue (reverses order)
    while stack:
        queue.append(stack.pop())

    # Move remaining elements to back
    for _ in range(len(queue) - k):
        queue.append(queue.popleft())

    return queue


# Test
queue = deque([1, 2, 3, 4, 5])
k = 3
print(f"Original: {list(queue)}")
result = reverse_first_k(queue, k)
print(f"After reversing first {k}: {list(result)}")
      Python

      4. Design Circular Deque (LeetCode #641)

      class MyCircularDeque:
    """Design circular double-ended queue"""

    def __init__(self, k):
        self.capacity = k
        self.deque = [0] * k
        self.front = 0
        self.rear = 0
        self.size = 0

    def insertFront(self, value):
        if self.isFull():
            return False
        self.front = (self.front - 1) % self.capacity
        self.deque[self.front] = value
        self.size += 1
        return True

    def insertLast(self, value):
        if self.isFull():
            return False
        self.deque[self.rear] = value
        self.rear = (self.rear + 1) % self.capacity
        self.size += 1
        return True

    def deleteFront(self):
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return True

    def deleteLast(self):
        if self.isEmpty():
            return False
        self.rear = (self.rear - 1) % self.capacity
        self.size -= 1
        return True

    def getFront(self):
        return -1 if self.isEmpty() else self.deque[self.front]

    def getRear(self):
        return -1 if self.isEmpty() else self.deque[(self.rear - 1) % self.capacity]

    def isEmpty(self):
        return self.size == 0

    def isFull(self):
        return self.size == self.capacity


# Test
deque = MyCircularDeque(3)
print(deque.insertLast(1))   # True
print(deque.insertLast(2))   # True
print(deque.insertFront(3))  # True
print(deque.insertFront(4))  # False (full)
print(deque.getRear())       # 2
print(deque.isFull())        # True
      Python

      5. Design Hit Counter (LeetCode #362)

      from collections import deque

class HitCounter:
    """Count hits in past 5 minutes (300 seconds)"""

    def __init__(self):
        self.hits = deque()

    def hit(self, timestamp):
        """Record a hit at given timestamp"""
        self.hits.append(timestamp)

    def getHits(self, timestamp):
        """Get number of hits in past 300 seconds"""
        # Remove hits older than 300 seconds
        while self.hits and self.hits[0] <= timestamp - 300:
            self.hits.popleft()

        return len(self.hits)


# Test
counter = HitCounter()
counter.hit(1)
counter.hit(2)
counter.hit(3)
print(counter.getHits(4))    # 3
counter.hit(300)
print(counter.getHits(300))  # 4
print(counter.getHits(301))  # 3 (hit at timestamp 1 is now > 300 seconds old)
      Python

      6. Moving Average from Data Stream (LeetCode #346)

      from collections import deque

class MovingAverage:
    """Calculate moving average of last n values"""

    def __init__(self, size):
        self.size = size
        self.queue = deque()
        self.total = 0

    def next(self, val):
        """Add value and return current average"""
        self.queue.append(val)
        self.total += val

        # Remove oldest value if over capacity
        if len(self.queue) > self.size:
            removed = self.queue.popleft()
            self.total -= removed

        return self.total / len(self.queue)


# Test
ma = MovingAverage(3)
print(ma.next(1))   # 1.0
print(ma.next(10))  # 5.5
print(ma.next(3))   # 4.666...
print(ma.next(5))   # 6.0 (average of 10, 3, 5)
      Python

      7. Shortest Path in Binary Matrix (LeetCode #1091)

      from collections import deque

def shortest_path_binary_matrix(grid):
    """
    Find shortest path from top-left to bottom-right
    Can move in 8 directions, only through 0s

    Returns path length, or -1 if no path exists
    """
    n = len(grid)

    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1

    # 8 directions
    directions = [
        (-1, -1), (-1, 0), (-1, 1),
        (0, -1),           (0, 1),
        (1, -1),  (1, 0),  (1, 1)
    ]

    queue = deque([(0, 0, 1)])  # (row, col, distance)
    grid[0][0] = 1  # Mark as visited

    while queue:
        row, col, dist = queue.popleft()

        if row == n - 1 and col == n - 1:
            return dist

        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc

            if (0 <= new_row < n and 
                0 <= new_col < n and 
                grid[new_row][new_col] == 0):

                grid[new_row][new_col] = 1  # Mark visited
                queue.append((new_row, new_col, dist + 1))

    return -1


# Test
grid = [
    [0, 0, 0],
    [1, 1, 0],
    [1, 1, 0]
]
print(f"Shortest path length: {shortest_path_binary_matrix(grid)}")
      Python

      Queue Interview Questions Checklist

      Easy Level

      • ✓ Implement queue using array/list
      • ✓ Implement queue using linked list
      • ✓ Implement queue using stacks
      • ✓ Implement stack using queues
      • ✓ Reverse a queue
      • ✓ Generate binary numbers

      Medium Level

      • ✓ BFS graph traversal
      • ✓ Level order tree traversal
      • ✓ First non-repeating character
      • ✓ Sliding window maximum
      • ✓ Circular queue implementation
      • ✓ Interleave queue
      • ✓ Reverse first K elements
      • ✓ Rotten oranges

      Hard Level

      • ✓ Shortest path in binary matrix
      • ✓ Perfect squares (BFS)
      • ✓ Design circular deque
      • ✓ Petrol pump (circular tour)
      • ✓ LRU Cache
      • ✓ Moving average

      Best Practices

      1. When to Use Queue

      • BFS algorithms (graphs, trees)
      • Order processing (FIFO required)
      • Buffering (IO operations, streaming)
      • Scheduling (process, task, job queues)
      • Request handling (web servers, APIs)
      • Rate limiting (sliding window)

      2. Choosing the Right Implementation

      # ✓ Use deque for general-purpose queues (RECOMMENDED)
from collections import deque
queue = deque()

# ✓ Use queue.Queue for thread-safe operations
from queue import Queue
queue = Queue()

# ✓ Use heapq for priority queues
import heapq
pq = []  # Use with heapq functions

# ✓ Use list only for small queues or learning
queue = []  # Avoid for production (O(n) dequeue)
      Python

      3. Common Pitfalls

      # ❌ Using list.pop(0) - O(n) operation
queue = [1, 2, 3]
queue.pop(0)  # Slow for large queues

# ✓ Use deque.popleft() - O(1) operation
from collections import deque
queue = deque([1, 2, 3])
queue.popleft()  # Fast

# ❌ Forgetting to check if queue is empty
queue.popleft()  # May raise IndexError

# ✓ Always check before dequeue
if queue:
    queue.popleft()
      Python

      4. Memory Management

      # For bounded queues, use maxlen
from collections import deque

# ✓ Automatically removes oldest when full
bounded_queue = deque(maxlen=100)

# ✓ Or use queue.Queue with maxsize
from queue import Queue
bounded_queue = Queue(maxsize=100)
      Python

      5. Type Hints and Documentation

      from typing import Generic, TypeVar, Optional
from collections import deque

T = TypeVar('T')

class Queue(Generic[T]):
    """
    A FIFO (First-In-First-Out) queue implementation.

    Type Parameters:
        T: The type of elements in the queue

    Attributes:
        _items: Deque storing queue elements
    """

    def __init__(self) -> None:
        self._items: deque[T] = deque()

    def enqueue(self, item: T) -> None:
        """Add item to rear of queue."""
        self._items.append(item)

    def dequeue(self) -> T:
        """Remove and return front item."""
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()

    def front(self) -> Optional[T]:
        """Return front item without removing."""
        return self._items[0] if self._items else None

    def is_empty(self) -> bool:
        """Check if queue is empty."""
        return len(self._items) == 0

    def size(self) -> int:
        """Return number of items in queue."""
        return len(self._items)
      Python

      Summary

      Key Takeaways

      1. FIFO Principle: First element in is first element out
      2. O(1) Operations: Enqueue and dequeue should be constant time
      3. Use deque: Python’s collections.deque is the best general-purpose queue
      4. Many Variants: Circular, priority, double-ended queues
      5. BFS Applications: Queue is fundamental for breadth-first algorithms
      6. Real-World Uses: Task scheduling, request handling, buffering

      Quick Reference

      # Recommended: Use deque
from collections import deque

# Create queue
queue = deque()

# Basic operations
queue.append(item)        # Enqueue - O(1)
item = queue.popleft()    # Dequeue - O(1)
item = queue[0]           # Front - O(1)
item = queue[-1]          # Rear - O(1)
is_empty = len(queue) == 0
size = len(queue)

# Bounded queue
queue = deque(maxlen=10)

# Thread-safe queue
from queue import Queue
queue = Queue(maxsize=10)
queue.put(item)
item = queue.get()
      Python

      Performance Comparison

      ImplementationEnqueueDequeueBest Use Case
      dequeO(1)O(1)General purpose
      listO(1)O(n)Learning only
      queue.QueueO(1)O(1)Multi-threading
      Linked ListO(1)O(1)Memory efficiency
      Circular ArrayO(1)O(1)Fixed size

      Further Reading

      • Graph Algorithms (BFS, Dijkstra)
      • Operating System Scheduling
      • Message Queues (RabbitMQ, Kafka)
      • Concurrent Programming
      • Stream Processing

      Practice Resources:

      • LeetCode Queue Problems
      • HackerRank Queue Challenges
      • GeeksforGeeks Queue Articles
      • Project Euler Problems

      Happy Coding! 🚀

      Discover more from Altgr Blog

      Subscribe to get the latest posts sent to your email.

      Related Posts

      Leave a Reply

      Your email address will not be published. Required fields are marked *