Pila, cola y lista enlazada

En resumen: Una pila devuelve primero el último elemento añadido (LIFO), una cola devuelve primero el primero añadido (FIFO), y una lista enlazada guarda cada elemento en un nodo con una flecha al siguiente.

Problema

«Deshacer» deshace lo que no es

Un editor de texto guarda las acciones en un array. Ctrl+Z debería deshacer la última, pero deshace la primera:

const actions = [];
actions.push("Texto escrito");
actions.push("Título en negrita");
actions.push("Foto insertada");

// Ctrl+Z: deshacer la última acción.
const undone = actions.shift();
console.log(`Deshecho: ${undone}`);
console.log("Queda:", actions);

Salida

Deshecho: Texto escrito
Queda: [ 'Título en negrita', 'Foto insertada' ]

La corrección es actions.pop(). Pero todo el que toque este código tiene que recordar de qué extremo se quita. Y en la caja de la tienda es al revés: se atiende primero al que llegó primero. ¿Hay una colección que sepa sola de qué extremo?

La idea

Pila: lo último, arriba

Una pila (stack) es como una pila de platos. Pones arriba y sacas de arriba. Lo último que pusiste sale primero. En inglés esto se llama LIFO: last in, first out.

El botón «Atrás» del navegador es una pila:

const history = [];
history.push("Inicio");
history.push("Portátiles");
history.push("Portátil de 14 pulgadas");
console.log(`Ahora: ${history.at(-1)}`);

history.pop();
console.log(`Atrás: ${history.at(-1)}`);
console.log(history);

Salida

Ahora: Portátil de 14 pulgadas
Atrás: Portátiles
[ 'Inicio', 'Portátiles' ]

JavaScript no tiene una clase aparte para la pila: un array es una pila si pones y sacas solo por el final.

• push pone arriba, pop() quita y devuelve el de arriba, y at(-1) solo mira el de arriba.
• Arriba es el final del array. Las dos operaciones son rápidas, porque al final no se mueve nada.
• console.log imprime la pila de abajo arriba: el de arriba es el último.

Más precisamente, para curiosos

• pop() y at(-1) en un array vacío no detienen el programa. Dan undefined:

const history = [];
console.log(history.pop());
console.log(history.at(-1));

Salida

undefined
undefined

Así que comprueba history.length antes de sacar.

Pruébalo

¿Qué queda por deshacer?

¿Qué imprimirá el programa?

const undo = [];
undo.push("fuente");
undo.push("color");
undo.push("tamaño");
undo.pop();
undo.push("subrayado");
while (undo.length > 0) {
  console.log(undo.pop());
}

Respuesta

fuente
color
subrayado

fuente
color
tamaño

subrayado
tamaño
color
fuente

subrayado
color
fuente

Comprobar

La idea

Cola: el primero que llega

Una cola (queue) es como la fila de la caja. Te pones al final, y se atiende al primero. En inglés esto se llama FIFO: first in, first out.

Los trabajos de impresión esperan en una cola:

const printer = [];
printer.push("factura.pdf");
printer.push("contrato.docx");
printer.push("foto.jpg");
console.log(`Siguiente: ${printer[0]}`);

while (printer.length > 0) {
  console.log(`Imprimiendo ${printer.shift()}`);
}
console.log("Cola:", printer);

Salida

Siguiente: factura.pdf
Imprimiendo factura.pdf
Imprimiendo contrato.docx
Imprimiendo foto.jpg
Cola: []

JavaScript no tiene una clase aparte para la cola. Un array se convierte en cola si pones al final y sacas por delante:

• push pone al final, shift quita y devuelve el primero, y printer[0] mira el primero.
• shift en un array vacío da undefined. No detiene el programa.

Pero shift tiene un costo. Mueve todos los demás un lugar hacia delante, como al insertar al principio en la lección sobre arrays. Con pocos trabajos de impresión no lo notas. Con una cola de decenas de miles de elementos, es muchas veces más lento que solo leer en orden. Ahí se usa la lista enlazada de la tarjeta siguiente, que guarda tanto el primer nodo como el último.

Más precisamente, para curiosos

• shift en una cola vacía:

