Complete DSA Series Part 8: Queue

FAANG Interview Prep

Your 12-step learning path • Currently on Step 8

Queue

FIFO, circular queue, deque, priority queue

You Are Here

Trees

Binary trees, traversals, expression trees, threaded trees

BST & Balanced Trees

Search, insert, delete, AVL, red-black, B-trees

Heaps, Sorting & Hashing

Min/max heaps, heapsort, hash tables, collision handling

Graphs, DP, Greedy & Backtracking

BFS, DFS, shortest paths, dynamic programming, optimization

Introduction to Queue

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. Think of it like a line at a ticket counter - the first person to join the line is the first to be served. Queues are fundamental in computer science, used in process scheduling, BFS traversal, print spooling, and handling asynchronous data transfer.

Queue FIFO data structure showing enqueue at rear and dequeue at front — Queue FIFO principle — elements are added at the rear (enqueue) and removed from the front (dequeue)

Mental Model: The Queue

Problem it solves: Process items in the exact order they arrive — fairness, buffering, level-order traversal. FIFO guarantees the item waiting longest is served next.

When NOT to use: When priority matters (use min/max heap), when newest-first is needed (use stack), or when random access is required (use array or hash map).

Common misconception: "A Python list works fine as a queue." list.pop(0) is \(O(n)\) — it shifts all remaining elements. Use collections.deque for \(O(1)\) popleft. This mistake silently turns an \(O(n)\) BFS into \(O(n^{2})\).

Interview lens: BFS always uses a queue. Multi-source BFS (fire spreading, shortest distance from multiple starts simultaneously) is a queue problem many people miss. Monotonic deque enables sliding window maximum in \(O(n)\).

Production lens: Every message broker (RabbitMQ, AWS SQS, Kafka) is a distributed persistent queue. Thread pool executors hold task queues. Rate limiters use token bucket queues. Queue semantics are foundational to distributed systems design.

Queue Operations

Core Queue Operations

Operation	Description	Time
enqueue(item)	Add item to rear	\(O(1)\)
dequeue()	Remove and return front item	\(O(1)\)*
front()/peek()	Return front item without removing	\(O(1)\)
isEmpty()	Check if queue is empty	\(O(1)\)
size()	Return number of items	\(O(1)\)

* \(O(n)\) for simple array implementation due to shifting; \(O(1)\) for circular/linked list

Queue Implementations

Array-Based Queue (Simple)

The naive array-based queue stores elements in a list with front and rear indices. Enqueue appends at the rear (\(O(1)\)), but dequeue from the front requires shifting all remaining elements (\(O(n)\)). This is why simple arrays are a poor choice for queues — the circular queue (next section) fixes this by reusing vacated front space without shifting.

# Simple Queue Implementation using Python List
# dequeue is O(n) due to list shifting - not efficient!

class SimpleQueue:
    def __init__(self):
        """Initialize empty queue"""
        self.items = []
    
    def enqueue(self, item):
        """Add item to rear - O(1) amortized"""
        self.items.append(item)
    
    def dequeue(self):
        """Remove and return front item - O(n) due to shifting"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.items.pop(0)  # This is O(n)!
    
    def front(self):
        """Return front item without removing - O(1)"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.items[0]
    
    def is_empty(self):
        """Check if queue is empty - O(1)"""
        return len(self.items) == 0
    
    def size(self):
        """Return number of items - O(1)"""
        return len(self.items)
    
    def __str__(self):
        return f"Queue(front -> {self.items})"

# Test Simple Queue
queue = SimpleQueue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(f"Queue: {queue}")           # Queue(front -> [1, 2, 3])
print(f"Front: {queue.front()}")   # 1
print(f"Dequeue: {queue.dequeue()}")  # 1
print(f"Queue: {queue}")           # Queue(front -> [2, 3])

// Simple Queue using std::vector
// dequeue is O(n) due to shifting - not efficient for large queues
#include <iostream>
#include <vector>
#include <stdexcept>

template <typename T>
class SimpleQueue {
private:
    std::vector<T> items;

public:
    void enqueue(const T& item) {
        items.push_back(item);  // O(1) amortized
    }
    
    T dequeue() {
        if (isEmpty()) {
            throw std::out_of_range("Queue is empty");
        }
        T front = items.front();
        items.erase(items.begin());  // O(n) - shifts all elements
        return front;
    }
    
    T front() const {
        if (isEmpty()) {
            throw std::out_of_range("Queue is empty");
        }
        return items.front();
    }
    
    bool isEmpty() const { return items.empty(); }
    
    size_t size() const { return items.size(); }
    
    void display() const {
        std::cout << "Queue(front -> ";
        for (const auto& item : items) {
            std::cout << item << " ";
        }
        std::cout << ")" << std::endl;
    }
};

// Usage
int main() {
    SimpleQueue<int> queue;
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    queue.display();  // Queue(front -> 1 2 3 )
    
    std::cout << "Front: " << queue.front() << std::endl;  // 1
    std::cout << "Dequeue: " << queue.dequeue() << std::endl;  // 1
    queue.display();  // Queue(front -> 2 3 )
    return 0;
}

// Simple Queue using ArrayList
// dequeue is O(n) due to shifting - not efficient for large queues
import java.util.ArrayList;
import java.util.NoSuchElementException;

public class SimpleQueue<T> {
    private ArrayList<T> items;
    
    public SimpleQueue() {
        items = new ArrayList<>();
    }
    
    public void enqueue(T item) {
        items.add(item);  // O(1) amortized
    }
    
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return items.remove(0);  // O(n) - shifts all elements
    }
    
    public T front() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return items.get(0);
    }
    
    public boolean isEmpty() {
        return items.isEmpty();
    }
    
    public int size() {
        return items.size();
    }
    
    @Override
    public String toString() {
        return "Queue(front -> " + items + ")";
    }
    
    public static void main(String[] args) {
        SimpleQueue<Integer> queue = new SimpleQueue<>();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        System.out.println(queue);  // Queue(front -> [1, 2, 3])
        
        System.out.println("Front: " + queue.front());  // 1
        System.out.println("Dequeue: " + queue.dequeue());  // 1
        System.out.println(queue);  // Queue(front -> [2, 3])
    }
}

Linked List-Based Queue

