Skip to main content

Queue and Monotonic Queue

A queue is a data structure that follows the First-In-First-Out (FIFO) principle. Elements are added at the rear and removed from the front. Queues are commonly used in scenarios where processing order needs to be maintained.

Applications​

  • Breadth-First Search (BFS): Queues are used to explore nodes level by level in graph traversal algorithms.
  • Task Scheduling: Queues manage tasks in operating systems and job scheduling systems.
  • Order Processing: Queues handle order processing in systems where tasks are processed in the order they arrive.

Implementation Using a LinkedList​

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

  enqueue(value) {
    const newNode = new Node(value);
    if (!this.rear) {
      this.front = this.rear = newNode; // Queue is empty
    } else {
      this.rear.next = newNode; // Link new node at the end
      this.rear = newNode; // Update rear
    }
    this.size++;
  }

  dequeue() {
    if (!this.front) return null; // Queue is empty
    const value = this.front.value;
    this.front = this.front.next; // Move front pointer to the next node
    if (!this.front) this.rear = null; // Reset rear if the queue is now empty
    this.size--;
    return value;
  }

  peek() {
    return this.front?.value || null; // Return front value or null if empty
  }

  isEmpty() {
    return this.size === 0; // Check if the queue is empty
  }

  getSize() {
    return this.size; // Return current size of the queue
  }
}

// Example usage:
const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);

console.log(queue.peek()); // 10
console.log(queue.dequeue()); // 10
console.log(queue.getSize()); // 2
console.log(queue.isEmpty()); // false

Queue Implementation​

1. Circular Array:

  • Uses a circular array to avoid shifting elements

2. Dynamic Resizing:

  • Doubles capacity when full
  • Shrinks when size < 25% of capacity
  • Minimum capacity of 10 to avoid excessive resizing

3. Memory Management:

  • Efficiently reuses array space
  • Prevents memory leaks by clearing references

4. Operations:

  • enqueue: O(1) amortized
  • dequeue: O(1) amortized
  • peek: O(1)
  • isEmpty/isFull: O(1)
  • getSize: O(1)
class Queue {
  constructor(capacity = 10) {
    this.capacity = capacity;
    this.items = new Array(capacity);
    this.front = 0;
    this.rear = 0;
    this.size = 0;
  }

  // Add element to queue
  enqueue(element) {
    if (this.isFull()) {
      this.resize();
    }
    this.items[this.rear] = element;
    this.rear = (this.rear + 1) % this.capacity;
    this.size++;
    return this.size;
  }

  // Remove and return front element
  dequeue() {
    if (this.isEmpty()) {
      throw new Error("Queue Underflow");
    }
    const item = this.items[this.front];
    this.items[this.front] = undefined;
    this.front = (this.front + 1) % this.capacity;
    this.size--;

    // Shrink array if it's too sparse
    if (this.size < this.capacity / 4 && this.capacity > 10) {
      this.shrink();
    }
    return item;
  }

  // Return front element without removing
  peek() {
    if (this.isEmpty()) {
      throw new Error("Queue is empty");
    }
    return this.items[this.front];
  }

  // Check if queue is empty
  isEmpty() {
    return this.size === 0;
  }

  // Check if queue is full
  isFull() {
    return this.size === this.capacity;
  }

  // Get current size
  getSize() {
    return this.size;
  }

  // Double the capacity when full
  resize() {
    const newCapacity = this.capacity * 2;
    const newItems = new Array(newCapacity);

    // Copy elements to new array
    for (let i = 0; i < this.size; i++) {
      newItems[i] = this.items[(this.front + i) % this.capacity];
    }

    this.items = newItems;
    this.capacity = newCapacity;
    this.front = 0;
    this.rear = this.size;
  }

  // Halve the capacity when sparse
  shrink() {
    const newCapacity = Math.max(10, Math.floor(this.capacity / 2));
    const newItems = new Array(newCapacity);

    // Copy elements to new array
    for (let i = 0; i < this.size; i++) {
      newItems[i] = this.items[(this.front + i) % this.capacity];
    }

    this.items = newItems;
    this.capacity = newCapacity;
    this.front = 0;
    this.rear = this.size;
  }

  // Clear queue
  clear() {
    this.items = new Array(this.capacity);
    this.front = 0;
    this.rear = 0;
    this.size = 0;
  }

  // Convert queue to array
  toArray() {
    const result = new Array(this.size);
    for (let i = 0; i < this.size; i++) {
      result[i] = this.items[(this.front + i) % this.capacity];
    }
    return result;
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
console.log(queue.dequeue()); // 1
console.log(queue.peek());    // 2

Example Problems​

Monotonic Queue​

A monotonic queue maintains its elements in a specific order, either increasing or decreasing. It is useful for problems where you need to efficiently manage a sliding window or find the maximum or minimum value in a subarray.

Types​

  1. Monotonic Increasing Queue: Maintains elements in increasing order from front to rear. Useful for problems like finding the minimum value in a sliding window.

  2. Monotonic Decreasing Queue: Maintains elements in decreasing order from front to rear. Useful for problems like finding the maximum value in a sliding window.

class MonotonicQueue {
  constructor(isIncreasing = true) {
    this.queue = [];
    this.isIncreasing = isIncreasing;
  }

  // Add element to the queue
  push(num) {
    while (
      this.queue.length > 0 &&
      ((this.isIncreasing && this.queue[this.queue.length - 1] > num) ||
        (!this.isIncreasing && this.queue[this.queue.length - 1] < num))
    ) {
      this.queue.pop();
    }
    this.queue.push(num);
  }

  // Remove element from front of queue
  pop(num) {
    if (this.queue.length > 0 && this.queue[0] === num) {
      this.queue.shift();
    }
  }

  // Get maximum/minimum element
  peek() {
    return this.queue[0];
  }

  size() {
    return this.queue.length;
  }
}

function maxSlidingWindow(nums, k) {
  const mq = new MonotonicQueue(false); // Decreasing for maximum
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    // Add new element
    mq.push(nums[i]);

    // Remove element outside window
    if (i >= k) {
      mq.pop(nums[i - k]);
    }

    // Store result after first window
    if (i >= k - 1) {
      result.push(mq.peek());
    }
  }

  return result;
}

Example Problems​

Monotonic Queue Guide​

For a comprehensive guide on monotonic queues, including templates and explanations, refer to the Monotonic Queue Guide.

Conclusion​

Queues and monotonic queues are essential data structures for managing ordered data and solving problems related to sliding windows and range queries. Understanding how to use these queues effectively can greatly enhance your problem-solving skills in competitive programming and real-world applications.