Design Queue

Overview

Design Queue is a fundamental system design problem that asks you to implement a queue data structure from scratch with all its core operations. This problem tests your understanding of queue operations, implementation choices (array vs linked list), edge cases, and efficient design.

A well-designed queue should support:

• enqueue(item) - Add element to rear
• dequeue() - Remove element from front
• peek() / front() - View front element without removing
• isEmpty() - Check if queue is empty
• size() - Get number of elements

Key characteristics:

• FIFO order - First in, first out
• Two ends - Front (dequeue) and rear (enqueue)
• O(1) operations - Efficient enqueue and dequeue
• Dynamic size - Can grow/shrink as needed
• Edge case handling - Handle empty queue, single element, etc.

Implementation Approaches

Approach 1: Linked List Implementation (Recommended)

Using doubly linked list for O(1) operations:

class ListNode<T> {
  val: T;
  next: ListNode<T> | null = null;
  prev: ListNode<T> | null = null;
  constructor(val: T) {
    this.val = val;
  }
}

class Queue<T> {
  private head: ListNode<T> | null = null;
  private tail: ListNode<T> | null = null;
  private length = 0;
  
  enqueue(item: T): void {
    const newNode = new ListNode(item);
    
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail!.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    
    this.length++;
  }
  
  dequeue(): T | undefined {
    if (this.isEmpty()) return undefined;
    
    const val = this.head!.val;
    
    if (this.head === this.tail) {
      // Single element
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head!.next;
      this.head!.prev = null;
    }
    
    this.length--;
    return val;
  }
  
  peek(): T | undefined {
    return this.head?.val;
  }
  
  rear(): T | undefined {
    return this.tail?.val;
  }
  
  isEmpty(): boolean {
    return this.length === 0;
  }
  
  size(): number {
    return this.length;
  }
}

Time: O(1) for all operations, Space: O(n)

Advantages:

• True O(1) operations
• Dynamic size
• No wasted space

Approach 2: Array with Pointers

Using array with front and rear pointers:

class QueueArray<T> {
  private items: T[] = [];
  private front = 0;
  private rear = -1;
  
  enqueue(item: T): void {
    this.rear++;
    this.items[this.rear] = item;
  }
  
  dequeue(): T | undefined {
    if (this.isEmpty()) return undefined;
    
    const item = this.items[this.front];
    this.front++;
    return item;
  }
  
  peek(): T | undefined {
    return this.isEmpty() ? undefined : this.items[this.front];
  }
  
  isEmpty(): boolean {
    return this.front > this.rear;
  }
  
  size(): number {
    return this.rear - this.front + 1;
  }
}

Time: O(1) amortized, Space: O(n)

