Using Queue Patterns

1. Understanding Queue Applications

Application	Description	Use Case	Example
Task Scheduling	Managing tasks in a first-in-first-out (FIFO) order	Job queues, batch processing	`queue.enqueue(task1); queue.dequeue();`
Breadth-First Search (BFS)	Traversing graphs or trees level by level	Shortest path in unweighted graphs	`queue.enqueue(root); while (!queue.isEmpty()) { node = queue.dequeue(); process(node); queue.enqueue(node.left); queue.enqueue(node.right); }`
Buffering	Temporarily hold data before processing	Audio/video streaming, I/O operations	`buffer.enqueue(data); process(buffer.dequeue());`
Resource Management	Managing access to shared resources	Thread pools, connection pooling	`resource = pool.acquire(); pool.release(resource);`

Example: BFS Implementation

const queue = [];
queue.push(root);

while (queue.length > 0) {
  const node = queue.shift();
  console.log(node.value);
  
  if (node.left) queue.push(node.left);
  if (node.right) queue.push(node.right);
}

Note: BFS is ideal for finding the shortest path in unweighted graphs.

2. Implementing Queue with Stacks

Operation	Description	Time Complexity	Space Complexity
Enqueue	Push element to the input stack	O(1)	O(n)
Dequeue	Pop from output stack if not empty, otherwise transfer all elements from input to output stack and then pop	O(1) amortized	O(n)

Example: Queue Implementation Using Two Stacks

class MyQueue {
  constructor() {
    this.input = [];
    this.output = [];
  }

  push(x) {
    this.input.push(x);
  }

  pop() {
    if (this.output.length === 0) {
      while (this.input.length !== 0) {
        this.output.push(this.input.pop());
      }
    }
    return this.output.pop();
  }

  peek() {
    if (this.output.length === 0) {
      while (this.input.length !== 0) {
        this.output.push(this.input.pop());
      }
    }
    return this.output[this.output.length - 1];
  }

  empty() {
    return this.input.length === 0 && this.output.length === 0;
  }
}

const queue = new MyQueue();
queue.push(1);
queue.push(2);
console.log(queue.peek()); // 1
console.log(queue.pop());  // 1
console.log(queue.empty()); // false

3. Implementing Circular Queue

Operation	Description	Time Complexity	Space Complexity
enqueue(element)	Adds an element to the rear of the queue	O(1)	O(1)
dequeue()	Removes and returns the element from the front of the queue	O(1)	O(1)
front()	Returns the element at the front without removing it	O(1)	O(1)
rear()	Returns the element at the rear without removing it	O(1)	O(1)
isEmpty()	Checks if the queue is empty	O(1)	O(1)
isFull()	Checks if the queue is full	O(1)	O(1)

Example: Implementing a Circular Queue in JavaScript

class CircularQueue {
  constructor(size) {
    this.size = size;
    this.queue = new Array(size);
    this.front = -1;
    this.rear = -1;
    this.count = 0;
  }

  enqueue(element) {
    if (this.isFull()) {
      throw new Error("Queue is full");
    }

    this.rear = (this.rear + 1) % this.size;
    this.queue[this.rear] = element;
    this.count++;
  }

  dequeue() {
    if (this.isEmpty()) {
      throw new Error("Queue is empty");
    }

    const element = this.queue[this.front];
    this.front = (this.front + 1) % this.size;
    this.count--;
    return element;
  }

  front() {
    if (this.isEmpty()) {
      throw new Error("Queue is empty");
    }
    return this.queue[this.front];
  }

  rear() {
    if (this.isEmpty()) {
      throw new Error("Queue is empty");
    }
    return this.queue[this.rear];
  }

  isEmpty() {
    return this.count === 0;
  }

  isFull() {
    return this.count === this.size;
  }
}

// Example usage:
const cq = new CircularQueue(5);
cq.enqueue(10);
cq.enqueue(20);
cq.enqueue(30);
console.log(cq.front()); // 10
console.log(cq.rear());  // 30
console.log(cq.dequeue()); // 10

Note: The circular queue uses modulo arithmetic to wrap around the array indices, allowing efficient reuse of space.

4. Implementing Deque

Operation	Description	Time Complexity	Code Example
pushFront()	Adds an element to the front of the deque	O(1)	`deque.pushFront(10);`
pushBack()	Adds an element to the back of the deque	O(1)	`deque.pushBack(20);`
popFront()	Removes and returns the first element	O(1)	`let element = deque.popFront();`
popBack()	Removes and returns the last element	O(1)	`let element = deque.popBack();`
peekFront()	Returns the first element without removing it	O(1)	`let first = deque.peekFront();`
peekBack()	Returns the last element without removing it	O(1)	`let last = deque.peekBack();`

Note: Deque operations are efficient at both ends, making it ideal for scenarios like sliding window problems or managing tasks in a priority queue.

5. Implementing Moving Average

Property	Description	Example
windowSize	Number of elements to consider for the moving average	`5`
dataStream	Array or stream of numerical values	`[10, 20, 30, 40, 50]`
currentAverage	Calculated average of the last `windowSize` elements	`30.0`

Example: Moving Average Implementation

class MovingAverage {
  constructor(windowSize) {
    this.windowSize = windowSize;
    this.queue = [];
    this.sum = 0;
  }

  next(val) {
    if (this.queue.length === this.windowSize) {
      this.sum -= this.queue.shift();
    }
    this.queue.push(val);
    this.sum += val;
    return this.sum / this.queue.length;
  }
}

const ma = new MovingAverage(3);
console.log(ma.next(10)); // 10.0
console.log(ma.next(20)); // 15.0
console.log(ma.next(30)); // 20.0
console.log(ma.next(40)); // 30.0

