Pila y cola en JavaScript

Problema

El correo del pedido sale vacío

La tienda envía un correo por cada pedido a partir de una plantilla: Pedido {order}: [{items}] (total {total} €). Las plantillas se escriben a mano, y a veces un paréntesis no se cierra, o se cierra con el que no es. Entonces el programa de correo no rellena nada, y el cliente recibe un correo vacío.

Antes de enviar, quieres decir: «la plantilla está bien» o «error en la posición 24». Contar los paréntesis no basta: en [{items}) hay dos abiertos y dos cerrados, y el error está justo ahí.

En la lección «Pila, cola y lista enlazada» la pila y la cola ya venían hechas: el arreglo. Aquí las construyes tú, para ver cuánto cuesta cada operación y dónde está la trampa.

La idea

Una pila sobre un arreglo que crece

Los paréntesis se cierran en orden inverso: el último abierto se cierra primero. Eso es una pila: pones encima y quitas de arriba.

Por dentro, una pila es un arreglo y un contador size:

push escribe en el índice size y aumenta el contador;
pop disminuye el contador y devuelve lo que hay ahí;
cuando el arreglo se llena, se hace el doble de grande, como en la complejidad amortizada.

class CharStack {
  constructor() {
    this.items = new Array(4);
    this.size = 0;
  }

  push(c) {
    if (this.size === this.items.length) {
      const bigger = new Array(this.size * 2);
      for (let i = 0; i < this.size; i++) bigger[i] = this.items[i];
      this.items = bigger;
    }
    this.items[this.size] = c;
    this.size++;
  }

