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 List<string>();
actions.Add("Texto escrito");
actions.Add("Título en negrita");
actions.Add("Foto insertada");

// Ctrl+Z: deshacer la última acción.
string undone = actions[0];
actions.RemoveAt(0);
Console.WriteLine("Deshecho: " + undone);
Console.WriteLine("Queda: " + string.Join(", ", actions));

Salida

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

La corrección es actions[^1] y actions.RemoveAt(actions.Count - 1): RemoveAt no devuelve el elemento quitado, así que lo lees antes. 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:

Stack<string> history = new Stack<string>();
history.Push("Inicio");
history.Push("Portátiles");
history.Push("Portátil de 14 pulgadas");
Console.WriteLine("Ahora: " + history.Peek());

history.Pop();
Console.WriteLine("Atrás: " + history.Peek());
Console.WriteLine(string.Join(", ", 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.
• Stack<T> está en System.Collections.Generic, como List<T>.
• string.Join recorre la pila de arriba abajo.

Más precisamente, para curiosos

• Pop y Peek en una pila vacía detienen el programa. TryPeek no: devuelve false si la pila está vacía, y te da el elemento de arriba a través de out:

Stack<string> history = new Stack<string>();
if (history.TryPeek(out string page))
{
    Console.WriteLine("Ahora: " + page);
}
else
{
    Console.WriteLine("No hay página anterior.");
}
history.Pop();

Error

Unhandled exception. System.InvalidOperationException: Stack empty.

El programa primero imprime «No hay página anterior.», y se detiene en Pop. Para Pop también existe TryPop.

• C# también tiene una clase Stack más antigua, sin corchetes angulares, en System.Collections. Guarda todo como object. Funciona, pero hoy se usa Stack<T>:

Stack stack = new Stack();
stack.Push("Google");
stack.Push("Apple");
stack.Push("Microsoft");
Console.WriteLine("Arriba: " + stack.Peek());
while (stack.Count > 0)
{
    Console.WriteLine("Sacado: " + stack.Pop());
}

Salida

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

Pruébalo

¿Qué queda por deshacer?

¿Qué imprimirá el programa?

Stack<string> undo = new Stack<string>();
undo.Push("fuente");
undo.Push("color");
undo.Push("tamaño");
undo.Pop();
undo.Push("subrayado");
while (undo.Count > 0)
{
    Console.WriteLine(undo.Pop());
}

Respuesta

fuente
color
tamaño

subrayado
tamaño
color
fuente

subrayado
color
fuente

fuente
color
subrayado

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 Queue<string>();
printer.Enqueue("factura.pdf");
printer.Enqueue("contrato.docx");
printer.Enqueue("foto.jpg");
Console.WriteLine("Siguiente: " + printer.Peek());

while (printer.Count > 0)
{
    Console.WriteLine("Imprimiendo " + printer.Dequeue());
}
Console.WriteLine("Cola: " + printer.Count);

Salida

Siguiente: factura.pdf
Imprimiendo factura.pdf
Imprimiendo contrato.docx
Imprimiendo foto.jpg
Cola: 0

• Enqueue pone al final, Dequeue quita y devuelve el primero, y Peek mira el primero.
• Queue<T> está en System.Collections.Generic. Count dice cuántos esperan, así que el bucle pregunta Count > 0.
• Dequeue y Peek en una cola vacía detienen el programa. TryDequeue y TryPeek devuelven false.

Más precisamente, para curiosos

• La cola vacía:

Queue<string> clients = new Queue<string>();
clients.Enqueue("Cliente 1");
Console.WriteLine("Atendido: " + clients.Dequeue());
if (!clients.TryDequeue(out string next))
{
    Console.WriteLine("No hay nadie esperando.");
}
clients.Dequeue();

Error

Unhandled exception. System.InvalidOperationException: Queue empty.

TryDequeue dice «No hay nadie esperando.», y el último Dequeue detiene el programa.

• C# no tiene una clase aparte para una cola con dos extremos. LinkedList<T> puede añadir y quitar en los dos extremos, así que los ejemplos antiguos la usan como cola:

LinkedList<string> clients = new LinkedList<string>();
clients.AddLast("Cliente 1");
clients.AddLast("Cliente 2");
clients.AddFirst("Cliente con cita");
Console.WriteLine("Atendido: " + clients.First.Value);
clients.RemoveFirst();
Console.WriteLine("Último: " + clients.Last.Value);
Console.WriteLine("Esperando: " + string.Join(", ", clients));

Salida

Atendido: Cliente con cita
Último: Cliente 2
Esperando: Cliente 1, Cliente 2

• Queue<string> también acepta null como elemento. Una cola vacía se reconoce por Count o por TryDequeue, no por null:

Queue<string> printer = new Queue<string>();
printer.Enqueue(null);
Console.WriteLine(printer.Count);

Salida

1

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 Queue<string>();
checkout.Enqueue("Carlos");
checkout.Enqueue("Lucía");
string next = checkout.();
Console.WriteLine("Tu turno, " + next);

Comprobar

Míralo

Una lista enlazada por dentro

List<T> 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
{
    public string Value;
    public Node Next;

    public Node(string value, Node next)
    {
        Value = value;
        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)
{
    Console.WriteLine(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<T>, y cuál usar cuándo

C# tiene una lista enlazada lista para usar: LinkedList<T>. Añade en los dos extremos con AddFirst y AddLast, quita por valor con Remove, y te da el primer y el último nodo a través de First y Last:

LinkedList<string> route = new LinkedList<string>();
route.AddLast("Zaragoza");
route.AddLast("Lleida");
route.AddFirst("Madrid");
route.AddLast("Barcelona");
Console.WriteLine(string.Join(", ", route));

route.Remove("Lleida");
Console.WriteLine("Después del cambio: " + string.Join(", ", route));
Console.WriteLine("De " + route.First.Value + " a " + route.Last.Value);

Salida

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

LinkedList<T> no tiene índices en absoluto. A un elemento por número solo llegas a través de los nodos, así que el compilador no permite [ ]:

Console.WriteLine(route[1]);

Error de compilación

error CS0021: Cannot apply indexing with [] to an expression of type 'LinkedList<string>'

Cuál usar cuándo:

• Una lista por número: List<T>. Es la elección habitual.
• Una pila: Stack<T>. Una cola: Queue<T>.
• LinkedList<T>: pocas veces. Cuando necesitas los dos extremos, o insertas y quitas a menudo junto a un nodo que ya tienes.

Más precisamente, para curiosos

• ¿Por qué LinkedList<T> suele ser más lenta, 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 List<T>, Stack<T> y Queue<T> es justo eso.
• Los nodos de una LinkedList<T> se ven: First es un LinkedListNode<string> con Value, Next y Previous. Las flechas van en las dos direcciones, así que Last y RemoveLast también son rápidos:

LinkedList<string> route = new LinkedList<string>();
route.AddLast("Madrid");
route.AddLast("Zaragoza");
route.AddLast("Barcelona");
LinkedListNode<string> second = route.First.Next;
Console.WriteLine(second.Value);
Console.WriteLine(second.Previous.Value + " <- " + second.Value + " -> " + second.Next.Value);
Console.WriteLine(route.Last.Next == null);

Salida

Zaragoza
Madrid <- Zaragoza -> Barcelona
True

• El nodo de la tarjeta anterior 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 NullReferenceException. ¿Qué línea tiene el error?

Elige la línea con el error.

1static int Count(Node head)2{3 int count = 0;4 Node n = head;5 while (n.Next != null)6 {7 count++;8 n = n.Next;9 }10 return count;11}

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 una propiedad 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: una Queue<T> solo ve su primer elemento, así que guarda el último precio en un campo aparte. Imprime los precios con F2.

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(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), una propiedad Count 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?

CBA

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 Dequeue() en una Queue<string> vacía?

Devuelve nullDevuelve un texto vacíoEl programa se detiene con InvalidOperationException

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