A linked-list queue uses a front pointer for dequeue and a rear pointer for enqueue — giving true \(O(1)\) for both operations with no wasted space and no capacity limit. Enqueue creates a new node at rear; dequeue removes the node at front. This is the standard production implementation when you need an unbounded queue with guaranteed constant-time operations (used internally by Python's collections.deque).

# Queue Implementation using Linked List
# All operations O(1)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedListQueue:
    def __init__(self):
        """Initialize empty queue with front and rear pointers"""
        self.front_node = None
        self.rear_node = None
        self._size = 0
    
    def enqueue(self, item):
        """Add item to rear - O(1)"""
        new_node = Node(item)
        
        if self.is_empty():
            self.front_node = new_node
            self.rear_node = new_node
        else:
            self.rear_node.next = new_node
            self.rear_node = 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_node.data
        self.front_node = self.front_node.next
        self._size -= 1
        
        # If queue becomes empty, reset rear
        if self.front_node is None:
            self.rear_node = None
        
        return item
    
    def front(self):
        """Return front item without removing - O(1)"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.front_node.data
    
    def rear(self):
        """Return rear item without removing - O(1)"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.rear_node.data
    
    def is_empty(self):
        return self.front_node is None
    
    def size(self):
        return self._size
    
    def display(self):
        elements = []
        current = self.front_node
        while current:
            elements.append(str(current.data))
            current = current.next
        print("Queue (front -> rear):", " -> ".join(elements))

# Test Linked List Queue
ll_queue = LinkedListQueue()
ll_queue.enqueue(1)
ll_queue.enqueue(2)
ll_queue.enqueue(3)
ll_queue.display()  # Queue (front -> rear): 1 -> 2 -> 3

print(f"Front: {ll_queue.front()}")  # 1
print(f"Rear: {ll_queue.rear()}")    # 3
print(f"Dequeue: {ll_queue.dequeue()}")  # 1
ll_queue.display()  # Queue (front -> rear): 2 -> 3

// Queue Implementation using Linked List
// All operations O(1)
#include <iostream>
#include <stdexcept>

template <typename T>
class LinkedListQueue {
private:
    struct Node {
        T data;
        Node* next;
        Node(const T& d) : data(d), next(nullptr) {}
    };
    
    Node* frontNode;
    Node* rearNode;
    size_t _size;

public:
    LinkedListQueue() : frontNode(nullptr), rearNode(nullptr), _size(0) {}
    
    ~LinkedListQueue() {
        while (frontNode) {
            Node* temp = frontNode;
            frontNode = frontNode->next;
            delete temp;
        }
    }
    
    void enqueue(const T& item) {
        Node* newNode = new Node(item);
        
        if (isEmpty()) {
            frontNode = rearNode = newNode;
        } else {
            rearNode->next = newNode;
            rearNode = newNode;
        }
        _size++;
    }
    
    T dequeue() {
        if (isEmpty()) {
            throw std::out_of_range("Queue is empty");
        }
        
        Node* temp = frontNode;
        T item = temp->data;
        frontNode = frontNode->next;
        delete temp;
        _size--;
        
        if (frontNode == nullptr) {
            rearNode = nullptr;
        }
        return item;
    }
    
    T front() const {
        if (isEmpty()) throw std::out_of_range("Queue is empty");
        return frontNode->data;
    }
    
    T rear() const {
        if (isEmpty()) throw std::out_of_range("Queue is empty");
        return rearNode->data;
    }
    
    bool isEmpty() const { return frontNode == nullptr; }
    
    size_t size() const { return _size; }
    
    void display() const {
        std::cout << "Queue (front -> rear): ";
        Node* current = frontNode;
        while (current) {
            std::cout << current->data;
            if (current->next) std::cout << " -> ";
            current = current->next;
        }
        std::cout << std::endl;
    }
};

// Usage
int main() {
    LinkedListQueue<int> queue;
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    queue.display();  // Queue (front -> rear): 1 -> 2 -> 3
    
    std::cout << "Front: " << queue.front() << std::endl;  // 1
    std::cout << "Rear: " << queue.rear() << std::endl;    // 3
    std::cout << "Dequeue: " << queue.dequeue() << std::endl;  // 1
    queue.display();  // Queue (front -> rear): 2 -> 3
    return 0;
}

// Queue Implementation using Linked List
// All operations O(1)

public class LinkedListQueue<T> {
    private class Node {
        T data;
        Node next;
        Node(T data) { this.data = data; }
    }
    
    private Node frontNode;
    private Node rearNode;
    private int size;
    
    public LinkedListQueue() {
        frontNode = null;
        rearNode = null;
        size = 0;
    }
    
    public void enqueue(T item) {
        Node newNode = new Node(item);
        
        if (isEmpty()) {
            frontNode = rearNode = newNode;
        } else {
            rearNode.next = newNode;
            rearNode = newNode;
        }
        size++;
    }
    
    public T dequeue() {
        if (isEmpty()) {
            throw new java.util.NoSuchElementException("Queue is empty");
        }
        
        T item = frontNode.data;
        frontNode = frontNode.next;
        size--;
        
        if (frontNode == null) {
            rearNode = null;
        }
        return item;
    }
    
    public T front() {
        if (isEmpty()) throw new java.util.NoSuchElementException("Queue is empty");
        return frontNode.data;
    }
    
    public T rear() {
        if (isEmpty()) throw new java.util.NoSuchElementException("Queue is empty");
        return rearNode.data;
    }
    
    public boolean isEmpty() { return frontNode == null; }
    
    public int size() { return size; }
    
    public void display() {
        StringBuilder sb = new StringBuilder("Queue (front -> rear): ");
        Node current = frontNode;
        while (current != null) {
            sb.append(current.data);
            if (current.next != null) sb.append(" -> ");
            current = current.next;
        }
        System.out.println(sb);
    }
    
    public static void main(String[] args) {
        LinkedListQueue<Integer> queue = new LinkedListQueue<>();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        queue.display();  // Queue (front -> rear): 1 -> 2 -> 3
        
        System.out.println("Front: " + queue.front());  // 1
        System.out.println("Rear: " + queue.rear());    // 3
        System.out.println("Dequeue: " + queue.dequeue());  // 1
        queue.display();  // Queue (front -> rear): 2 -> 3
    }
}

Circular Queue

A circular queue (ring buffer) uses a fixed-size array where the rear wraps around to the front, making efficient use of space. Both enqueue and dequeue are \(O(1)\).

Circular Queue: Wrap-Around Logic

                            flowchart TD
                                E(["enqueue(x)"]) --> EC{"size == capacity?"}
                                EC -->|"Yes"| EF["QueueFull Error"]
                                EC -->|"No"| EG["rear = (rear + 1) % capacity\narr[rear] = x\nsize += 1"]
                                D(["dequeue()"]) --> DC{"size == 0?"}
                                DC -->|"Yes"| DF["QueueEmpty Error"]
                                DC -->|"No"| DG["val = arr[front]\nfront = (front + 1) % capacity\nsize -= 1\nreturn val"]
                                EG --> DONE1["O(1) ✓"]
                                DG --> DONE2["O(1) ✓"]

# Circular Queue Implementation
# Fixed-size, efficient O(1) operations

class CircularQueue:
    def __init__(self, capacity):
        """Initialize circular queue with fixed capacity"""
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front_idx = 0
        self.rear_idx = -1
        self._size = 0
    
    def enqueue(self, item):
        """Add item to rear - O(1)"""
        if self.is_full():
            raise OverflowError("Queue is full")
        
        # Move rear circularly
        self.rear_idx = (self.rear_idx + 1) % self.capacity
        self.queue[self.rear_idx] = item
        self._size += 1
    
    def dequeue(self):
        """Remove and return front item - O(1)"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        
        item = self.queue[self.front_idx]
        self.queue[self.front_idx] = None  # Optional: help GC
        
        # Move front circularly
        self.front_idx = (self.front_idx + 1) % self.capacity
        self._size -= 1
        
        return item
    
    def front(self):
        """Return front item - O(1)"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.queue[self.front_idx]
    
    def rear(self):
        """Return rear item - O(1)"""
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.queue[self.rear_idx]
    
    def is_empty(self):
        return self._size == 0
    
    def is_full(self):
        return self._size == self.capacity
    
    def size(self):
        return self._size
    
    def display(self):
        if self.is_empty():
            print("Queue is empty")
            return
        
        elements = []
        i = self.front_idx
        for _ in range(self._size):
            elements.append(str(self.queue[i]))
            i = (i + 1) % self.capacity
        print("Circular Queue:", " -> ".join(elements))
        print(f"Array state: {self.queue}")

# Test Circular Queue
cq = CircularQueue(5)
for i in range(1, 6):
    cq.enqueue(i * 10)
    
cq.display()  # 10 -> 20 -> 30 -> 40 -> 50

# Dequeue some elements
print(f"Dequeue: {cq.dequeue()}")  # 10
print(f"Dequeue: {cq.dequeue()}")  # 20

# Enqueue wraps around
cq.enqueue(60)
cq.enqueue(70)
cq.display()  # Shows wraparound

// Circular Queue Implementation
// Fixed-size, efficient O(1) operations
#include <iostream>
#include <vector>
#include <stdexcept>

template <typename T>
class CircularQueue {
private:
    std::vector<T> queue;
    int capacity;
    int frontIdx;
    int rearIdx;
    int _size;

public:
    CircularQueue(int cap) : capacity(cap), frontIdx(0), rearIdx(-1), _size(0) {
        queue.resize(capacity);
    }
    
    void enqueue(const T& item) {
        if (isFull()) {
            throw std::overflow_error("Queue is full");
        }
        rearIdx = (rearIdx + 1) % capacity;
        queue[rearIdx] = item;
        _size++;
    }
    
    T dequeue() {
        if (isEmpty()) {
            throw std::out_of_range("Queue is empty");
        }
        T item = queue[frontIdx];
        frontIdx = (frontIdx + 1) % capacity;
        _size--;
        return item;
    }
    
    T front() const {
        if (isEmpty()) throw std::out_of_range("Queue is empty");
        return queue[frontIdx];
    }
    
    T rear() const {
        if (isEmpty()) throw std::out_of_range("Queue is empty");
        return queue[rearIdx];
    }
    
    bool isEmpty() const { return _size == 0; }
    
    bool isFull() const { return _size == capacity; }
    
    int size() const { return _size; }
    
    void display() const {
        if (isEmpty()) {
            std::cout << "Queue is empty" << std::endl;
            return;
        }
        std::cout << "Circular Queue: ";
        int i = frontIdx;
        for (int count = 0; count < _size; count++) {
            std::cout << queue[i];
            if (count < _size - 1) std::cout << " -> ";
            i = (i + 1) % capacity;
        }
        std::cout << std::endl;
    }
};

int main() {
    CircularQueue<int> cq(5);
    for (int i = 1; i <= 5; i++) cq.enqueue(i * 10);
    cq.display();  // 10 -> 20 -> 30 -> 40 -> 50
    
    std::cout << "Dequeue: " << cq.dequeue() << std::endl;  // 10
    std::cout << "Dequeue: " << cq.dequeue() << std::endl;  // 20
    
    cq.enqueue(60);
    cq.enqueue(70);
    cq.display();  // Shows wraparound
    return 0;
}

// Circular Queue Implementation
// Fixed-size, efficient O(1) operations

public class CircularQueue<T> {
    private Object[] queue;
    private int capacity;
    private int frontIdx;
    private int rearIdx;
    private int size;
    
    public CircularQueue(int capacity) {
        this.capacity = capacity;
        queue = new Object[capacity];
        frontIdx = 0;
        rearIdx = -1;
        size = 0;
    }
    
    public void enqueue(T item) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        rearIdx = (rearIdx + 1) % capacity;
        queue[rearIdx] = item;
        size++;
    }
    
    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (isEmpty()) {
            throw new java.util.NoSuchElementException("Queue is empty");
        }
        T item = (T) queue[frontIdx];
        frontIdx = (frontIdx + 1) % capacity;
        size--;
        return item;
    }
    
    @SuppressWarnings("unchecked")
    public T front() {
        if (isEmpty()) throw new java.util.NoSuchElementException("Queue is empty");
        return (T) queue[frontIdx];
    }
    
    @SuppressWarnings("unchecked")
    public T rear() {
        if (isEmpty()) throw new java.util.NoSuchElementException("Queue is empty");
        return (T) queue[rearIdx];
    }
    
    public boolean isEmpty() { return size == 0; }
    
    public boolean isFull() { return size == capacity; }
    
    public int size() { return size; }
    
    public void display() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return;
        }
        StringBuilder sb = new StringBuilder("Circular Queue: ");
        int i = frontIdx;
        for (int count = 0; count < size; count++) {
            sb.append(queue[i]);
            if (count < size - 1) sb.append(" -> ");
            i = (i + 1) % capacity;
        }
        System.out.println(sb);
    }
    
    public static void main(String[] args) {
        CircularQueue<Integer> cq = new CircularQueue<>(5);
        for (int i = 1; i <= 5; i++) cq.enqueue(i * 10);
        cq.display();  // 10 -> 20 -> 30 -> 40 -> 50
        
        System.out.println("Dequeue: " + cq.dequeue());  // 10
        System.out.println("Dequeue: " + cq.dequeue());  // 20
        
        cq.enqueue(60);
        cq.enqueue(70);
        cq.display();  // Shows wraparound
    }
}