Limitation: Space grows but never shrinks (front pointer moves but array doesn't shrink).

Approach 3: Circular Array (Fixed Size)

Using circular array for fixed-size queue:

class CircularQueue<T> {
  private items: (T | null)[];
  private front = 0;
  private rear = -1;
  private size = 0;
  private capacity: number;
  
  constructor(capacity: number) {
    this.capacity = capacity;
    this.items = new Array(capacity).fill(null);
  }
  
  enqueue(item: T): boolean {
    if (this.isFull()) return false;
    
    this.rear = (this.rear + 1) % this.capacity;
    this.items[this.rear] = item;
    this.size++;
    return true;
  }
  
  dequeue(): T | null {
    if (this.isEmpty()) return null;
    
    const item = this.items[this.front];
    this.items[this.front] = null;
    this.front = (this.front + 1) % this.capacity;
    this.size--;
    return item;
  }
  
  peek(): T | null {
    return this.isEmpty() ? null : this.items[this.front];
  }
  
  isEmpty(): boolean {
    return this.size === 0;
  }
  
  isFull(): boolean {
    return this.size === this.capacity;
  }
  
  getSize(): number {
    return this.size;
  }
}

Time: O(1) for all operations, Space: O(capacity)

Use case: Fixed-size queue requirements.

Pattern 1: LeetCode - Design Circular Queue

LeetCode problem with specific requirements:

class MyCircularQueue {
  private items: number[];
  private front = 0;
  private rear = -1;
  private size = 0;
  private capacity: number;
  
  constructor(k: number) {
    this.capacity = k;
    this.items = new Array(k);
  }
  
  enQueue(value: number): boolean {
    if (this.isFull()) return false;
    
    this.rear = (this.rear + 1) % this.capacity;
    this.items[this.rear] = value;
    this.size++;
    return true;
  }
  
  deQueue(): boolean {
    if (this.isEmpty()) return false;
    
    this.items[this.front] = undefined;
    this.front = (this.front + 1) % this.capacity;
    this.size--;
    return true;
  }
  
  Front(): number {
    return this.isEmpty() ? -1 : this.items[this.front];
  }
  
  Rear(): number {
    if (this.isEmpty()) return -1;
    const rearIndex = (this.rear - 1 + this.capacity) % this.capacity;
    return this.items[this.rear];
  }
  
  isEmpty(): boolean {
    return this.size === 0;
  }
  
  isFull(): boolean {
    return this.size === this.capacity;
  }
}

Time: O(1) for all operations

Pattern 2: Design Queue with Max Element

Queue that can return maximum element:

class QueueWithMax<T extends number> {
  private queue = new Queue<T>();
  private maxDeque: T[] = []; // Decreasing order
  
  enqueue(item: T): void {
    this.queue.enqueue(item);
    
    // Remove elements smaller than current
    while (this.maxDeque.length > 0 && this.maxDeque[this.maxDeque.length - 1] < item) {
      this.maxDeque.pop();
    }
    
    this.maxDeque.push(item);
  }
  
  dequeue(): T | undefined {
    const item = this.queue.dequeue();
    
    if (item !== undefined && item === this.maxDeque[0]) {
      this.maxDeque.shift();
    }
    
    return item;
  }
  
  getMax(): T | undefined {
    return this.maxDeque.length > 0 ? this.maxDeque[0] : undefined;
  }
  
  peek(): T | undefined {
    return this.queue.peek();
  }
  
  isEmpty(): boolean {
    return this.queue.isEmpty();
  }
}

Time: O(1) amortized for all operations

Key insight: Use deque to maintain maximum element.

Pattern 3: Thread-Safe Queue

Queue with thread safety (simplified):

class ThreadSafeQueue<T> {
  private queue = new Queue<T>();
  private lock = false;
  
  async enqueue(item: T): Promise<void> {
    while (this.lock) {
      await this.wait();
    }
    
    this.lock = true;
    this.queue.enqueue(item);
    this.lock = false;
  }
  
  async dequeue(): Promise<T | undefined> {
    while (this.lock) {
      await this.wait();
    }
    
    this.lock = true;
    const item = this.queue.dequeue();
    this.lock = false;
    return item;
  }
  
  private wait(): Promise<void> {
    return new Promise(resolve => setTimeout(resolve, 1));
  }
  
  peek(): T | undefined {
    return this.queue.peek();
  }
  
  isEmpty(): boolean {
    return this.queue.isEmpty();
  }
}

Note: Simplified version. Real thread-safe queues use proper synchronization primitives.

Pattern 4: Bounded Queue

Queue with maximum capacity:

class BoundedQueue<T> {
  private items: T[] = [];
  private front = 0;
  private rear = -1;
  private capacity: number;
  
  constructor(capacity: number) {
    this.capacity = capacity;
  }
  
  enqueue(item: T): boolean {
    if (this.isFull()) {
      // Option 1: Reject
      return false;
      
      // Option 2: Remove oldest
      // this.dequeue();
    }
    
    this.rear++;
    this.items[this.rear] = item;
    return true;
  }
  
  dequeue(): T | undefined {
    if (this.isEmpty()) return undefined;
    
    const item = this.items[this.front];
    this.front++;
    return item;
  }
  
  peek(): T | undefined {
    return this.isEmpty() ? undefined : this.items[this.front];
  }
  
  isEmpty(): boolean {
    return this.front > this.rear;
  }
  
  isFull(): boolean {
    return this.size() >= this.capacity;
  }
  
  size(): number {
    return this.rear - this.front + 1;
  }
}

Time: O(1) for all operations

Pattern 5: Priority Queue Implementation

Queue where elements are served by priority:

class PriorityQueue<T> {
  private heap: T[] = [];
  private compare: (a: T, b: T) => number;
  
  constructor(compareFn: (a: T, b: T) => number) {
    this.compare = compareFn;
  }
  
  enqueue(item: T): void {
    this.heap.push(item);
    this.bubbleUp(this.heap.length - 1);
  }
  
  dequeue(): T | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();
    
    const top = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.bubbleDown(0);
    return top;
  }
  
  peek(): T | undefined {
    return this.heap[0];
  }
  
  isEmpty(): boolean {
    return this.heap.length === 0;
  }
  
  size(): number {
    return this.heap.length;
  }
  
  private bubbleUp(i: number): void {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.compare(this.heap[i], this.heap[parent]) >= 0) break;
      [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
      i = parent;
    }
  }
  
  private bubbleDown(i: number): void {
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      
      if (left < this.heap.length && this.compare(this.heap[left], this.heap[smallest]) < 0) {
        smallest = left;
      }
      
      if (right < this.heap.length && this.compare(this.heap[right], this.heap[smallest]) < 0) {
        smallest = right;
      }
      
      if (smallest === i) break;
      
      [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
      i = smallest;
    }
  }
}

