Queues

What is a Queue?

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. Think of it like a line of people waiting - the first person to join the line is the first one to be served. Elements are added at the back (enqueue) and removed from the front (dequeue).

Queues are essential for managing tasks in order, handling requests, and implementing breadth-first search algorithms.

Queue Operations

Queue Implementation Using Array

class Queue {
  constructor() {
    this.items = [];
  }

  // Add element to rear - O(1)
  enqueue(element) {
    this.items.push(element);
  }

  // Remove element from front - O(n) due to array shift
  dequeue() {
    if (this.isEmpty()) {
      throw new Error('Queue is empty');
    }
    return this.items.shift();  // O(n) operation!
  }

  // Get front element - O(1)
  front() {
    if (this.isEmpty()) {
      throw new Error('Queue is empty');
    }
    return this.items[0];
  }

  // Check if empty - O(1)
  isEmpty() {
    return this.items.length === 0;
  }

  // Get size - O(1)
  size() {
    return this.items.length;
  }

  // Print queue
  print() {
    console.log(this.items.join(' ← '));
  }
}

// Usage
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.print();  // 1 ← 2 ← 3

console.log(queue.dequeue());  // 1
console.log(queue.front());    // 2
queue.print();  // 2 ← 3

Optimized Queue Using Object (O(1) dequeue)

class OptimizedQueue {
  constructor() {
    this.items = {};
    this.frontIndex = 0;
    this.backIndex = 0;
  }

  // Enqueue - O(1)
  enqueue(element) {
    this.items[this.backIndex] = element;
    this.backIndex++;
  }

  // Dequeue - O(1)
  dequeue() {
    if (this.isEmpty()) {
      throw new Error('Queue is empty');
    }
    
    const item = this.items[this.frontIndex];
    delete this.items[this.frontIndex];
    this.frontIndex++;
    
    return item;
  }

  // Front - O(1)
  front() {
    if (this.isEmpty()) {
      throw new Error('Queue is empty');
    }
    return this.items[this.frontIndex];
  }

  isEmpty() {
    return this.backIndex === this.frontIndex;
  }

  size() {
    return this.backIndex - this.frontIndex;
  }

  print() {
    const values = [];
    for (let i = this.frontIndex; i < this.backIndex; i++) {
      values.push(this.items[i]);
    }
    console.log(values.join(' ← '));
  }
}

// This is much more efficient for large queues!

Queue Implementation Using Linked List

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

class LinkedQueue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.length = 0;
  }

  // Enqueue - O(1)
  enqueue(data) {
    const newNode = new Node(data);
    
    if (this.isEmpty()) {
      this.front = this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }
    
    this.length++;
  }

  // Dequeue - O(1)
  dequeue() {
    if (this.isEmpty()) {
      throw new Error('Queue is empty');
    }
    
    const dequeuedData = this.front.data;
    this.front = this.front.next;
    
    if (this.front === null) {
      this.rear = null;
    }
    
    this.length--;
    return dequeuedData;
  }

  peek() {
    if (this.isEmpty()) {
      throw new Error('Queue is empty');
    }
    return this.front.data;
  }

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

  size() {
    return this.length;
  }
}

Circular Queue

A circular queue is a linear data structure that connects the end back to the beginning, forming a circle. This efficiently uses space when implementing a queue with a fixed size array.

class CircularQueue {
  constructor(capacity) {
    this.items = new Array(capacity);
    this.capacity = capacity;
    this.front = -1;
    this.rear = -1;
    this.currentSize = 0;
  }

  // Check if full - O(1)
  isFull() {
    return this.currentSize === this.capacity;
  }

  // Check if empty - O(1)
  isEmpty() {
    return this.currentSize === 0;
  }

  // Enqueue - O(1)
  enqueue(element) {
    if (this.isFull()) {
      throw new Error('Queue is full');
    }
    
    // First element
    if (this.front === -1) {
      this.front = 0;
    }
    
    // Circular increment
    this.rear = (this.rear + 1) % this.capacity;
    this.items[this.rear] = element;
    this.currentSize++;
  }

