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 una lista. Ctrl+Z debería deshacer la última, pero deshace la primera:

List<String> actions = new ArrayList<>();
actions.add("Texto escrito");
actions.add("Título en negrita");
actions.add("Foto insertada");

// Ctrl+Z: deshacer la última acción.
String undone = actions.remove(0);
System.out.println("Deshecho: " + undone);
System.out.println("Queda: " + actions);

Salida

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

La corrección es actions.remove(actions.size() - 1). 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:

Deque<String> history = new ArrayDeque<>();
history.push("Inicio");
history.push("Portátiles");
history.push("Portátil de 14 pulgadas");
System.out.println("Ahora: " + history.peek());

history.pop();
System.out.println("Atrás: " + history.peek());
System.out.println(history);

Salida

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

• push pone arriba, pop quita y devuelve el de arriba, y peek solo mira el de arriba.
• Deque es la interfaz y ArrayDeque es la clase. Las dos están en java.util.
• println imprime la pila de arriba abajo.

Más precisamente, para curiosos

• pop en una pila vacía detiene el programa con java.util.NoSuchElementException. peek en una pila vacía devuelve null.
• Java también tiene una clase más antigua, Stack. Funciona, pero la documentación de Java recomienda ArrayDeque:

Stack<String> stack = new Stack<>();
stack.push("Google");
stack.push("Apple");
stack.push("Microsoft");
System.out.println("Arriba: " + stack.peek());
while (!stack.isEmpty()) {
    System.out.println("Sacado: " + stack.pop());
}

Salida

Arriba: Microsoft
Sacado: Microsoft
Sacado: Apple
Sacado: Google

Pruébalo

¿Qué queda por deshacer?

¿Qué imprimirá el programa?

Deque<String> undo = new ArrayDeque<>();
undo.push("fuente");
undo.push("color");
undo.push("tamaño");
undo.pop();
undo.push("subrayado");
while (!undo.isEmpty()) {
    System.out.println(undo.pop());
}

Respuesta

subrayado
tamaño
color
fuente

subrayado
color
fuente

fuente
color
subrayado

fuente
color
tamaño

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:

Queue<String> printer = new ArrayDeque<>();
printer.offer("factura.pdf");
printer.offer("contrato.docx");
printer.offer("foto.jpg");
System.out.println("Siguiente: " + printer.peek());

while (!printer.isEmpty()) {
    System.out.println("Imprimiendo " + printer.poll());
}
System.out.println("Cola: " + printer);

Salida

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

• offer pone al final, poll quita y devuelve el primero, y peek mira el primero.
• El tipo es la interfaz Queue, y la clase vuelve a ser ArrayDeque. Puede hacer las dos cosas: ser una pila y ser una cola. El nombre viene de double-ended queue, una cola con dos extremos.
• poll y peek en una cola vacía devuelven null.

Más precisamente, para curiosos

• También existen add, remove() y element(). Hacen lo mismo, pero en una cola vacía lanzan una excepción en lugar de devolver null.
• En ejemplos antiguos la cola es una LinkedList. Eso también funciona, porque LinkedList también implementa Queue:

Queue<String> clients = new LinkedList<>();
clients.offer("Cliente 1");
clients.offer("Cliente 2");
System.out.println("Atendido: " + clients.poll());
System.out.println("Esperando: " + clients);

Salida

Atendido: Cliente 1
Esperando: [Cliente 2]

• ArrayDeque no acepta null como elemento. Si no, poll no tendría forma de decir «está vacía».

Pruébalo

El siguiente en la caja

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

Queue<String> checkout = new ArrayDeque<>();
checkout.offer("Carlos");
checkout.offer("Lucía");
String next = checkout.();
System.out.println("Tu turno, " + next);

Comprobar

Míralo

Una lista enlazada por dentro

ArrayList 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 {
    String value;
    Node next;

    Node(String value, Node 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.

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

for (Node n = head; n != null; n = n.next) {
    System.out.println(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

LinkedList, y cuál usar cuándo

Java tiene una lista enlazada lista para usar: LinkedList. Implementa tanto List como Deque, así que tiene add, get y remove, pero también addFirst, addLast y getFirst:

LinkedList<String> route = new LinkedList<>();
route.add("Zaragoza");
route.add("Lleida");
route.addFirst("Madrid");
route.addLast("Barcelona");
System.out.println(route);

route.remove("Lleida");
System.out.println("Después del cambio: " + route);
System.out.println("De " + route.getFirst() + " a " + route.getLast());

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: ArrayList. Es la elección habitual.
• Una pila o una cola: ArrayDeque.
• LinkedList: pocas veces. Sirve para las dos cosas, pero suele ser más lenta que ellas.

Más precisamente, para curiosos

• ¿Por qué pierde LinkedList, 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. El array detrás de ArrayList y ArrayDeque es justo eso. En la práctica, LinkedList gana solo si insertas o quitas a menudo en el medio con un iterador que ya llegó allí.
• LinkedList guarda flechas en las dos direcciones, al siguiente y al anterior. Por eso getLast y removeLast también son rápidos. El nodo de esta tarjeta solo tiene next. Una lista así se llama simplemente enlazada.

Pruébalo

Encuentra el error

El método 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 NullPointerException. ¿Qué línea tiene el error?

Elige la línea con el error.

1static int count(Node head) {2 int count = 0;3 Node 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 private de la clase.

1. Un tren de juguete. Una clase Train con los métodos addWagon(String 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(String 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(double 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: Deque tiene peekLast().

Salida

SAP: último precio 155.0 €
Media de los últimos 3: 152.0 €

4. Paréntesis equilibrados. Un editor de código comprueba si los paréntesis (), [] y {} se cierran en el orden correcto. Escribe isBalanced(String 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(String value) (al final), remove(String value), contains(String 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.

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 poll() en una ArrayDeque vacía?

nullLanza NoSuchElementException0

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 · Excepciones · Listas
• Continúa en: Códigos hash y funciones hash · Clases anidadas · Command · Complejidad en espacio
• Ejercicios sobre el tema: Colecciones