Complete DSA Series Part 8: Queue

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 Operations

Queue Implementations

Array-Based Queue (Simple)

# 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])

C++

// 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;
}

Java

// 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

# 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

C++

// 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;
}

Java

// 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 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

C++

// 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;
}

Java

// 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.

# 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

C++

// 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;
}

Java

// 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++

// 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

// 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. Typically implemented using a heap.

# 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)

C++

// 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;
}

Java

// 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

C++

// 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;
}

Java

// 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 - 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']

C++

// 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;
}

Java

// 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]]

C++

// 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;
}

Java

// 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)

# 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

C++

// 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;
}

Java

// 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]
    }
}

LeetCode Practice Problems

# 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

# 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

# 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;
    }
}

# 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}

# 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