Note: The queue maintains only the last windowSize elements to efficiently calculate the average.

6. Finding Recent Counter

Property	Description	Usage
recentCounter	Tracks recent requests within a time window	`new RecentCounter()`
ping(timestamp)	Adds a new request at timestamp and returns count of recent requests	`counter.ping(1000)`

Example: Recent Counter Implementation

class RecentCounter {
  constructor() {
    this.queue = [];
  }

  ping(t) {
    this.queue.push(t);
    while (this.queue[0] < t - 3000) {
      this.queue.shift();
    }
    return this.queue.length;
  }
}

const counter = new RecentCounter();
console.log(counter.ping(1000)); // 1
console.log(counter.ping(2000)); // 2
console.log(counter.ping(3000)); // 3
console.log(counter.ping(4000)); // 2

7. Implementing Hit Counter

A hit counter is a data structure that tracks the number of hits (requests) within a specific time window. It's commonly used in web analytics and rate-limiting systems.

Operation	Description	Time Complexity	Space Complexity
hit()	Records a hit at the current timestamp	O(1)	O(n) where n is the number of unique timestamps
getHits()	Returns the number of hits in the last 5 minutes	O(n) where n is the number of unique timestamps	O(n)

Example: Basic Hit Counter Implementation

class HitCounter {
  constructor() {
    this.queue = [];
  }

  hit(timestamp) {
    this.queue.push(timestamp);
  }

  getHits(timestamp) {
    const fiveMinutesAgo = timestamp - 300;
    while (this.queue.length && this.queue[0] <= fiveMinutesAgo) {
      this.queue.shift();
    }
    return this.queue.length;
  }
}

const counter = new HitCounter();
counter.hit(1);
counter.hit(2);
counter.hit(3);
console.log(counter.getHits(4)); // Output: 3

Note: The implementation uses a queue to store timestamps of hits. When getHits is called, it removes outdated timestamps from the front of the queue before returning the count.

8. Solving Dota2 Senate

In the Dota2 Senate problem, we simulate a voting process where each senator can ban another senator from the opposing party. The goal is to determine which party will ultimately win, assuming both parties play optimally.

This problem can be solved efficiently using a queue-based approach to simulate the voting rounds.

Property	Description
senate	A string representing the senators, where 'R' denotes a Radiant senator and 'D' denotes a Dire senator.
winner	The party that wins the voting process, either "Radiant" or "Dire".

Example: Solving Dota2 Senate

function predictPartyVictory(senate) {
    const radiant = [];
    const dire = [];
    
    for (let i = 0; i < senate.length; i++) {
        if (senate[i] === 'R') radiant.push(i);
        else dire.push(i);
    }
    
    let turn = 0;
    while (radiant.length > 0 && dire.length > 0) {
        if (radiant[0] < dire[0]) {
            radiant.push(radiant[0] + senate.length);
        } else {
            dire.push(dire[0] + senate.length);
        }
        radiant.shift();
        dire.shift();
    }
    
    return radiant.length > 0 ? "Radiant" : "Dire";
}

// Example usage:
console.log(predictPartyVictory("RD")); // Output: "Radiant"

Note: The algorithm simulates each round of voting by comparing the earliest senators from each party. The senator with the lower index bans the other and gets requeued for the next round, ensuring optimal play.

9. Implementing Design Snake Game

Example: Basic Snake Game Logic

// Snake game state
let snake = [
  { x: 10, y: 10 },
  { x: 9, y: 10 },
  { x: 8, y: 10 }
];
let food = { x: 15, y: 15 };
let direction = 'RIGHT';
let nextDirection = 'RIGHT';

// Move snake
function moveSnake() {
  const head = { x: snake[0].x, y: snake[0].y };

  switch (nextDirection) {
    case 'UP': head.y--; break;
    case 'DOWN': head.y++; break;
    case 'LEFT': head.x--; break;
    case 'RIGHT': head.x++; break;
  }

  snake.unshift(head);

  // Check if food is eaten
  if (head.x === food.x && head.y === food.y) {
    // Grow snake (don't remove tail)
    generateFood();
  } else {
    snake.pop(); // Remove tail
  }

  direction = nextDirection;
}

// Generate new food position
function generateFood() {
  // Simple random generation (in practice, avoid overlap with snake)
  food.x = Math.floor(Math.random() * 20);
  food.y = Math.floor(Math.random() * 20);
}

Component	Description	Implementation
Snake Body	Array of coordinates representing snake segments	`let snake = [{x: 10, y: 10}, ...]`
Food Position	Single coordinate where food appears	`let food = {x: 15, y: 15}`
Direction	Current movement direction (UP/DOWN/LEFT/RIGHT)	`let direction = 'RIGHT'`
Next Direction	Queued direction change (prevents 180-degree turns)	`let nextDirection = 'RIGHT'`

Note: The snake body is managed as a queue where the head is added to the front and tail removed from the back.

Game Loop Steps

Read input for next direction
Update snake head position based on current direction
Check for food collision
If food eaten, grow snake (don't remove tail)
Otherwise, remove tail segment
Generate new food if eaten
Check for collisions (self or walls)

10. Solving Perfect Squares

Given a positive integer n, return the least number of perfect square numbers that sum to n.

Input	Description	Output
n	Positive integer	Minimum count of perfect squares that sum to `n`

Example:

const numSquares = (n) => {
  const dp = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    dp[i] = i;
    for (let j = 1; j * j <= i; j++) {
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    }
  }
  return dp[n];
};

console.log(numSquares(12)); // Output: 3 (4 + 4 + 4)

Note: This problem can be solved using BFS or dynamic programming. The DP approach uses the fact that any number can be expressed as sum of at most 4 squares (Lagrange's four-square theorem).