DSA Interview Prep · Lesson

Queue Implementation and Deque

Build a queue with Python's deque, implement a circular queue, and solve sliding-window maximum using a monotonic deque.

The Queue Data Structure

A queue is a first-in, first-out (FIFO) data structure. The first element enqueued is the first element dequeued — like a checkout line at a store. Core operations are enqueue (add to rear) and dequeue (remove from front). Both must be O(1) for the queue to be efficient.

Using a Python list as a queue is tempting but wrong: list.pop(0) is O(n) because it shifts all elements. The correct tool is collections.deque, which provides O(1) appendleft, append, popleft, and pop.

from collections import deque

queue = deque()

# Enqueue (add to rear)
queue.append(10)
queue.append(20)
queue.append(30)
print('Queue:', queue)          # deque([10, 20, 30])

# Peek front
print('Front:', queue[0])       # 10

# Dequeue (remove from front)
print('Dequeued:', queue.popleft())  # 10
print('Queue after:', queue)         # deque([20, 30])

Queue Class Using deque

Wrap deque in a Queue class with named operations to match what interviewers expect. Internally enqueue calls append and dequeue calls popleft. The peek operation reads queue[0] without removing it.

from collections import deque

class Queue:
    def __init__(self):
        self._data = deque()

    def enqueue(self, val):
        self._data.append(val)

    def dequeue(self):
        if self.is_empty():
            raise IndexError('dequeue from empty queue')
        return self._data.popleft()

    def peek(self):
        if self.is_empty():
            raise IndexError('peek at empty queue')
        return self._data[0]

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

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

q = Queue()
q.enqueue(1); q.enqueue(2); q.enqueue(3)
print(q.peek())     # 1
print(q.dequeue())  # 1
print(len(q))       # 2

All lessons in this course

← Back to DSA Interview Prep