Deque (Double-Ended Queue)

A deque allows insertion and deletion at both ends, combining the capabilities of both stack and queue. Python's collections.deque is implemented as a doubly-linked list of fixed-size blocks, giving \(O(1)\) operations at both ends with good cache performance. Use a deque when you need both FIFO queue behavior AND the ability to push/pop from the front — for example, the "sliding window maximum" pattern or implementing a work-stealing scheduler.

Double-ended queue showing insertion and deletion at both front and rear ends — Deque (double-ended queue) — supports insertion and deletion at both ends in \(O(1)\) time

# Deque Implementation using Doubly Linked List
# All operations O(1)

class DequeNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class Deque:
    def __init__(self):
        """Initialize empty deque"""
        self.front_node = None
        self.rear_node = None
        self._size = 0
    
    def add_front(self, item):
        """Add item to front - O(1)"""
        new_node = DequeNode(item)
        
        if self.is_empty():
            self.front_node = new_node
            self.rear_node = new_node
        else:
            new_node.next = self.front_node
            self.front_node.prev = new_node
            self.front_node = new_node
        
        self._size += 1
    
    def add_rear(self, item):
        """Add item to rear - O(1)"""
        new_node = DequeNode(item)
        
        if self.is_empty():
            self.front_node = new_node
            self.rear_node = new_node
        else:
            new_node.prev = self.rear_node
            self.rear_node.next = new_node
            self.rear_node = new_node
        
        self._size += 1
    
    def remove_front(self):
        """Remove and return front item - O(1)"""
        if self.is_empty():
            raise IndexError("Deque is empty")
        
        item = self.front_node.data
        self.front_node = self.front_node.next
        
        if self.front_node:
            self.front_node.prev = None
        else:
            self.rear_node = None
        
        self._size -= 1
        return item
    
    def remove_rear(self):
        """Remove and return rear item - O(1)"""
        if self.is_empty():
            raise IndexError("Deque is empty")
        
        item = self.rear_node.data
        self.rear_node = self.rear_node.prev
        
        if self.rear_node:
            self.rear_node.next = None
        else:
            self.front_node = None
        
        self._size -= 1
        return item
    
    def peek_front(self):
        if self.is_empty():
            raise IndexError("Deque is empty")
        return self.front_node.data
    
    def peek_rear(self):
        if self.is_empty():
            raise IndexError("Deque is empty")
        return self.rear_node.data
    
    def is_empty(self):
        return self.front_node is None
    
    def size(self):
        return self._size
    
    def display(self):
        elements = []
        current = self.front_node
        while current:
            elements.append(str(current.data))
            current = current.next
        print("Deque:", " <-> ".join(elements))

# Test Deque
deque = Deque()
deque.add_rear(1)
deque.add_rear(2)
deque.add_front(0)
deque.add_rear(3)
deque.display()  # Deque: 0 <-> 1 <-> 2 <-> 3

print(f"Remove front: {deque.remove_front()}")  # 0
print(f"Remove rear: {deque.remove_rear()}")    # 3
deque.display()  # Deque: 1 <-> 2

// Deque Implementation using Doubly Linked List
// All operations O(1)
#include <iostream>
#include <stdexcept>

