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:

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

# Ctrl+Z: deshacer la última acción.
undone = actions.pop(0)
print("Deshecho:", undone)
print("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:

history = []
history.append("Inicio")
history.append("Portátiles")
history.append("Portátil de 14 pulgadas")
print("Ahora:", history[-1])

history.pop()
print("Atrás:", history[-1])
print(history)

Salida

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

Python no tiene una clase aparte para la pila: una lista es una pila si pones y sacas solo por el final.

• append pone arriba, pop() sin índice quita y devuelve el de arriba, y history[-1] solo mira el de arriba.
• Arriba es el final de la lista. Las dos operaciones son rápidas, porque al final no se mueve nada.
• print imprime la pila de abajo arriba: el de arriba es el último.

Más precisamente, para curiosos

• pop() y [-1] en una lista vacía detienen el programa con IndexError. Así que comprueba primero. if history: significa «si la lista no está vacía»: una lista vacía en if y while funciona como False.

history = []
if history:
    print("Ahora:", history[-1])
else:
    print("No hay página anterior.")
try:
    history.pop()
except IndexError as e:
    print(f"IndexError: {e}")

Salida

No hay página anterior.
IndexError: pop from empty list

Pruébalo

¿Qué queda por deshacer?

¿Qué imprimirá el programa?

undo = []
undo.append("fuente")
undo.append("color")
undo.append("tamaño")
undo.pop()
undo.append("subrayado")
while len(undo) > 0:
    print(undo.pop())

Respuesta

fuente
color
subrayado

subrayado
color
fuente

fuente
color
tamaño

subrayado
tamaño
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:

from collections import deque

printer = deque()
printer.append("factura.pdf")
printer.append("contrato.docx")
printer.append("foto.jpg")
print("Siguiente:", printer[0])

while len(printer) > 0:
    print("Imprimiendo", printer.popleft())
print("Cola:", printer)

Salida

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

• deque está en el módulo collections, así que el archivo empieza con from collections import deque. El nombre viene de double-ended queue, una cola con dos extremos.
• append pone al final, popleft quita y devuelve el primero, y printer[0] mira el primero.
• ¿Por qué no una lista con pop(0)? pop(0) mueve todos los demás un lugar hacia delante, como al insertar al principio en la lección sobre listas. deque quita por delante sin mover nada.

Más precisamente, para curiosos

• popleft en una cola vacía detiene el programa con IndexError. Una deque también puede ser una pila: append y pop trabajan por el extremo derecho.

from collections import deque

clients = deque()
clients.append("Cliente 1")
clients.append("Cliente 2")
print("Último:", clients.pop())
print("Atendido:", clients.popleft())
try:
    clients.popleft()
except IndexError as e:
    print(f"IndexError: {e}")

Salida

Último: Cliente 2
Atendido: Cliente 1
IndexError: pop from an empty deque

• También existe queue.Queue, pero es para programas con varios hilos que se pasan tareas. Para una cola normal, usa deque.

Pruébalo

El siguiente en la caja

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

from collections import deque

checkout = deque()
checkout.append("Carlos")
checkout.append("Lucía")
client = checkout.()
print(f"Tu turno, {client}")

Comprobar

Míralo

Una lista enlazada por dentro

Una lista 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:
    def __init__(self, value, next):
        self.value = value
        self.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 None.

head = None
head = Node("Café", head)
head = Node("Leche", head)
head = Node("Pan", head)

n = head
while n is not None:
    print(n.value)
    n = n.next

Paso a paso, en palabras

1. La lista está vacía: head es None.
2. Un nodo nuevo: next es el head anterior (None), 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 None: 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 None.
• El costo: los nodos no tienen índices. Al quinto elemento llegas pasando por los cuatro primeros.

La idea

deque, y cuál usar cuándo

Python no tiene una lista enlazada lista para usar como la clase Node. Tiene deque: por dentro es una lista enlazada, pero cada nodo no guarda un elemento, sino todo un bloque de ellos. Por eso es rápida en los dos extremos: append y appendleft, pop y popleft, [0] y [-1]:

from collections import deque

route = deque()
route.append("Zaragoza")
route.append("Lleida")
route.appendleft("Madrid")
route.append("Barcelona")
print(list(route))

route.remove("Lleida")
print("Después del cambio:", list(route))
print("De", route[0], "a", route[-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: list. Es la elección habitual.
• Una pila: list con append y pop.
• Una cola: deque con append y popleft.

Más precisamente, para curiosos

• list(route) crea una lista normal a partir de la cola, para que se imprima como lista. print(route) a secas da deque([...]).
• En CPython cada bloque de una deque guarda 64 elementos, y los bloques están enlazados en las dos direcciones, al siguiente y al anterior. Por eso route[0] y route[-1] son rápidos, mientras que un elemento en el medio de una cola grande es lento: llegas a él pasando por los bloques.
• 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 AttributeError. ¿Qué línea tiene el error?

Elige la línea con el error.

1def count(head):2 count = 03 n = head4 while n.next is not None:5 count += 16 n = n.next7 return count

Comprobar

Ejercicio

Pilas y colas en acción

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

1. Un tren de juguete. Una clase Train con los métodos add_wagon(wagon) y remove_wagon(). El tren es una pila: el último vagón enganchado es el primero que se desengancha. remove_wagon() devuelve el vagón desenganchado, o None 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 add_stop(stop) y get_next_stop(), que devuelve la próxima parada, o None 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. update_price(price) añade un precio, y si hay más de N precios, quita el más antiguo. Añade get_last_price() y average() para los precios guardados. Para SAP con N = 3, pasa los precios 150, 152, 149 y 155. Pista: deque(maxlen=3) quita sola el más antiguo cuando hay más de 3. Imprime los precios con dos decimales.

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 is_balanced(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 __str__(). 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é pasa con popleft() en una deque vacía?

Devuelve 0Devuelve NoneEl programa se detiene con IndexError

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