Queue & Deque

First-In, First-Out and More

The Queue is a FIFO (First-In, First-Out) data structure, perfect for processing tasks in the order they were received. The Deque (Double-Ended Queue) provides even more flexibility by allowing efficient additions and removals from both ends.

1. The Queue

A Queue is a linear data structure that follows the FIFO (First-In, First-Out) principle. Think of a checkout line: the first person to get in line is the first one to be served. Queues are fundamental in algorithms like Breadth-First Search (BFS).

Queue Methods

Method	Description	Complexity
enqueue(item)	Adds an item to the rear (end) of the queue.	O(1)
dequeue()	Removes and returns the item from the front of the queue.	O(1)
front() / peek()	Returns the front item without removing it.	O(1)
isEmpty()	Returns true if the queue is empty.	O(1)

from collections import deque

# Create a queue
q = deque()

# Enqueue
q.append("a")  # q is now deque(['a'])
q.append("b")  # q is now deque(['a', 'b'])

# Peek
print(q[0])    # Prints 'a'

# Dequeue
item = q.popleft() # item is 'a', q is now deque(['b'])
print(item)

2. The Deque (Double-Ended Queue)

A Deque (pronounced "deck") is a generalization of a queue that supports adding and removing elements from either the front or the back in O(1) time. This makes it incredibly versatile for a wide range of problems.

Deque Methods

Method	Description	Complexity
push_back(item)	Adds an item to the rear (end). Same as enqueue.	O(1)
pop_front()	Removes and returns the front item. Same as dequeue.	O(1)
push_front(item)	Adds an item to the front of the deque.	O(1)
pop_back()	Removes and returns the rear item.	O(1)
front() / back()	Peek at the front or rear item.	O(1)

from collections import deque

# Create a deque
d = deque()

d.append("b")      # Add to right: deque(['b'])
d.append("c")      # Add to right: deque(['b', 'c'])
d.appendleft("a")  # Add to left:  deque(['a', 'b', 'c'])

# Remove from left
d.popleft()        # Returns 'a', d is now deque(['b', 'c'])

# Remove from right
d.pop()            # Returns 'c', d is now deque(['b'])

3. Classic Problems & Techniques

Implement Queue using Stacks

This is a classic interview question that tests your understanding of both data structures. You can use two stacks: an input stack and an output stack. To enqueue, you simply push to the input stack. To dequeue, if the output stack is empty, you pop every element from the input stack and push it to the output stack. This reverses the order, effectively creating a FIFO structure. Then you pop from the output stack. This is called amortized O(1) time complexity.

class MyQueue:
    def __init__(self):
        self.input_stack = []
        self.output_stack = []

    def push(self, x: int) -> None:
        self.input_stack.append(x)

    def pop(self) -> int:
        self.peek()
        return self.output_stack.pop()

    def peek(self) -> int:
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())
        return self.output_stack[-1]

    def empty(self) -> bool:
        return not self.input_stack and not self.output_stack

Design Circular Deque

Design your implementation of the circular double-ended queue. This problem requires careful handling of pointers and capacity constraints within a fixed-size array.

class MyCircularDeque:
    def __init__(self, k: int):
        self.deque = [0] * k
        self.capacity = k
        self.size = 0
        self.head = 0
        self.tail = -1

    def insertFront(self, value: int) -> bool:
        if self.isFull(): return False
        self.head = (self.head - 1 + self.capacity) % self.capacity
        self.deque[self.head] = value
        if self.isEmpty(): self.tail = self.head
        self.size += 1
        return True

    def insertLast(self, value: int) -> bool:
        if self.isFull(): return False
        self.tail = (self.tail + 1) % self.capacity
        self.deque[self.tail] = value
        if self.isEmpty(): self.head = self.tail
        self.size += 1
        return True

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

    def deleteLast(self) -> bool:
        if self.isEmpty(): return False
        self.tail = (self.tail - 1 + self.capacity) % self.capacity
        self.size -= 1
        return True

    def getFront(self) -> int:
        return self.deque[self.head] if not self.isEmpty() else -1

    def getRear(self) -> int:
        return self.deque[self.tail] if not self.isEmpty() else -1

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity

Technique: Monotonic Queue

A monotonic queue is a deque where the elements are always kept in a sorted order (either increasing or decreasing). This pattern is the key to solving "Sliding Window Minimum/Maximum" problems in O(n) time.

Classic Problem: Sliding Window Maximum

Given an array and a window size k, find the maximum value in each sliding window. A naive approach would be O(n*k). Using a monotonic (decreasing) deque, we can do it in O(n). As the window slides:

Before adding a new element, remove all elements from the back of the deque that are smaller than the new element. This maintains the decreasing order.
Add the new element's index to the back of the deque.
Remove indices from the front of the deque that are no longer in the current window.
The front of the deque always holds the index of the maximum element in the current window.

Monotonic Deque for Sliding Window Max (k=3)

Array: [1, 3, -1, -3, 5, 3, 6, 7]
i=0, num=1. Deque: [0]
i=1, num=3. Pop 0. Deque: [1]
i=2, num=-1. Deque: [1, 2]. Window max: nums[1]=3
i=3, num=-3. Deque: [1, 2, 3]. Window max: nums[1]=3
i=4, num=5. Pop 3, 2, 1. Deque: [4]. Window max: nums[4]=5
...

from typing import List
import collections

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        output = []
        q = collections.deque() # store indices
        l = r = 0
        
        while r < len(nums):
            # pop smaller values from q
            while q and nums[q[-1]] < nums[r]:
                q.pop()
            q.append(r)
            
            # remove left val from window
            if l > q[0]:
                q.popleft()
            
            if (r + 1) >= k:
                output.append(nums[q[0]])
                l += 1
            r += 1
        return output

Interactive Queue (FIFO) Simulation

Visualize the First-In, First-Out principle of a queue.

Queue is empty