template <typename T>
class Deque {
private:
    struct Node {
        T data;
        Node* prev;
        Node* next;
        Node(const T& d) : data(d), prev(nullptr), next(nullptr) {}
    };
    
    Node* frontNode;
    Node* rearNode;
    size_t _size;

public:
    Deque() : frontNode(nullptr), rearNode(nullptr), _size(0) {}
    
    ~Deque() {
        while (frontNode) {
            Node* temp = frontNode;
            frontNode = frontNode->next;
            delete temp;
        }
    }
    
    void addFront(const T& item) {
        Node* newNode = new Node(item);
        if (isEmpty()) {
            frontNode = rearNode = newNode;
        } else {
            newNode->next = frontNode;
            frontNode->prev = newNode;
            frontNode = newNode;
        }
        _size++;
    }
    
    void addRear(const T& item) {
        Node* newNode = new Node(item);
        if (isEmpty()) {
            frontNode = rearNode = newNode;
        } else {
            newNode->prev = rearNode;
            rearNode->next = newNode;
            rearNode = newNode;
        }
        _size++;
    }
    
    T removeFront() {
        if (isEmpty()) throw std::out_of_range("Deque is empty");
        Node* temp = frontNode;
        T item = temp->data;
        frontNode = frontNode->next;
        if (frontNode) frontNode->prev = nullptr;
        else rearNode = nullptr;
        delete temp;
        _size--;
        return item;
    }
    
    T removeRear() {
        if (isEmpty()) throw std::out_of_range("Deque is empty");
        Node* temp = rearNode;
        T item = temp->data;
        rearNode = rearNode->prev;
        if (rearNode) rearNode->next = nullptr;
        else frontNode = nullptr;
        delete temp;
        _size--;
        return item;
    }
    
    T peekFront() const {
        if (isEmpty()) throw std::out_of_range("Deque is empty");
        return frontNode->data;
    }
    
    T peekRear() const {
        if (isEmpty()) throw std::out_of_range("Deque is empty");
        return rearNode->data;
    }
    
    bool isEmpty() const { return frontNode == nullptr; }
    size_t size() const { return _size; }
    
    void display() const {
        std::cout << "Deque: ";
        Node* current = frontNode;
        while (current) {
            std::cout << current->data;
            if (current->next) std::cout << " <-> ";
            current = current->next;
        }
        std::cout << std::endl;
    }
};

int main() {
    Deque<int> deque;
    deque.addRear(1);
    deque.addRear(2);
    deque.addFront(0);
    deque.addRear(3);
    deque.display();  // Deque: 0 <-> 1 <-> 2 <-> 3
    
    std::cout << "Remove front: " << deque.removeFront() << std::endl;  // 0
    std::cout << "Remove rear: " << deque.removeRear() << std::endl;    // 3
    deque.display();  // Deque: 1 <-> 2
    return 0;
}

// Deque Implementation using Doubly Linked List
// All operations O(1)

public class Deque<T> {
    private class Node {
        T data;
        Node prev, next;
        Node(T data) { this.data = data; }
    }
    
    private Node frontNode, rearNode;
    private int size;
    
    public void addFront(T item) {
        Node newNode = new Node(item);
        if (isEmpty()) {
            frontNode = rearNode = newNode;
        } else {
            newNode.next = frontNode;
            frontNode.prev = newNode;
            frontNode = newNode;
        }
        size++;
    }
    
    public void addRear(T item) {
        Node newNode = new Node(item);
        if (isEmpty()) {
            frontNode = rearNode = newNode;
        } else {
            newNode.prev = rearNode;
            rearNode.next = newNode;
            rearNode = newNode;
        }
        size++;
    }
    
    public T removeFront() {
        if (isEmpty()) throw new java.util.NoSuchElementException("Deque is empty");
        T item = frontNode.data;
        frontNode = frontNode.next;
        if (frontNode != null) frontNode.prev = null;
        else rearNode = null;
        size--;
        return item;
    }
    
    public T removeRear() {
        if (isEmpty()) throw new java.util.NoSuchElementException("Deque is empty");
        T item = rearNode.data;
        rearNode = rearNode.prev;
        if (rearNode != null) rearNode.next = null;
        else frontNode = null;
        size--;
        return item;
    }
    
    public T peekFront() {
        if (isEmpty()) throw new java.util.NoSuchElementException("Deque is empty");
        return frontNode.data;
    }
    
    public T peekRear() {
        if (isEmpty()) throw new java.util.NoSuchElementException("Deque is empty");
        return rearNode.data;
    }
    
    public boolean isEmpty() { return frontNode == null; }
    public int size() { return size; }
    
    public void display() {
        StringBuilder sb = new StringBuilder("Deque: ");
        Node current = frontNode;
        while (current != null) {
            sb.append(current.data);
            if (current.next != null) sb.append(" <-> ");
            current = current.next;
        }
        System.out.println(sb);
    }
    
    public static void main(String[] args) {
        Deque<Integer> deque = new Deque<>();
        deque.addRear(1);
        deque.addRear(2);
        deque.addFront(0);
        deque.addRear(3);
        deque.display();  // Deque: 0 <-> 1 <-> 2 <-> 3
        
        System.out.println("Remove front: " + deque.removeFront());  // 0
        System.out.println("Remove rear: " + deque.removeRear());    // 3
        deque.display();  // Deque: 1 <-> 2
    }
}

# Python's collections.deque - Highly optimized implementation
from collections import deque

# Create deque
d = deque([1, 2, 3])

# Add to both ends
d.append(4)        # Add to right
d.appendleft(0)    # Add to left
print(d)  # deque([0, 1, 2, 3, 4])

# Remove from both ends
d.pop()            # Remove from right
d.popleft()        # Remove from left
print(d)  # deque([1, 2, 3])

# Rotation
d = deque([1, 2, 3, 4, 5])
d.rotate(2)   # Rotate right by 2
print(d)  # deque([4, 5, 1, 2, 3])

d.rotate(-2)  # Rotate left by 2
print(d)  # deque([1, 2, 3, 4, 5])

# Max length deque (automatically removes from opposite end)
bounded = deque(maxlen=3)
bounded.extend([1, 2, 3])
bounded.append(4)  # 1 is automatically removed
print(bounded)  # deque([2, 3, 4], maxlen=3)

// C++ std::deque - Highly optimized double-ended queue
#include <iostream>
#include <deque>
#include <algorithm>

int main() {
    std::deque<int> d = {1, 2, 3};
    
    // Add to both ends
    d.push_back(4);      // Add to right
    d.push_front(0);     // Add to left
    // d = {0, 1, 2, 3, 4}
    
    // Remove from both ends
    d.pop_back();        // Remove from right
    d.pop_front();       // Remove from left
    // d = {1, 2, 3}
    
    // Access elements
    std::cout << "Front: " << d.front() << std::endl;  // 1
    std::cout << "Back: " << d.back() << std::endl;    // 3
    std::cout << "Index 1: " << d[1] << std::endl;     // 2
    
    // Rotation using std::rotate
    d = {1, 2, 3, 4, 5};
    std::rotate(d.begin(), d.begin() + 2, d.end());  // Rotate left by 2
    // d = {3, 4, 5, 1, 2}
    
    // Print deque
    for (int val : d) std::cout << val << " ";
    std::cout << std::endl;
    
    return 0;
}

// Java's ArrayDeque - Highly optimized double-ended queue
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Collections;
import java.util.LinkedList;

