Queue Variations

Deque (Double-Ended Queue)

A deque allows insertion and deletion at both ends.

from collections import deque

dq = deque()

# Add to both ends
dq.append(1)        # Add to right
dq.appendleft(0)    # Add to left

# Remove from both ends
dq.pop()            # Remove from right
dq.popleft()        # Remove from left

# [0, 1] operations are all O(1)

Deque Implementation

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):
        return self.items.pop(0) if self.items else None

    def remove_rear(self):
        return self.items.pop() if self.items else None

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

Priority Queue

Elements are dequeued based on priority, not insertion order.

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []

    def enqueue(self, item, priority):
        # Lower priority number = higher priority
        heapq.heappush(self.heap, (priority, item))

    def dequeue(self):
        if self.heap:
            return heapq.heappop(self.heap)[1]
        return None

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

# Usage
pq = PriorityQueue()
pq.enqueue("low priority", 3)
pq.enqueue("high priority", 1)
pq.enqueue("medium priority", 2)

print(pq.dequeue())  # "high priority"
print(pq.dequeue())  # "medium priority"
print(pq.dequeue())  # "low priority"

Python's Built-in Priority Queue

from queue import PriorityQueue

pq = PriorityQueue()
pq.put((1, "high priority"))
pq.put((3, "low priority"))
pq.put((2, "medium priority"))

while not pq.empty():
    priority, item = pq.get()
    print(item)

Circular Queue

A fixed-size queue where the end connects to the beginning.

class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = 0
        self.rear = -1
        self.size = 0

    def enqueue(self, item):
        if self.is_full():
            return False

        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = item
        self.size += 1
        return True

    def dequeue(self):
        if self.is_empty():
            return None

        item = self.queue[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return item

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

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

    def peek(self):
        if self.is_empty():
            return None
        return self.queue[self.front]

# Usage
cq = CircularQueue(3)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
print(cq.dequeue())  # 1
cq.enqueue(4)  # Wraps around

Queue Using Two Stacks

An interesting implementation that amortizes to O(1):

class QueueWithStacks:
    def __init__(self):
        self.inbox = []   # For enqueue
        self.outbox = []  # For dequeue

    def enqueue(self, item):
        self.inbox.append(item)

    def dequeue(self):
        if not self.outbox:
            # Transfer all items from inbox to outbox
            while self.inbox:
                self.outbox.append(self.inbox.pop())

        return self.outbox.pop() if self.outbox else None

    def peek(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

        return self.outbox[-1] if self.outbox else None

Time Complexity Comparison

*Using deque or two-pointer implementation