Colas

¿Qué es una cola?

Una cola es una estructura de datos lineal que sigue el principio First In, First Out (FIFO). Piensa en una fila de personas: la primera en llegar es la primera en ser atendida. Los elementos se agregan al final (enqueue) y se eliminan del frente (dequeue).

Las colas son esenciales para gestionar tareas en orden, manejar solicitudes e implementar BFS.

Operaciones de la cola

Implementación de cola usando 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

Cola optimizada con objeto (dequeue O(1))

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!

Implementación de cola usando lista enlazada

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

Cola circular

Una cola circular conecta el final con el inicio, formando un círculo. Esto aprovecha el espacio al implementar una cola con un array de tamaño fijo.

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!

Cola de prioridad

Una cola de prioridad es un tipo especial de cola donde cada elemento tiene una prioridad. Los elementos con mayor prioridad salen antes que los de menor prioridad.

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'

Problemas comunes de colas

1. Implementar una pila usando colas

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. Generar números binarios de 1 a 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. Primer carácter no repetido en un flujo

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

Aplicaciones reales

Comparación cola vs pila