public class DequeDemo {
    public static void main(String[] args) {
        Deque<Integer> d = new ArrayDeque<>();
        d.add(1); d.add(2); d.add(3);  // d = [1, 2, 3]
        
        // Add to both ends
        d.addLast(4);      // Add to right
        d.addFirst(0);     // Add to left
        // d = [0, 1, 2, 3, 4]
        
        // Remove from both ends
        d.pollLast();      // Remove from right
        d.pollFirst();     // Remove from left
        // d = [1, 2, 3]
        
        // Access elements
        System.out.println("First: " + d.peekFirst());  // 1
        System.out.println("Last: " + d.peekLast());    // 3
        
        // Rotation using Collections (with LinkedList)
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1); list.add(2); list.add(3); list.add(4); list.add(5);
        
        Collections.rotate(list, 2);  // Rotate right by 2
        System.out.println(list);  // [4, 5, 1, 2, 3]
        
        Collections.rotate(list, -2); // Rotate left by 2
        System.out.println(list);  // [1, 2, 3, 4, 5]
        
        // Print deque
        for (int val : d) System.out.print(val + " ");
        System.out.println();
    }
}

Priority Queue

A priority queue serves elements based on their priority rather than insertion order. Unlike a regular queue (FIFO), the element with the highest priority (or lowest value in a min-priority queue) is always served first. Typically backed by a binary heap, giving \(O(\log n)\) insert and extract-min/max. Use cases: Dijkstra's shortest path, A* pathfinding, event-driven simulation, OS task scheduling (nice values), Huffman encoding, and any problem where you repeatedly need "the best/smallest/largest current option".

# Priority Queue using Python's heapq (Min-Heap)
import heapq

# Simple priority queue with heapq
class PriorityQueue:
    def __init__(self):
        self._heap = []
        self._index = 0  # For stable sorting of same priority
    
    def push(self, item, priority):
        """Add item with priority (lower priority = higher importance)"""
        heapq.heappush(self._heap, (priority, self._index, item))
        self._index += 1
    
    def pop(self):
        """Remove and return highest priority item"""
        if self.is_empty():
            raise IndexError("Priority queue is empty")
        return heapq.heappop(self._heap)[2]
    
    def peek(self):
        """Return highest priority item without removing"""
        if self.is_empty():
            raise IndexError("Priority queue is empty")
        return self._heap[0][2]
    
    def is_empty(self):
        return len(self._heap) == 0
    
    def size(self):
        return len(self._heap)

# Test Priority Queue
pq = PriorityQueue()
pq.push("Task C", 3)  # Low priority
pq.push("Task A", 1)  # High priority
pq.push("Task B", 2)  # Medium priority
pq.push("Task D", 1)  # Same high priority as Task A

# Pop in priority order
while not pq.is_empty():
    print(f"Processing: {pq.pop()}")
# Task A, Task D, Task B, Task C (ordered by priority, FIFO for same priority)

// Priority Queue using std::priority_queue (Max-Heap by default)
// For Min-Heap, use greater<> comparator
#include <iostream>
#include <queue>
#include <vector>
#include <string>

int main() {
    // Min-Heap Priority Queue with (priority, index, item)
    // Use greater<> for min-heap behavior
    using PQItem = std::tuple<int, int, std::string>;
    std::priority_queue<PQItem, std::vector<PQItem>, std::greater<PQItem>> pq;
    
    int index = 0;
    pq.push({3, index++, "Task C"});  // Low priority
    pq.push({1, index++, "Task A"});  // High priority
    pq.push({2, index++, "Task B"});  // Medium priority
    pq.push({1, index++, "Task D"});  // Same high priority as Task A
    
    // Pop in priority order
    while (!pq.empty()) {
        auto [priority, idx, item] = pq.top();
        pq.pop();
        std::cout << "Processing: " << item << std::endl;
    }
    // Task A, Task D, Task B, Task C (ordered by priority, FIFO for same priority)
    
    return 0;
}

// Priority Queue using PriorityQueue (Min-Heap by default)
import java.util.PriorityQueue;
import java.util.Comparator;

public class PriorityQueueDemo {
    static class Task {
        String name;
        int priority;
        int index;  // For FIFO ordering of same priority
        
        Task(String name, int priority, int index) {
            this.name = name;
            this.priority = priority;
            this.index = index;
        }
    }
    
    public static void main(String[] args) {
        // Min-Heap: lower priority value = higher importance
        PriorityQueue<Task> pq = new PriorityQueue<>(
            Comparator.comparingInt((Task t) -> t.priority)
                      .thenComparingInt(t -> t.index)  // FIFO for same priority
        );
        
        int index = 0;
        pq.offer(new Task("Task C", 3, index++));  // Low priority
        pq.offer(new Task("Task A", 1, index++));  // High priority
        pq.offer(new Task("Task B", 2, index++));  // Medium priority
        pq.offer(new Task("Task D", 1, index++));  // Same high priority as Task A
        
        // Pop in priority order
        while (!pq.isEmpty()) {
            Task task = pq.poll();
            System.out.println("Processing: " + task.name);
        }
        // Task A, Task D, Task B, Task C (ordered by priority, FIFO for same priority)
    }
}

# Max-Heap Priority Queue (negate priorities)
import heapq

class MaxPriorityQueue:
    def __init__(self):
        self._heap = []
    
    def push(self, item, priority):
        """Add item with priority (higher priority = more important)"""
        heapq.heappush(self._heap, (-priority, item))
    
    def pop(self):
        """Remove and return highest priority item"""
        if not self._heap:
            raise IndexError("Empty")
        return heapq.heappop(self._heap)[1]
    
    def peek(self):
        return self._heap[0][1] if self._heap else None

# Test Max Priority Queue
max_pq = MaxPriorityQueue()
max_pq.push("Low", 1)
max_pq.push("High", 10)
max_pq.push("Medium", 5)

print(max_pq.pop())  # High
print(max_pq.pop())  # Medium
print(max_pq.pop())  # Low

// Max-Heap Priority Queue (default behavior in C++)
#include <iostream>
#include <queue>
#include <string>

int main() {
    // Max-Heap: higher priority = higher importance (default)
    std::priority_queue<std::pair<int, std::string>> maxPQ;
    
    maxPQ.push({1, "Low"});
    maxPQ.push({10, "High"});
    maxPQ.push({5, "Medium"});
    
    while (!maxPQ.empty()) {
        auto [priority, item] = maxPQ.top();
        maxPQ.pop();
        std::cout << item << std::endl;
    }
    // High, Medium, Low
    
    return 0;
}

// Max-Heap Priority Queue (use reverseOrder comparator)
import java.util.PriorityQueue;
import java.util.Collections;
import java.util.Comparator;

public class MaxPriorityQueueDemo {
    public static void main(String[] args) {
        // Max-Heap: use reverseOrder or custom comparator
        PriorityQueue<int[]> maxPQ = new PriorityQueue<>(
            (a, b) -> b[0] - a[0]  // Compare by priority descending
        );
        
        maxPQ.offer(new int[]{1, 0});   // {priority, index for "Low"}
        maxPQ.offer(new int[]{10, 1});  // {priority, index for "High"}
        maxPQ.offer(new int[]{5, 2});   // {priority, index for "Medium"}
        
        String[] items = {"Low", "High", "Medium"};
        
        while (!maxPQ.isEmpty()) {
            int[] entry = maxPQ.poll();
            System.out.println(items[entry[1]]);
        }
        // High, Medium, Low
        
        // Alternative: Simple max-heap for integers
        PriorityQueue<Integer> maxInts = new PriorityQueue<>(Collections.reverseOrder());
        maxInts.offer(1);
        maxInts.offer(10);
        maxInts.offer(5);
        
        while (!maxInts.isEmpty()) {
            System.out.print(maxInts.poll() + " ");  // 10 5 1
        }
        System.out.println();
    }
}