  // Dequeue - O(1)
  dequeue() {
    if (this.isEmpty()) {
      throw new Error('Queue is empty');
    }
    
    const item = this.items[this.front];
    
    // Reset if last element
    if (this.front === this.rear) {
      this.front = this.rear = -1;
    } else {
      // Circular increment
      this.front = (this.front + 1) % this.capacity;
    }
    
    this.currentSize--;
    return item;
  }

  peek() {
    if (this.isEmpty()) {
      throw new Error('Queue is empty');
    }
    return this.items[this.front];
  }

  size() {
    return this.currentSize;
  }
}

// Usage
const cq = new CircularQueue(5);
cq.enqueue(1);
cq.enqueue(2);
cq.enqueue(3);
console.log(cq.dequeue());  // 1
cq.enqueue(4);
cq.enqueue(5);
cq.enqueue(6);  // Now using the circular space!

Priority Queue

A priority queue is a special type of queue where each element has a priority. Elements with higher priority are dequeued before elements with lower priority.

class PriorityQueue {
  constructor() {
    this.items = [];
  }

  // Enqueue with priority - O(n) for simple implementation
  enqueue(element, priority) {
    const queueElement = { element, priority };
    
    // Find correct position based on priority
    let added = false;
    for (let i = 0; i < this.items.length; i++) {
      if (queueElement.priority < this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break;
      }
    }
    
    if (!added) {
      this.items.push(queueElement);
    }
  }

  // Dequeue highest priority - O(1)
  dequeue() {
    if (this.isEmpty()) {
      throw new Error('Queue is empty');
    }
    return this.items.shift().element;
  }

  front() {
    if (this.isEmpty()) {
      throw new Error('Queue is empty');
    }
    return this.items[0].element;
  }

  isEmpty() {
    return this.items.length === 0;
  }

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

  print() {
    console.log(this.items.map(item => 
      `${item.element}(p:${item.priority})`
    ).join(' ← '));
  }
}

// Usage
const pq = new PriorityQueue();
pq.enqueue('Low priority task', 3);
pq.enqueue('High priority task', 1);
pq.enqueue('Medium priority task', 2);
pq.print();  // High priority task(p:1) ← Medium priority task(p:2) ← Low priority task(p:3)
console.log(pq.dequeue());  // 'High priority task'

Common Queue Problems

1. Implement Stack Using Queues

class StackUsingQueues {
  constructor() {
    this.q1 = [];
    this.q2 = [];
  }

  push(x) {
    // Add to q2
    this.q2.push(x);
    
    // Move all from q1 to q2
    while (this.q1.length > 0) {
      this.q2.push(this.q1.shift());
    }
    
    // Swap q1 and q2
    [this.q1, this.q2] = [this.q2, this.q1];
  }

  pop() {
    if (this.empty()) {
      throw new Error('Stack is empty');
    }
    return this.q1.shift();
  }

  top() {
    if (this.empty()) {
      throw new Error('Stack is empty');
    }
    return this.q1[0];
  }

  empty() {
    return this.q1.length === 0;
  }
}

2. Generate Binary Numbers from 1 to N

function generateBinaryNumbers(n) {
  const result = [];
  const queue = [];
  
  queue.push('1');
  
  for (let i = 0; i < n; i++) {
    const front = queue.shift();
    result.push(front);
    
    // Generate next binary numbers
    queue.push(front + '0');
    queue.push(front + '1');
  }
  
  return result;
}

console.log(generateBinaryNumbers(5));
// ['1', '10', '11', '100', '101']

3. First Non-Repeating Character in Stream

function firstNonRepeating(stream) {
  const queue = [];
  const charCount = {};
  const result = [];
  
  for (let char of stream) {
    // Update count
    charCount[char] = (charCount[char] || 0) + 1;
    queue.push(char);
    
    // Remove repeating characters from front
    while (queue.length > 0 && charCount[queue[0]] > 1) {
      queue.shift();
    }
    
    // First non-repeating or -1
    result.push(queue.length > 0 ? queue[0] : '-1');
  }
  
  return result;
}

console.log(firstNonRepeating('aabcbc'));
// ['a', '-1', 'b', 'b', 'b', 'c']

Real-World Applications

Queue vs Stack Comparison