Docs ejecutables de C#: Stack

Q: ¿Qué es un Stack en C#?

Stack de System.Collections.Generic es una colección LIFO (last in, first out, el último que entra es el primero que sale). Push pone un elemento encima, Pop quita y devuelve el elemento de arriba, y Peek devuelve el elemento de arriba sin quitarlo. Las tres se ejecutan en tiempo constante.

Q: ¿Qué ocurre al hacer Pop sobre una pila vacía en C#?

Pop y Peek lanzan InvalidOperationException cuando la pila está vacía. Comprueba antes stack.Count > 0, o usa TryPop(out var item) y TryPeek(out var item), que devuelven false en lugar de lanzar una excepción (.NET Core 2.0 y posteriores).

Q: ¿Qué diferencia hay entre un Stack y una Queue en C#?

Un Stack devuelve primero el elemento más nuevo (el último que entra es el primero que sale), mientras que una Queue devuelve primero el más antiguo (el primero que entra es el primero que sale). Usa una pila para el historial de deshacer, las estructuras anidadas y la búsqueda en profundidad; usa una cola para procesar trabajo en orden de llegada y para la búsqueda en anchura.

Un Stack<T> es un montón: pones elementos encima con Push y los quitas de arriba con Pop, así que el último que entra es el primero que sale (LIFO). Solo se puede llegar al de arriba, y cada operación sobre él tarda un tiempo constante.

Push, Pop y Peek

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var plates = new Stack<string>();
        plates.Push("blue");
        plates.Push("red");
        plates.Push("green");

        Console.WriteLine("On top: " + plates.Peek()); // look only
        Console.WriteLine("Count: " + plates.Count);

        Console.WriteLine("Took " + plates.Pop());       // remove the top
        Console.WriteLine("On top: " + plates.Peek());

        while (plates.Count > 0)
        {
            Console.WriteLine("Took " + plates.Pop());
        }
        Console.WriteLine("Count: " + plates.Count);
    }
}

Salida:

On top: green
Count: 3
Took green
On top: red
Took red
Took blue
Count: 0

green se apiló el último, así que sale primero. Peek devuelve el de arriba sin cambiar la pila, y así puedes ver lo que te daría Pop antes de decidir sacarlo.

La excepción de la pila vacía y TryPop

Hacer pop o peek sobre una pila vacía lanza InvalidOperationException. Suele aparecer en parsers y algoritmos que reciben una entrada con más elementos de cierre que de apertura.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var history = new Stack<int>();

        try
        {
            history.Pop();
        }
        catch (InvalidOperationException e)
        {
            Console.WriteLine("Caught " + e.GetType().Name);
        }

        history.Push(10);

        int value;
        Console.WriteLine(history.TryPop(out value) + " " + value);
        Console.WriteLine(history.TryPop(out value) + " " + value); // empty now
    }
}

Salida:

Caught InvalidOperationException
True 10
False 0

TryPop y TryPeek (.NET Core 2.0 y posteriores) devuelven false con una pila vacía y ponen la variable out en el valor por defecto, aquí 0. En .NET Framework, comprueba antes Count > 0.

Orden de iteración: primero el de arriba

Enumerar una pila no quita nada, y va de arriba abajo, en el orden en que Pop devolvería los elementos:

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        var pages = new Stack<string>();
        pages.Push("home");
        pages.Push("products");
        pages.Push("checkout");

        foreach (string page in pages)
        {
            Console.Write(page + " ");
        }
        Console.WriteLine();

        Console.WriteLine(string.Join(" > ", pages.ToArray()));
        Console.WriteLine(pages.Contains("home"));

        var copy = new Stack<string>(pages);  // pushes in enumeration order...
        Console.WriteLine(copy.Peek());        // ...so the copy is reversed

        var sameOrder = new Stack<string>(pages.Reverse());
        Console.WriteLine(sameOrder.Peek());
    }
}

Salida:

checkout products home 
checkout > products > home
True
home
checkout

La copia invertida pilla a la gente por sorpresa: el constructor recibe cualquier IEnumerable<T> y apila sus elementos en orden, y una pila se enumera empezando por arriba, así que el antiguo elemento de arriba acaba abajo del todo en la copia. Invertir antes la secuencia (el Reverse() de LINQ devuelve los elementos empezando por abajo) da una copia con el mismo elemento arriba.

Apilar una lista de elementos en una pila nueva también los invierte, lo que es una forma rápida de invertir una secuencia: new Stack<char>("hello") devuelve con pop o, l, l, e, h.

Ejemplo: un historial para deshacer

Los editores guardan cada cambio en una pila. Deshacer saca el cambio más reciente y lo revierte; rehacer mantiene una segunda pila de cambios deshechos.

using System;
using System.Collections.Generic;

class Editor
{
    private string text = "";
    private readonly Stack<string> undo = new Stack<string>();
    private readonly Stack<string> redo = new Stack<string>();

    public void Type(string s)
    {
        undo.Push(text);   // remember the state before the change
        redo.Clear();      // a new change invalidates the redo history
        text += s;
    }

    public void Undo()
    {
        if (undo.Count == 0) return;
        redo.Push(text);
        text = undo.Pop();
    }

    public void Redo()
    {
        if (redo.Count == 0) return;
        undo.Push(text);
        text = redo.Pop();
    }

    public string Text { get { return text; } }
}

class Program
{
    static void Main()
    {
        var ed = new Editor();
        ed.Type("Hello");
        ed.Type(", world");
        ed.Type("!");
        Console.WriteLine(ed.Text);

        ed.Undo();
        Console.WriteLine(ed.Text);
        ed.Undo();
        Console.WriteLine(ed.Text);

        ed.Redo();
        Console.WriteLine(ed.Text);
    }
}