Queue Applications

Breadth-First Search (BFS)

BFS is the defining application of queues. The algorithm explores a graph level-by-level: visit all nodes at distance 1 from the source before any at distance 2. The queue maintains the "frontier" — nodes discovered but not yet explored. This level-by-level expansion naturally finds shortest paths in unweighted graphs and powers maze solvers, social network friend suggestions ("people 2 hops away"), and web crawlers.

# BFS - Classic Queue Application
from collections import deque

def bfs_graph(graph, start):
    """
    Breadth-First Search on a graph.
    Time: O(V + E), Space: O(V)
    """
    visited = set()
    queue = deque([start])
    visited.add(start)
    traversal = []
    
    while queue:
        node = queue.popleft()
        traversal.append(node)
        
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return traversal

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

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

// BFS - Classic Queue Application
// Time: O(V + E), Space: O(V)
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>

std::vector<std::string> bfsGraph(
    const std::unordered_map<std::string, std::vector<std::string>>& graph,
    const std::string& start
) {
    std::unordered_set<std::string> visited;
    std::queue<std::string> q;
    std::vector<std::string> traversal;
    
    q.push(start);
    visited.insert(start);
    
    while (!q.empty()) {
        std::string node = q.front();
        q.pop();
        traversal.push_back(node);
        
        if (graph.find(node) != graph.end()) {
            for (const auto& neighbor : graph.at(node)) {
                if (visited.find(neighbor) == visited.end()) {
                    visited.insert(neighbor);
                    q.push(neighbor);
                }
            }
        }
    }
    return traversal;
}

int main() {
    std::unordered_map<std::string, std::vector<std::string>> graph = {
        {"A", {"B", "C"}},
        {"B", {"A", "D", "E"}},
        {"C", {"A", "F"}},
        {"D", {"B"}},
        {"E", {"B", "F"}},
        {"F", {"C", "E"}}
    };
    
    std::cout << "BFS traversal: ";
    for (const auto& node : bfsGraph(graph, "A")) {
        std::cout << node << " ";
    }
    std::cout << std::endl;  // A B C D E F
    return 0;
}

// BFS - Classic Queue Application
// Time: O(V + E), Space: O(V)
import java.util.*;