const clients = ["Cliente 1"];
console.log(`Atendido: ${clients.shift()}`);
console.log(clients.shift());

Salida

Atendido: Cliente 1
undefined

• El motor V8 a veces hace rápido shift moviendo el inicio del array en lugar de mover los elementos. Con arrays grandes eso no pasa. No cuentes con ello.

Pruébalo

El siguiente en la caja

La cajera llama al siguiente cliente. ¿Qué método lo saca de la cola?

const checkout = [];
checkout.push("Carlos");
checkout.push("Lucía");
const client = checkout.();
console.log(`Tu turno, ${client}`);

Comprobar

Míralo

Una lista enlazada por dentro

Un array guarda los elementos uno junto a otro en un array. Por eso insertar al principio mueve todos los demás. Hay otra forma: cada elemento está en un objeto aparte que guarda el valor y una flecha al siguiente. Un objeto así se llama nodo (node):

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

Una lista de nodos se llama lista enlazada (linked list). Basta con guardar el primer nodo, head. Cada siguiente lo encuentras siguiendo la flecha next. El último apunta a null.

let head = null;
head = new Node("Café", head);
head = new Node("Leche", head);
head = new Node("Pan", head);

for (let n = head; n !== null; n = n.next) {
  console.log(n.value);
}

Paso a paso, en palabras

1. La lista está vacía: head apunta a null.
2. Un nodo nuevo: next es el head anterior (null), y head pasa al nodo.
3. El segundo nodo apunta al primero. Nada se mueve en la memoria: solo cambian las flechas.
4. El tercer nodo también entra por delante: el último añadido es el primero.
5. n empieza en head e imprime cada nodo.
6. n llega a null: el bucle se detiene.

• Insertar al principio: un nodo nuevo cuyo next apunta al antiguo primero, y head apunta al nuevo. Dos flechas, y no mueves nada.
• Recorrer: empiezas en head y sigues next hasta llegar a null.
• El costo: los nodos no tienen índices. Al quinto elemento llegas pasando por los cuatro primeros.

La idea

El array, y cuál usar cuándo

JavaScript no tiene una lista enlazada lista para usar. Un array puede añadir y quitar en los dos extremos: push y pop al final, unshift y shift al principio:

const route = [];
route.push("Zaragoza");
route.push("Lleida");
route.unshift("Madrid");
route.push("Barcelona");
console.log(route);

route.splice(route.indexOf("Lleida"), 1);
console.log("Después del cambio:", route);
console.log(`De ${route[0]} a ${route.at(-1)}`);

Salida

[ 'Madrid', 'Zaragoza', 'Lleida', 'Barcelona' ]
Después del cambio: [ 'Madrid', 'Zaragoza', 'Barcelona' ]
De Madrid a Barcelona

Cuál usar cuándo:

• Una lista por número: un array. Es la elección habitual.
• Una pila: un array con push y pop.
• Una cola: un array con push y shift, mientras sea pequeña. Una cola grande, con miles de elementos: una lista enlazada como la de la tarjeta anterior, que también guarda el último nodo.

Más precisamente, para curiosos

• unshift es como shift: mueve todos los elementos un lugar, así que es lento al principio de un array grande.
• ¿Por qué un array suele ser más rápido que una lista enlazada, incluso al insertar? Cada nodo es un objeto aparte en algún lugar de la memoria, y el procesador lee más rápido los datos que están uno junto a otro. Un array es justo eso.
• El nodo de esta tarjeta solo tiene next. Una lista así se llama simplemente enlazada.

Pruébalo

Encuentra el error

La función debería contar los nodos. Para la lista Pan → Leche → Café devuelve 2 en lugar de 3. Y con una lista vacía se detiene con TypeError. ¿Qué línea tiene el error?

Elige la línea con el error.

1function count(head) {2 let count = 0;3 let n = head;4 while (n.next !== null) {5 count++;6 n = n.next;7 }8 return count;9}

Comprobar

Ejercicio

Pilas y colas en acción

Resuelve las tareas en tu editor. La colección es un campo privado de la clase, con un # delante.