Time: O(log n) for enqueue/dequeue, O(1) for peek

Note: This is actually a priority queue, not a regular FIFO queue.

When to Use Each Implementation

Linked List Queue

• When: Dynamic size needed, true O(1) operations required
• Advantages: No wasted space, efficient operations
• Disadvantages: Extra memory for pointers

Array Queue

• When: Simple implementation, predictable size
• Advantages: Simple, cache-friendly
• Disadvantages: May waste space, not true O(1) if resizing

Circular Queue

• When: Fixed size, memory constrained
• Advantages: Space efficient, O(1) operations
• Disadvantages: Fixed capacity

Template (Linked List Queue)

class QueueTemplate<T> {
  private head: ListNode<T> | null = null;
  private tail: ListNode<T> | null = null;
  private length = 0;
  
  enqueue(item: T): void {
    const newNode = new ListNode(item);
    
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail!.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    
    this.length++;
  }
  
  dequeue(): T | undefined {
    if (this.isEmpty()) return undefined;
    
    const val = this.head!.val;
    
    if (this.head === this.tail) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head!.next;
      this.head!.prev = null;
    }
    
    this.length--;
    return val;
  }
  
  peek(): T | undefined {
    return this.head?.val;
  }
  
  isEmpty(): boolean {
    return this.length === 0;
  }
  
  size(): number {
    return this.length;
  }
}

Time and Space Complexity

Linked List Implementation

• enqueue: O(1)
• dequeue: O(1)
• peek: O(1)
• isEmpty: O(1)
• size: O(1)
• Space: O(n)

Array Implementation

• enqueue: O(1) amortized
• dequeue: O(1)
• peek: O(1)
• isEmpty: O(1)
• size: O(1)
• Space: O(n)

Circular Queue

• All operations: O(1)
• Space: O(capacity)

Practice Tips

1. Choose implementation - Linked list for dynamic, array for simple, circular for fixed size
2. Handle edge cases - Empty queue, single element, full queue
3. Maintain pointers - Keep head and tail pointers updated correctly
4. Memory management - Clear references when removing nodes
5. Test thoroughly - Test enqueue, dequeue, peek, isEmpty, size
6. Error handling - Return undefined/null for empty queue operations
7. Documentation - Document time/space complexity

Common Mistakes

1. Not handling empty queue - Dequeue/peek from empty queue causes errors
2. Wrong pointer updates - Not updating head/tail correctly
3. Memory leaks - Not clearing references in linked list
4. Single element case - Not handling queue with one element
5. Size tracking - Not updating size counter correctly
6. Circular queue modulo - Wrong modulo calculation
7. Not checking full - Enqueue to full circular queue

Real-World Applications

Queue design is used extensively in:

• Operating Systems - Process scheduling, task queues
• Networking - Packet queues, message queues
• Web Servers - Request queues, connection pools
• Database Systems - Transaction queues
• Game Development - Event queues, AI decision queues
• Distributed Systems - Job queues, message brokers
• Printers - Print job queues
• Streaming - Data stream buffers

Related Concepts

• Stack - LIFO data structure (opposite of queue)
• Deque - Double-ended queue
• Priority Queue - Queue with priority ordering
• Circular Queue - Fixed-size queue with wraparound
• Linked List - Implementation structure for queue

Summary

Designing a queue requires understanding:

• FIFO order - First in, first out principle
• Two ends - Front for dequeue, rear for enqueue
• Implementation choice - Linked list vs array vs circular
• Edge cases - Empty queue, single element, full queue
• Efficiency - O(1) operations for basic queue

Key takeaways:

• Linked list implementation for true O(1) operations
• Handle edge cases (empty, single element)
• Maintain head and tail pointers correctly
• Choose right implementation for use case
• Essential foundation for many algorithms

Mastering queue design will help you implement efficient queues and understand the foundation for BFS, scheduling, and many other algorithms in coding interviews.