  pop() {
    if (this.size === 0) throw new Error("pila vacía");
    this.size--;
    return this.items[this.size];
  }

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

Tanto push como pop trabajan solo con el final del arreglo. Nada se mueve, así que las dos son O(1) (push es O(1) en promedio, por el crecimiento).

En JavaScript el arreglo ya crece solo, y push y pop() son exactamente el push y el pop de la pila. Aquí el arreglo se duplica a mano, para que veas lo que hace el motor por ti.

Míralo

Comprobar la plantilla

Recorres la plantilla carácter a carácter:

un paréntesis que abre va a la pila;
uno que cierra toma lo de arriba de la pila y comprueba que sea del mismo tipo;
si la pila está vacía al llegar un paréntesis que cierra, o no está vacía al final, la plantilla está mal.

function firstError(text) {
  const opened = new CharStack();
  for (let i = 0; i < text.length; i++) {
    const c = text[i];
    if ("([{".includes(c)) {
      opened.push(c);
    } else if (")]}".includes(c)) {
      if (opened.isEmpty()) return i;
      if ("([{".indexOf(opened.pop()) !== ")]}".indexOf(c)) return i;
    }
  }
  return opened.isEmpty() ? -1 : text.length;
}

const templates = [
  "Pedido {order}: [{items}] (total {total} €)",
  "Pedido {order}: [{items}) (total {total} €)",
  "Pedido {order}: [{items}] (total {total} €",
];
for (const t of templates) {
  const at = firstError(t);
  console.log(at < 0 ? "OK" : `error en la posición ${at}`);
}

OK
error en la posición 24
error en la posición 42

En la segunda plantilla llega ) cuando arriba de la pila está [: error en la posición 24. En la tercera, ( nunca se cierra y el error está al final, en la posición 42, la longitud del texto.

Más precisamente, para curiosos

Un comprobador de JSON de verdad también salta los paréntesis dentro de texto entre comillas: "[1" no abre nada. Entonces la pila guarda además «ahora estoy dentro de un texto». Lo mismo vale para las etiquetas HTML: la pila guarda los nombres de las etiquetas abiertas, y </div> debe encontrar div arriba.

Pruébalo

Predice la salida

console.log(firstError("({total)}"));

Respuesta

-1

Problema

La cola de entregas de la mañana

A las 8 de la mañana hay 10 000 solicitudes de entrega esperando en el sistema. Los mensajeros las toman una a una, la más antigua primero: eso es una cola. Alguien la escribió con una lista normal:

const jobs = [];
for (let id = 1; id <= 10_000; id++) {
  jobs.push(`#${id}`);
}
let done = 0;
while (jobs.length > 0) {
  const job = jobs.shift();
  done++;
}
console.log(`procesados: ${done}`);

procesados: 10000

Parece inocente, pero jobs.shift() quita del índice 0 de un arreglo. Todos los que van después del primero avanzan un lugar. Con 10 000 en espera, la primera salida mueve 9999, la segunda 9998… En total son unos 50 millones de movimientos solo para sacar cada una una vez.

La idea

Un búfer circular: se mueve head, no los pedidos

No muevas los pedidos. Mueve el puntero al primero.

head es el índice del primer pedido, y size es cuántos esperan.
Una salida lee items[head], deja libre el lugar y avanza head uno. Nadie más se mueve.
El pedido nuevo va a tail = (head + size) % lugares. El resto de la división convierte el arreglo en un círculo: después del último lugar viene el primero. Los lugares libres de delante, liberados por las salidas, se usan otra vez.
Cuando todos los lugares están ocupados, grow crea un arreglo del doble de tamaño y copia los pedidos en el orden de la cola, desde head. Después head es 0.

Un arreglo así, cuyo final continúa desde el principio, se llama búfer circular.

class JobQueue {
  constructor() {
    this.items = new Array(4).fill(null);
    this.head = 0;
    this.size = 0;
  }

  enqueue(job) {
    if (this.size === this.items.length) this.grow();
    const tail = (this.head + this.size) % this.items.length;
    this.items[tail] = job;
    this.size++;
  }

  dequeue() {
    if (this.size === 0) {
      throw new Error("cola vacía");
    }
    const job = this.items[this.head];
    this.items[this.head] = null;
    this.head = (this.head + 1) % this.items.length;
    this.size--;
    return job;
  }

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

  grow() {
    const n = this.items.length;
    const bigger = new Array(n * 2).fill(null);
    for (let i = 0; i < this.size; i++) {
      bigger[i] = this.items[(this.head + i) % n];
    }
    this.items = bigger;
    this.head = 0;
  }
}

Para que veas lo que hay dentro, la clase tiene también un método para imprimir:

toString() {
  const shown = this.items.map((s) => s ?? "-").join(", ");
  return `[${shown}] head=${this.head}`;
}

Míralo

head, tail y la vuelta al principio

Entran tres pedidos, salen dos, y entran otros tres. El último de ellos no va después del final del arreglo, sino al índice 0. Entonces el arreglo está lleno, y el séptimo pedido lo hace crecer:

class JobQueue {
  constructor() {
    this.items = new Array(4).fill(null);
    this.head = 0;
    this.size = 0;
  }

  enqueue(job) {
    if (this.size === this.items.length) this.grow();
    const tail = (this.head + this.size) % this.items.length;
    this.items[tail] = job;
    this.size++;
  }

  dequeue() {
    if (this.size === 0) {
      throw new Error("cola vacía");
    }
    const job = this.items[this.head];
    this.items[this.head] = null;
    this.head = (this.head + 1) % this.items.length;
    this.size--;
    return job;
  }

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

  grow() {
    const n = this.items.length;
    const bigger = new Array(n * 2).fill(null);
    for (let i = 0; i < this.size; i++) {
      bigger[i] = this.items[(this.head + i) % n];
    }
    this.items = bigger;
    this.head = 0;
  }
}

Paso a paso, en palabras

Una cola de entregas en un arreglo con 4 lugares. head es el índice del primer pedido, size es cuántos esperan.
enqueue: el pedido nuevo va a (head + size) % 4. Tres pedidos ocupan los lugares 0, 1 y 2.
dequeue toma el pedido que está en head y avanza head. Nadie más se mueve: #103 se queda en el lugar 2.
#104: (2 + 1) % 4 = 3, el último lugar del arreglo.
#105: (2 + 2) % 4 = 0. El final del arreglo vuelve al principio y los lugares libres de delante se usan otra vez.
#106 va al lugar 1. Ya están ocupados 4 de 4: el arreglo está lleno y el primero de la cola está en el lugar 2.
#107 ya no cabe. grow crea 8 lugares y copia en el orden de la cola, desde head: #103, #104, #105, #106. head pasa a ser 0.
#107 va al lugar 4. Una copia por pedido al crecer y ninguna al sacar por delante.

const q = new JobQueue();
for (let id = 101; id <= 103; id++) q.enqueue(`#${id}`);
console.log(String(q));
console.log(`entrega: ${q.dequeue()}`);
console.log(`entrega: ${q.dequeue()}`);
console.log(String(q));
for (let id = 104; id <= 106; id++) q.enqueue(`#${id}`);
console.log(String(q));
q.enqueue("#107");
console.log(String(q));

[#101, #102, #103, -] head=0
entrega: #101
entrega: #102
[-, -, #103, -] head=2
[#105, #106, #103, #104] head=2
[#103, #104, #105, #106, #107, -, -, -] head=0

Mira la tercera línea de la salida: [#105, #106, #103, #104] head=2. El primero de la cola es #103, en el índice 2, y #105 y #106 están delante, porque allí había lugares libres. El orden en el arreglo no es el orden de la cola. Por eso grow no copia uno a uno.

Pruébalo

¿Adónde van #205 y #206?

const q = new JobQueue();
for (let id = 201; id <= 204; id++) q.enqueue(`#${id}`);
q.dequeue();
q.dequeue();
q.dequeue();
q.enqueue("#205");
q.enqueue("#206");
console.log(String(q));

Respuesta

[#205, #206, -, #204] head=3

[#204, #205, #206, -] head=0

[-, -, -, #204, #205, #206, -, -] head=3

Pruébalo

Completa

El pedido nuevo va al lugar:

const tail = (this.head + this.size) % ;

La idea

Cuánto cuesta

Cuenta los movimientos de solicitudes ya escritas: las copias al crecer y el avance al sacar del índice 0. Las dos colas empiezan con 4 lugares y se duplican. Entran 10 000 solicitudes y después salen todas:

function shiftMoves(n) {
  let items = new Array(4);
  let size = 0;
  let moves = 0;
  for (let job = 1; job <= n; job++) {
    if (size === items.length) {
      const bigger = new Array(size * 2);
      for (let i = 0; i < size; i++) bigger[i] = items[i];
      moves += size;
      items = bigger;
    }
    items[size++] = job;
  }
  while (size > 0) {
    for (let i = 1; i < size; i++) {
      items[i - 1] = items[i];
      moves++;
    }
    size--;
  }
  return moves;
}

function ringMoves(n) {
  let items = new Array(4);
  let head = 0;
  let size = 0;
  let moves = 0;
  for (let job = 1; job <= n; job++) {
    if (size === items.length) {
      const bigger = new Array(size * 2);
      for (let i = 0; i < size; i++) {
        bigger[i] = items[(head + i) % items.length];
        moves++;
      }
      items = bigger;
      head = 0;
    }
    items[(head + size) % items.length] = job;
    size++;
  }
  while (size > 0) {
    head = (head + 1) % items.length;
    size--;
  }
  return moves;
}

for (const n of [1000, 10000]) {
  console.log(`${n}: lista ${shiftMoves(n)}, anillo ${ringMoves(n)}`);
}

1000: lista 500520, anillo 1020
10000: lista 50011380, anillo 16380

Ejecútalo, también hasta 100 000:

Lista: quitar en el índice 0 O(n²)
Búfer circular O(n)

Algoritmo	n = 10	n = 1000	n = 10.000	n = 100.000
Lista: quitar en el índice 0	57	500.520	50.011.380	≈ 5.001.138.000
Búfer circular	12	1020	16.380	131.068

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

Con 10 000 solicitudes la lista hace 50 011 380 movimientos, y el anillo 16 380, todos por el crecimiento. Una salida del índice 0 es O(n), así que n salidas son O(n²). En el anillo una salida es O(1), y añadir es O(1) en promedio, como en la pila.

Más precisamente, para curiosos

Así es en los lenguajes:

Java: ArrayDeque es un búfer circular: un arreglo elements y los índices head y tail. Siempre queda un lugar libre, para distinguir «vacío» (head == tail) de «lleno», así que el arreglo empieza con 17 lugares para 16 elementos. Cuando se llena, un arreglo pequeño crece algo más del doble, y uno grande un 50 %.
C#: Queue<T> es un búfer circular con _array, _head, _tail y _size. Empieza con 4 lugares y duplica el arreglo cuando se llena. Stack<T> es un arreglo que también se duplica.
Python: collections.deque no es un búfer circular, sino una lista enlazada de bloques de 64 lugares. Por eso los dos extremos son O(1). list.pop(0) es O(n), exactamente como en el problema.
JavaScript: no hay una cola incorporada. shift() mueve todos los elementos del arreglo. V8 a veces lo hace rápido moviendo el inicio del arreglo en vez de mover los elementos, pero no con arreglos grandes, y no está prometido. Para una cola grande escribes un anillo como este, o una cola de nodos.

Algunos anillos guardan tail en vez de size, y otros guardan los dos. Es solo otra manera de escribir lo mismo: tail = (head + size) % lugares.

Pruébalo

Encuentra el error

Alguien escribió grow de forma más corta. Los pedidos de antes del crecimiento salen en orden, y los de después, mezclados:

grow() {
  const n = this.items.length;
  const bigger = new Array(n * 2).fill(null);
  for (let i = 0; i < this.size; i++) {
    bigger[i] = this.items[i];
  }
  this.items = bigger;
  this.head = 0;
}

const q = new JobQueue();
for (let id = 101; id <= 103; id++) q.enqueue(`#${id}`);
q.dequeue();
q.dequeue();
for (let id = 104; id <= 107; id++) q.enqueue(`#${id}`);
const order = [];
while (!q.isEmpty()) order.push(q.dequeue());
console.log(order.join(" "));

#105 #106 #103 #104 #107

¿En qué línea está el error?

Elige la línea con el error.

Ejercicio

Las últimas 5 líneas del registro

Resuelve la tarea en tu editor.

Las últimas 5 líneas. El servidor de la tienda escribe una línea en el registro por cada acción. Cuando hay un error quieres ver las últimas 5 líneas, no todo el registro. Escribe LastLines con un anillo de 5 lugares que nunca crece: mientras haya sitio, una línea va a (head + size) % 5; cuando está lleno, la línea nueva sobrescribe la más antigua (en head), y head avanza. Un método lines() devuelve las líneas de la más antigua a la más nueva. Dale las ocho líneas:

09:00 inicio de sesión: maría
09:02 carrito: +2
09:03 pago: 48 €
09:05 cierre de sesión: maría
09:07 inicio de sesión: lucía
09:08 búsqueda: café
09:09 carrito: +1
09:11 pago: 12 €

Las últimas 5:
09:05 cierre de sesión: maría
09:07 inicio de sesión: lucía
09:08 búsqueda: café
09:09 carrito: +1
09:11 pago: 12 €

Más tareas

Paréntesis y etiquetas. Amplía la comprobación de la plantilla a las etiquetas <b>…</b> y <i>…</i>: la pila guarda los nombres de las etiquetas abiertas.
Una cola que se encoge. Si después de la hora punta de la mañana esperan 10 solicitudes en una cola con 8192 lugares, la memoria queda vacía. Haz que la cola reduzca su arreglo a la mitad cuando esté llena menos de una cuarta parte. ¿Por qué no cuando esté llena menos de la mitad?
Una pila con dos colas. Construye una pila usando solo dos de tus colas. ¿Cuánto cuesta pop?

Test

Ponte a prueba

1. ¿Por qué una pila comprueba los paréntesis, en vez de contar simplemente los que abren y los que cierran?Porque contar es más lentoPorque el último paréntesis abierto debe cerrarse primero, y un número no sabe cuál fue el últimoPorque contar no funciona con más de 10 paréntesis

2. Una cola con 10 000 en espera está en una lista normal, y cada salida es del índice 0. ¿Cuántos movimientos cuesta una salida por delante?Más o menos tantos como esperan detrás del primero: todos avanzan un lugarNingunoUno

3. Un búfer circular con 8 lugares: head = 6, size = 3. ¿A qué lugar va el pedido nuevo?Al 9Al 0Al 1

4. El búfer circular está lleno y tiene que crecer. ¿Por qué grow no puede copiar sin más items[0], items[1]… al arreglo nuevo?Porque el primero de la cola está en head, no en 0; la copia debe hacerse en el orden de la cola, desde headSí puede: los lugares son los mismosPorque el arreglo nuevo es más pequeño

Pila y cola

Cookies