Salida:

Hello, world!
Hello, world
Hello
Hello, world

Guardar instantáneas completas es la versión más sencilla. Los editores reales apilan en su lugar pequeños objetos de comando (qué se insertó y dónde), cada uno con un método para revertirse, pero las dos pilas funcionan igual.

Ejemplo: paréntesis equilibrados

Comprobar que (, [ y { se cierran en el orden correcto es el ejercicio clásico de pilas, y la misma lógica está dentro de todos los compiladores y parsers de JSON.

using System;
using System.Collections.Generic;

class Program
{
    static bool IsBalanced(string s)
    {
        var open = new Stack<char>();
        foreach (char c in s)
        {
            if (c == '(' || c == '[' || c == '{')
            {
                open.Push(c);
            }
            else if (c == ')' || c == ']' || c == '}')
            {
                if (open.Count == 0) return false;          // closer with no opener
                char top = open.Pop();
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) return false; // wrong kind
            }
        }
        return open.Count == 0;                             // leftovers are unclosed
    }

    static void Main()
    {
        string[] inputs = { "f(a[i], {x: 1})", "(]", "((a)", "a)b(", "" };
        foreach (string input in inputs)
        {
            Console.WriteLine("\"" + input + "\" -> " + IsBalanced(input));
        }
    }
}

Salida:

"f(a[i], {x: 1})" -> True
"(]" -> False
"((a)" -> False
"a)b(" -> False
"" -> True

Las tres comprobaciones de fallo corresponden a las tres formas en que los paréntesis salen mal: un cierre sin nada abierto (a)b(, detectado con Count == 0 en lugar de con una excepción de Pop), un cierre del tipo equivocado ((]) y aperturas que nunca se cierran (((a), detectadas con la comprobación final).

Otros usos

Búsqueda en profundidad. Sustituye la cola de una búsqueda en anchura por una pila y el recorrido va en profundidad antes que en anchura. Una pila explícita también sustituye a la recursividad cuando la entrada es lo bastante profunda como para arriesgarse a una StackOverflowException, que no se puede capturar.
Evaluar expresiones. La notación postfija (3 4 + 2 *) se evalúa apilando números y sacando dos por cada operador.
Vuelta atrás. El historial de navegación, la resolución de laberintos y los estados de un parser apilan una posición y vuelven a ella con pop al llegar a un callejón sin salida.

Consulta Queue para la colección equivalente en la que el primero que entra es el primero que sale.

Stack frente a Queue frente a List

	`Stack<T>`	`Queue<T>`	`List<T>`
Orden de salida	El más nuevo primero	El más antiguo primero	Cualquiera, por índice
Añadir	`Push`	`Enqueue`	`Add`, `Insert`
Quitar	`Pop` (arriba)	`Dequeue` (principio)	`Remove`, `RemoveAt`
Mirar	`Peek`	`Peek`	`list[i]`
Variantes seguras	`TryPop`, `TryPeek`	`TryDequeue`, `TryPeek`	no hacen falta

Para varios hilos, ConcurrentStack<T> de System.Collections.Concurrent ofrece Push, TryPop y TryPeek sin locks.

Errores comunes

Hacer pop sin comprobar. Una pila vacía lanza InvalidOperationException; comprueba Count o usa TryPop.
Esperar que foreach empiece por el primer elemento apilado. Empieza por el de arriba.
Copiar con new Stack<T>(stack). La copia sale invertida.
Apilar dentro de un foreach sobre la misma pila. Lanza una excepción; usa un bucle while (stack.Count > 0).

Preguntas frecuentes

¿Qué es un Stack en C#?

Stack<T> de System.Collections.Generic es una colección LIFO (last in, first out, el último que entra es el primero que sale). Push pone un elemento encima, Pop quita y devuelve el elemento de arriba, y Peek devuelve el elemento de arriba sin quitarlo. Las tres se ejecutan en tiempo constante.

¿Qué ocurre al hacer Pop sobre una pila vacía en C#?

Pop y Peek lanzan InvalidOperationException cuando la pila está vacía. Comprueba antes stack.Count > 0, o usa TryPop(out var item) y TryPeek(out var item), que devuelven false en lugar de lanzar una excepción (.NET Core 2.0 y posteriores).

¿En qué orden recorre foreach un Stack?

De arriba abajo: el elemento añadido más recientemente va primero, el mismo orden en que los devolvería Pop. ToArray() usa el mismo orden. Una consecuencia es que new Stack<T>(otherStack) produce una copia invertida, porque el constructor apila los elementos en el orden en que los enumera.

¿Qué diferencia hay entre un Stack y una Queue en C#?

Un Stack<T> devuelve primero el elemento más nuevo (el último que entra es el primero que sale), mientras que una Queue<T> devuelve primero el más antiguo (el primero que entra es el primero que sale). Usa una pila para el historial de deshacer, las estructuras anidadas y la búsqueda en profundidad; usa una cola para procesar trabajo en orden de llegada y para la búsqueda en anchura.

¿Cómo compruebo si los paréntesis están equilibrados en C#?

Recorre el string una vez. Apila cada paréntesis de apertura en un Stack<char>. Para cada paréntesis de cierre, la pila no debe estar vacía y su elemento de arriba debe ser el de apertura correspondiente, que entonces sacas. El string está equilibrado cuando el recorrido termina con la pila vacía.

Conceptos relacionados