public class BFSGraph {
    public static List<String> bfsGraph(
        Map<String, List<String>> graph, String start
    ) {
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        List<String> traversal = new ArrayList<>();
        
        queue.offer(start);
        visited.add(start);
        
        while (!queue.isEmpty()) {
            String node = queue.poll();
            traversal.add(node);
            
            for (String neighbor : graph.getOrDefault(node, List.of())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        return traversal;
    }
    
    public static void main(String[] args) {
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("A", Arrays.asList("B", "C"));
        graph.put("B", Arrays.asList("A", "D", "E"));
        graph.put("C", Arrays.asList("A", "F"));
        graph.put("D", Arrays.asList("B"));
        graph.put("E", Arrays.asList("B", "F"));
        graph.put("F", Arrays.asList("C", "E"));
        
        System.out.println("BFS traversal: " + bfsGraph(graph, "A"));
        // [A, B, C, D, E, F]
    }
}

# Level Order Traversal of Binary Tree
from collections import deque

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

def level_order_traversal(root):
    """
    Level-order traversal using queue.
    Time: O(n), Space: O(n)
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

# Test
#       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))
# [[1], [2, 3], [4, 5, 6]]

// Level Order Traversal of Binary Tree
// Time: O(n), Space: O(n)
#include <iostream>
#include <vector>
#include <queue>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

std::vector<std::vector<int>> levelOrderTraversal(TreeNode* root) {
    std::vector<std::vector<int>> result;
    if (!root) return result;
    
    std::queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int levelSize = q.size();
        std::vector<int> level;
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(level);
    }
    return result;
}

int main() {
    //       1
    //      / \
    //     2   3
    //    / \   \
    //   4   5   6
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);
    
    std::cout << "Level Order: ";
    auto result = levelOrderTraversal(root);
    for (const auto& level : result) {
        std::cout << "[";
        for (int i = 0; i < level.size(); i++) {
            std::cout << level[i];
            if (i < level.size() - 1) std::cout << ", ";
        }
        std::cout << "] ";
    }
    std::cout << std::endl;  // [1] [2, 3] [4, 5, 6]
    return 0;
}

// Level Order Traversal of Binary Tree
// Time: O(n), Space: O(n)
import java.util.*;

public class LevelOrderTraversal {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }
    
    public static List<List<Integer>> levelOrderTraversal(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> level = new ArrayList<>();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
        }
        return result;
    }
    
    public static void main(String[] args) {
        //       1
        //      / \
        //     2   3
        //    / \   \
        //   4   5   6
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
        
        System.out.println("Level Order: " + levelOrderTraversal(root));
        // [[1], [2, 3], [4, 5, 6]]
    }
}

Sliding Window Maximum (Monotonic Deque)

Given an array and window size \(k\), find the maximum in each window as it slides right. The brute force is \(O(nk)\). A monotonic decreasing deque solves it in \(O(n)\): the deque's front always holds the index of the current window's maximum. When sliding right: (1) remove indices that fell out of the window from the front, (2) remove all indices from the back whose values are smaller than the new element (they can never be the max), (3) add the new index. This is one of the most elegant deque applications in competitive programming.

# Sliding Window Maximum using Monotonic Deque
from collections import deque

def max_sliding_window(nums, k):
    """
    Find maximum in each sliding window of size k.
    Uses monotonic decreasing deque.
    Time: O(n), Space: O(k)
    """
    if not nums or k == 0:
        return []
    
    deq = deque()  # Stores indices, values in decreasing order
    result = []
    
    for i in range(len(nums)):
        # Remove indices outside window
        while deq and deq[0] < i - k + 1:
            deq.popleft()
        
        # Remove smaller elements from back (maintain decreasing order)
        while deq and nums[deq[-1]] < nums[i]:
            deq.pop()
        
        deq.append(i)
        
        # Add to result once window is of size k
        if i >= k - 1:
            result.append(nums[deq[0]])
    
    return result

# Test
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(f"nums = {nums}, k = {k}")
print(f"Max in each window: {max_sliding_window(nums, k)}")
# [3, 3, 5, 5, 6, 7]

# Explanation:
# Window [1, 3, -1] max=3
# Window [3, -1, -3] max=3
# Window [-1, -3, 5] max=5
# Window [-3, 5, 3] max=5
# Window [5, 3, 6] max=6
# Window [3, 6, 7] max=7

// Sliding Window Maximum using Monotonic Deque
// Time: O(n), Space: O(k)
#include <iostream>
#include <vector>
#include <deque>

std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {
    std::vector<int> result;
    if (nums.empty() || k == 0) return result;
    
    std::deque<int> dq;  // Stores indices, values in decreasing order
    
    for (int i = 0; i < nums.size(); i++) {
        // Remove indices outside window
        while (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }
        
        // Remove smaller elements from back (maintain decreasing order)
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }
        
        dq.push_back(i);
        
        // Add to result once window is of size k
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    return result;
}

int main() {
    std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    
    std::cout << "nums = [";
    for (int i = 0; i < nums.size(); i++) {
        std::cout << nums[i] << (i < nums.size() - 1 ? ", " : "");
    }
    std::cout << "], k = " << k << std::endl;
    
    std::cout << "Max in each window: ";
    for (int val : maxSlidingWindow(nums, k)) {
        std::cout << val << " ";
    }
    std::cout << std::endl;  // 3 3 5 5 6 7
    return 0;
}

// Sliding Window Maximum using Monotonic Deque
// Time: O(n), Space: O(k)
import java.util.*;

public class SlidingWindowMax {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 0) {
            return new int[0];
        }
        
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();  // Stores indices
        
        for (int i = 0; i < n; i++) {
            // Remove indices outside window
            while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) {
                dq.pollFirst();
            }
            
            // Remove smaller elements from back (maintain decreasing order)
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
                dq.pollLast();
            }
            
            dq.offerLast(i);
            
            // Add to result once window is of size k
            if (i >= k - 1) {
                result[i - k + 1] = nums[dq.peekFirst()];
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        
        System.out.println("nums = " + Arrays.toString(nums) + ", k = " + k);
        System.out.println("Max in each window: " + 
            Arrays.toString(maxSlidingWindow(nums, k)));
        // [3, 3, 5, 5, 6, 7]
    }
}

                            Decision Lens: Queue Type Selection
                            
                                NeedUseKey Method

                                Basic FIFOcollections.dequeappend / popleft — both \(O(1)\)
Priority / min extractionheapq or PriorityQueueheappush / heappop — \(O(\log n)\)
Thread-safe queuequeue.QueueBlocking put / get with timeout
Sliding window max/minMonotonic dequeMaintain decreasing order, \(O(1)\) window max
Distributed / persistentRabbitMQ / SQS / KafkaAMQP / HTTP API; at-least-once delivery

Need	Use	Key Method
Basic FIFO	`collections.deque`	`append / popleft` — both \(O(1)\)
Priority / min extraction	`heapq` or `PriorityQueue`	`heappush / heappop` — \(O(\log n)\)
Thread-safe queue	`queue.Queue`	Blocking `put / get` with timeout
Sliding window max/min	Monotonic deque	Maintain decreasing order, \(O(1)\) window max
Distributed / persistent	RabbitMQ / SQS / Kafka	AMQP / HTTP API; at-least-once delivery

LeetCode Practice Problems

Easy 232. Implement Queue using Stacks

Implement a FIFO queue using only two stacks.

# LeetCode 232 - Implement Queue using Stacks
# Amortized O(1) for all operations

class MyQueue:
    def __init__(self):
        self.stack_in = []   # For enqueue
        self.stack_out = []  # For dequeue
    
    def push(self, x):
        """Add to rear - O(1)"""
        self.stack_in.append(x)
    
    def pop(self):
        """Remove from front - Amortized O(1)"""
        self._transfer()
        return self.stack_out.pop()
    
    def peek(self):
        """Get front - Amortized O(1)"""
        self._transfer()
        return self.stack_out[-1]
    
    def empty(self):
        return not self.stack_in and not self.stack_out
    
    def _transfer(self):
        """Move elements from stack_in to stack_out"""
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())

# Test
queue = MyQueue()
queue.push(1)
queue.push(2)
print(queue.peek())   # 1
print(queue.pop())    # 1
print(queue.empty())  # False

// LeetCode 232 - Implement Queue using Stacks
// Amortized O(1) for all operations
#include <stack>

class MyQueue {
private:
    std::stack<int> stackIn;   // For enqueue
    std::stack<int> stackOut;  // For dequeue
    
    void transfer() {
        if (stackOut.empty()) {
            while (!stackIn.empty()) {
                stackOut.push(stackIn.top());
                stackIn.pop();
            }
        }
    }

public:
    void push(int x) {
        stackIn.push(x);  // O(1)
    }
    
    int pop() {
        transfer();  // Amortized O(1)
        int val = stackOut.top();
        stackOut.pop();
        return val;
    }
    
    int peek() {
        transfer();  // Amortized O(1)
        return stackOut.top();
    }
    
    bool empty() {
        return stackIn.empty() && stackOut.empty();
    }
};

// Usage:
// MyQueue queue;
// queue.push(1); queue.push(2);
// queue.peek();  // 1
// queue.pop();   // 1
// queue.empty(); // false

// LeetCode 232 - Implement Queue using Stacks
// Amortized O(1) for all operations
import java.util.Stack;

class MyQueue {
    private Stack<Integer> stackIn;   // For enqueue
    private Stack<Integer> stackOut;  // For dequeue
    
    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }
    
    private void transfer() {
        if (stackOut.isEmpty()) {
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
    }
    
    public void push(int x) {
        stackIn.push(x);  // O(1)
    }
    
    public int pop() {
        transfer();  // Amortized O(1)
        return stackOut.pop();
    }
    
    public int peek() {
        transfer();  // Amortized O(1)
        return stackOut.peek();
    }
    
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
}

// Usage:
// MyQueue queue = new MyQueue();
// queue.push(1); queue.push(2);
// queue.peek();  // 1
// queue.pop();   // 1
// queue.empty(); // false

Medium 622. Design Circular Queue

Design a circular queue implementation.

# LeetCode 622 - Design Circular Queue
# All operations O(1)

class MyCircularQueue:
    def __init__(self, k):
        self.queue = [None] * k
        self.capacity = k
        self.size = 0
        self.front = 0
        self.rear = -1
    
    def enQueue(self, value):
        if self.isFull():
            return False
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = value
        self.size += 1
        return True
    
    def deQueue(self):
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return True
    
    def Front(self):
        return -1 if self.isEmpty() else self.queue[self.front]
    
    def Rear(self):
        return -1 if self.isEmpty() else self.queue[self.rear]
    
    def isEmpty(self):
        return self.size == 0
    
    def isFull(self):
        return self.size == self.capacity

# Test
cq = MyCircularQueue(3)
print(cq.enQueue(1))  # True
print(cq.enQueue(2))  # True
print(cq.enQueue(3))  # True
print(cq.enQueue(4))  # False (full)
print(cq.Rear())      # 3
print(cq.isFull())    # True
print(cq.deQueue())   # True
print(cq.enQueue(4))  # True
print(cq.Rear())      # 4

// LeetCode 622 - Design Circular Queue
// All operations O(1)
#include <vector>

class MyCircularQueue {
private:
    std::vector<int> queue;
    int capacity;
    int size;
    int front;
    int rear;

public:
    MyCircularQueue(int k) : capacity(k), size(0), front(0), rear(-1) {
        queue.resize(k);
    }
    
    bool enQueue(int value) {
        if (isFull()) return false;
        rear = (rear + 1) % capacity;
        queue[rear] = value;
        size++;
        return true;
    }
    
    bool deQueue() {
        if (isEmpty()) return false;
        front = (front + 1) % capacity;
        size--;
        return true;
    }
    
    int Front() {
        return isEmpty() ? -1 : queue[front];
    }
    
    int Rear() {
        return isEmpty() ? -1 : queue[rear];
    }
    
    bool isEmpty() {
        return size == 0;
    }
    
    bool isFull() {
        return size == capacity;
    }
};

// Usage:
// MyCircularQueue cq(3);
// cq.enQueue(1);  // true
// cq.enQueue(2);  // true
// cq.enQueue(3);  // true
// cq.enQueue(4);  // false (full)
// cq.Rear();      // 3

// LeetCode 622 - Design Circular Queue
// All operations O(1)

class MyCircularQueue {
    private int[] queue;
    private int capacity;
    private int size;
    private int front;
    private int rear;
    
    public MyCircularQueue(int k) {
        capacity = k;
        queue = new int[k];
        size = 0;
        front = 0;
        rear = -1;
    }
    
    public boolean enQueue(int value) {
        if (isFull()) return false;
        rear = (rear + 1) % capacity;
        queue[rear] = value;
        size++;
        return true;
    }
    
    public boolean deQueue() {
        if (isEmpty()) return false;
        front = (front + 1) % capacity;
        size--;
        return true;
    }
    
    public int Front() {
        return isEmpty() ? -1 : queue[front];
    }
    
    public int Rear() {
        return isEmpty() ? -1 : queue[rear];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == capacity;
    }
}

// Usage:
// MyCircularQueue cq = new MyCircularQueue(3);
// cq.enQueue(1);  // true
// cq.enQueue(2);  // true
// cq.enQueue(3);  // true
// cq.enQueue(4);  // false (full)
// cq.Rear();      // 3

Medium 102. Binary Tree Level Order Traversal

Return the level order traversal of a binary tree.

# LeetCode 102 - Binary Tree Level Order Traversal
# Time: O(n), Space: O(n)
from collections import deque

def levelOrder(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

// LeetCode 102 - Binary Tree Level Order Traversal
// Time: O(n), Space: O(n)
#include <vector>
#include <queue>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    std::vector<std::vector<int>> levelOrder(TreeNode* root) {
        std::vector<std::vector<int>> result;
        if (!root) return result;
        
        std::queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            int levelSize = q.size();
            std::vector<int> level;
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            result.push_back(level);
        }
        return result;
    }
};

// LeetCode 102 - Binary Tree Level Order Traversal
// Time: O(n), Space: O(n)
import java.util.*;

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> level = new ArrayList<>();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
        }
        return result;
    }
}

Hard 239. Sliding Window Maximum

Find the maximum in each sliding window.

# LeetCode 239 - Sliding Window Maximum
# Time: O(n), Space: O(k)
from collections import deque

def maxSlidingWindow(nums, k):
    if not nums:
        return []
    
    deq = deque()  # Indices with decreasing values
    result = []
    
    for i, num in enumerate(nums):
        # Remove indices outside window
        while deq and deq[0] < i - k + 1:
            deq.popleft()
        
        # Remove smaller elements
        while deq and nums[deq[-1]] < num:
            deq.pop()
        
        deq.append(i)
        
        # Add max when window is complete
        if i >= k - 1:
            result.append(nums[deq[0]])
    
    return result

# Test
print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]

// LeetCode 239 - Sliding Window Maximum
// Time: O(n), Space: O(k)
#include <vector>
#include <deque>

class Solution {
public:
    std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
        std::vector<int> result;
        std::deque<int> dq;  // Indices with decreasing values
        
        for (int i = 0; i < nums.size(); i++) {
            // Remove indices outside window
            while (!dq.empty() && dq.front() < i - k + 1) {
                dq.pop_front();
            }
            
            // Remove smaller elements
            while (!dq.empty() && nums[dq.back()] < nums[i]) {
                dq.pop_back();
            }
            
            dq.push_back(i);
            
            // Add max when window is complete
            if (i >= k - 1) {
                result.push_back(nums[dq.front()]);
            }
        }
        return result;
    }
};

// Test: maxSlidingWindow({1,3,-1,-3,5,3,6,7}, 3) = {3,3,5,5,6,7}

// LeetCode 239 - Sliding Window Maximum
// Time: O(n), Space: O(k)
import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();  // Indices with decreasing values
        
        for (int i = 0; i < n; i++) {
            // Remove indices outside window
            while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) {
                dq.pollFirst();
            }
            
            // Remove smaller elements
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
                dq.pollLast();
            }
            
            dq.offerLast(i);
            
            // Add max when window is complete
            if (i >= k - 1) {
                result[i - k + 1] = nums[dq.peekFirst()];
            }
        }
        return result;
    }
}

// Test: maxSlidingWindow({1,3,-1,-3,5,3,6,7}, 3) = {3,3,5,5,6,7}

Medium 621. Task Scheduler

Schedule tasks with cooldown period.

# LeetCode 621 - Task Scheduler
# Time: O(n), Space: O(1)
from collections import Counter

def leastInterval(tasks, n):
    """
    Find minimum intervals to complete all tasks with cooldown.
    """
    freq = Counter(tasks)
    max_freq = max(freq.values())
    
    # Count tasks with max frequency
    max_count = sum(1 for f in freq.values() if f == max_freq)
    
    # Formula: (max_freq - 1) * (n + 1) + max_count
    # But result can't be less than total tasks
    result = (max_freq - 1) * (n + 1) + max_count
    
    return max(result, len(tasks))

# Test
print(leastInterval(["A","A","A","B","B","B"], 2))  # 8
# A -> B -> idle -> A -> B -> idle -> A -> B

// LeetCode 621 - Task Scheduler
// Time: O(n), Space: O(1)
#include <vector>
#include <algorithm>

class Solution {
public:
    int leastInterval(std::vector<char>& tasks, int n) {
        // Count frequency of each task
        std::vector<int> freq(26, 0);
        for (char task : tasks) {
            freq[task - 'A']++;
        }
        
        int maxFreq = *std::max_element(freq.begin(), freq.end());
        
        // Count tasks with max frequency
        int maxCount = 0;
        for (int f : freq) {
            if (f == maxFreq) maxCount++;
        }
        
        // Formula: (maxFreq - 1) * (n + 1) + maxCount
        // But result can't be less than total tasks
        int result = (maxFreq - 1) * (n + 1) + maxCount;
        
        return std::max(result, static_cast<int>(tasks.size()));
    }
};

// Test: leastInterval({A,A,A,B,B,B}, 2) = 8
// A -> B -> idle -> A -> B -> idle -> A -> B

// LeetCode 621 - Task Scheduler
// Time: O(n), Space: O(1)
import java.util.*;

class Solution {
    public int leastInterval(char[] tasks, int n) {
        // Count frequency of each task
        int[] freq = new int[26];
        for (char task : tasks) {
            freq[task - 'A']++;
        }
        
        int maxFreq = Arrays.stream(freq).max().getAsInt();
        
        // Count tasks with max frequency
        int maxCount = 0;
        for (int f : freq) {
            if (f == maxFreq) maxCount++;
        }
        
        // Formula: (maxFreq - 1) * (n + 1) + maxCount
        // But result can't be less than total tasks
        int result = (maxFreq - 1) * (n + 1) + maxCount;
        
        return Math.max(result, tasks.length);
    }
}

// Test: leastInterval(['A','A','A','B','B','B'], 2) = 8
// A -> B -> idle -> A -> B -> idle -> A -> B

Quick Check — Test Yourself

Implement a queue using two stacks. What are the amortized costs?
Given a grid of 0s and 1s, find the shortest path from top-left to bottom-right using multi-source BFS.
What is the sliding window maximum for [1,3,-1,-3,5,3,6,7] with window size 3?

Common Bugs

Using list.pop(0) for dequeue: This is \(O(n)\) in Python. Always use collections.deque.popleft() for \(O(1)\).
Not marking visited in BFS: Marking visited when enqueuing (not when dequeuing) is critical — otherwise the same node gets added multiple times.
Circular queue index wrap-around: (rear + 1) % capacity not rear + 1. Forgetting the modulo breaks the ring buffer.

Interview Lens

BFS problems often have non-obvious multi-source setups: “01 matrix” (distance from nearest 0), “rotting oranges” (simultaneous spread). The key insight: enqueue all sources at step 0 before starting BFS. This gives the correct shortest distance from any source in one pass.

Production Lens

AWS SQS, RabbitMQ, and Apache Kafka all implement queue semantics at distributed scale. Key concepts: at-least-once vs exactly-once delivery, dead-letter queues for failed messages, visibility timeout (message becomes invisible while being processed), and back-pressure when consumers are slower than producers.

Next in the Series

In Part 9: Trees & Tree Traversals, queues get their most important application — level-order (BFS) traversal is a queue in disguise, and trees are the foundation for BSTs, heaps, and tries.