1. Un tren de juguete. Una clase Train con los métodos addWagon(wagon) y removeWagon(). El tren es una pila: el último vagón enganchado es el primero que se desengancha. removeWagon() devuelve el vagón desenganchado, o null si no hay ninguno. Añade count(). Engancha tres vagones y desengancha dos.

Salida

Desenganchado: Vagón 3
Desenganchado: Vagón 2
Vagones: 1

2. Una línea de autobús. Una clase BusRoute con una cola de paradas y los métodos addStop(stop) y getNextStop(), que devuelve la próxima parada, o null si el recorrido terminó. Añade «Estación Central», «Plaza Mayor» y «Ciudad Universitaria», y recorre la línea.

Salida

Próxima parada: Estación Central
Próxima parada: Plaza Mayor
Próxima parada: Ciudad Universitaria
Fin del recorrido.

3. Un indicador de bolsa. Una clase StockTicker guarda los últimos N precios de una acción. El constructor recibe el símbolo y N. updatePrice(price) añade un precio, y si hay más de N precios, quita el más antiguo. Añade getLastPrice() y average() para los precios guardados. Para SAP con N = 3, pasa los precios 150, 152, 149 y 155. Pista: at(-1) es el último precio. Imprime los precios con dos decimales, con toFixed(2).

Salida

SAP: último precio 155.00 €
Media de los últimos 3: 152.00 €

4. Paréntesis equilibrados. Un editor de código comprueba si los paréntesis (), [] y {} se cierran en el orden correcto. Escribe isBalanced(text) con una pila: con un paréntesis que abre, lo pones en la pila, y con uno que cierra, quitas el de arriba y compruebas que sea del mismo tipo. Al final la pila tiene que estar vacía. Lee tres líneas.

Entrada

(1 + [2 * 3])
(1 + 2]
((5)

Salida

(1 + [2 * 3]) -> sí
(1 + 2] -> no
((5) -> no

5. Tu propia lista enlazada. Una clase MyLinkedList con los nodos de la lección y los métodos add(value) (al final), remove(value), contains(value), size() y toString(). En remove, busca el nodo anterior al que buscas y redirige su next. Comprueba aparte el caso en que se quita el primero.

Salida

[Factura, Informe, Reunión]
Contiene Informe: true
Después de quitar: [Factura, Reunión]
Tamaño: 2

Más tareas

• Deshacer y rehacer. Guarda dos pilas: undo y redo. Una acción nueva va a undo y vacía redo. «Deshacer» pasa el de arriba de undo a redo, y «Rehacer» lo devuelve.
• Palabras al revés. Lee una frase e imprímela con las palabras en orden inverso, pasando por una pila: «Hoy es viernes» se convierte en «viernes es Hoy».
• Dos cajas. Los clientes llegan uno a uno y van a la caja con la fila más corta. Imprime quién fue atendido en qué caja.
• Invierte la lista enlazada. Añade a MyLinkedList un método reverse() que dé la vuelta a las flechas sin crear nodos nuevos.

• Una cola rápida. Añade a MyLinkedList un campo para el último nodo, para que add al final también sea rápido. Ahora es una cola sin shift: add al final, y quitar el primero por delante.

Test

Ponte a prueba

1. Pones A en una pila, luego B, luego C. ¿Cuál sale primero con pop?

CAB

2. ¿Cuál es un trabajo para una cola?

Deshacer la última acciónEl botón «Atrás» del navegadorLos trabajos de impresión, que se imprimen en el orden en que llegan

3. ¿Qué devuelve shift() en un array vacío?

undefinedEl programa se detiene con un error0

4. ¿Por qué insertar al principio de una lista enlazada es rápido?

Porque la lista se ordena solaPorque se crea un nodo nuevo y se mueven dos flechas, sin tocar los demás elementosPorque los elementos están uno junto a otro en la memoria

5. ¿Qué es lento en una lista enlazada?

Añadir al principioQuitar el primer elementoObtener un elemento por su número, por ejemplo el quinientos

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: Polimorfismo · Interfaces sin interface · Excepciones · Arrays: push, splice y sort
• Continúa en: Códigos hash y funciones hash · Clases anidadas y datos · Command · Complejidad en espacio
• Ejercicios sobre el tema: Colecciones