Stack w C#

Stack<T> to wbudowana w .NET kolekcja reprezentująca strukturę danych typu LIFO (Last-In-First-Out) — ostatni element, który trafił na stos, jest też pierwszym, który z niego zejdzie. To dokładne przeciwieństwo kolejki (FIFO), o której pisałem w osobnym artykule o Queue<T>.

Ten artykuł skupia się na gotowej klasie Stack<T> z .NET — jej API, złożoności, pułapkach i realnych zastosowaniach. Jeśli chcesz zobaczyć, jak zbudować własny stos od podstaw (własny interfejs, tablica, wskaźnik wierzchołka), zobacz dedykowany temu artykuł: Implementowanie stosu w C#.

Czym jest Stack<T> i kiedy go użyć

Najlepszą analogią jest przycisk “Wstecz” w przeglądarce. Każdy odwiedzony adres trafia na stos. Kliknięcie “Wstecz” zdejmuje ze stosu ostatnio dodany adres — czyli ten, na którym właśnie byłeś, nie ten, od którego zaczynałeś sesję przeglądania. Dokładnie ten sam mechanizm stoi za funkcją cofania (undo) w edytorach tekstu czy grafiki: ostatnia wykonana operacja jest pierwszą, którą cofasz.

Stos jest naturalnym wyborem, gdy w Twojej logice liczy się dostęp wyłącznie do ostatnio dodanego elementu — nie do dowolnego po indeksie, jak w List<T>.

Podstawowe operacje stosu

• Push — dodaje element na wierzch stosu,
• Pop — usuwa i zwraca element z wierzchu stosu,
• Peek — zwraca element z wierzchu, bez usuwania go.

var stack = new Stack<string>();

// Dodaj element na stos
stack.Push("https://dev-hobby.pl");
stack.Push("https://dev-hobby.pl/blog");

// Sprawdź, czy stos zawiera dany element — O(n)
var contains = stack.Contains("https://dev-hobby.pl");

// Usuń i zwróć element z wierzchu stosu
var top = stack.Pop(); // "https://dev-hobby.pl/blog"

// Podejrzyj element z wierzchu, nie usuwając go
var next = stack.Peek();

// Bezpieczne warianty — nie rzucają wyjątku na pustym stosie
if (stack.TryPop(out var result))
{
    Console.WriteLine(result);
}

if (stack.TryPeek(out var peeked))
{
    Console.WriteLine(peeked);
}

// Usuń wszystkie elementy ze stosu
stack.Clear();

// Uzyskaj liczbę elementów na stosie
var count = stack.Count;

Podobnie jak przy Queue<T>, warianty TryPop i TryPeek są tym, czego brakuje w wielu tutorialach — a to one ratują z najczęstszego błędu opisanego niżej.

Jak Stack<T> działa pod maską — w skrócie

Wewnętrznie Stack<T> opiera się na tablicy o zmiennym rozmiarze. Ponieważ tablice w C# mają stały rozmiar, w miarę wpychania elementów przez Push kolekcja w razie potrzeby alokuje nową, większą tablicę (domyślnie podwaja pojemność) i kopiuje do niej dotychczasowe elementy. Jeśli z góry znasz przybliżoną maksymalną liczbę elementów, warto podać ją w konstruktorze, by uniknąć zbędnych realokacji:

var stack = new Stack<string>(capacity: 100);

Złożoność czasowa Stack<T>

• Push — O(1) zamortyzowane (sporadyczna realokacja to O(n), ale rzadka),
• Pop — O(1),
• Peek — O(1),
• Contains — O(n), bo wymaga przeszukania całej kolekcji,
• ToArray() — O(n), zwraca elementy w kolejności od wierzchu do dołu stosu.

Stack vs Queue vs List — kiedy co wybrać

• Stack<T> — kolejność LIFO. Wybierz do cofania operacji (undo/redo), parsowania wyrażeń nawiasowych, przechodzenia po grafie/drzewie w głąb (DFS), historii nawigacji.
• Queue<T> — kolejność FIFO. Wybierz, gdy kolejność przetwarzania musi odpowiadać kolejności napływania (zadania w tle, BFS).
• List<T> — gdy potrzebujesz swobodnego dostępu po indeksie czy sortowania. Symulowanie stosu przez list.Add()/list[^1]/list.RemoveAt(list.Count - 1) zadziała, ale jest mniej czytelne i mniej wyraziste niż dedykowany typ.

Zastosowania Stack<T> w praktyce

Sprawdzanie poprawności nawiasów — klasyczne zadanie rekrutacyjne, w którym stos jest jedynym rozsądnym narzędziem:

static bool AreParenthesesBalanced(string expression)
{
    var stack = new Stack<char>();
    var pairs = new Dictionary<char, char> { [')'] = '(', [']'] = '[', ['}'] = '{' };

    foreach (var ch in expression)
    {
        if (ch is '(' or '[' or '{')
        {
            stack.Push(ch);
        }
        else if (pairs.ContainsKey(ch))
        {
            if (!stack.TryPop(out var last) || last != pairs[ch])
            {
                return false;
            }
        }
    }

    return stack.Count == 0;
}

Przechodzenie po grafie w głąb (DFS) — stos zastępuje tu rekurencję, gdy wolisz iteracyjną implementację:

static void Dfs(Dictionary<int, List<int>> graph, int start)
{
    var visited = new HashSet<int>();
    var stack = new Stack<int>();

    stack.Push(start);

    while (stack.TryPop(out var node))
    {
        if (!visited.Add(node)) continue;

        Console.WriteLine($"Odwiedzam: {node}");

        foreach (var neighbor in graph[node])
        {
            stack.Push(neighbor);
        }
    }
}

Call stack maszyny wirtualnej .NET — sam mechanizm wywołań metod i rekurencji w CLR działa właśnie na stosie: każde wywołanie metody odkłada tzw. ramkę stosu (stack frame), a powrót z metody ją zdejmuje. To dlatego zbyt głęboka rekurencja kończy się StackOverflowException — dosłownie przepełnieniem stosu wywołań.

Obliczanie wyrażeń w odwrotnej notacji polskiej (ONP/RPN) — kolejne klasyczne zadanie rekrutacyjne, gdzie stos jest naturalnym narzędziem: liczby odkładamy na stos, a napotkany operator zdejmuje dwa ostatnie elementy, wykonuje działanie i odkłada wynik z powrotem:

static double EvaluateRpn(string[] tokens)
{
    var stack = new Stack<double>();

    foreach (var token in tokens)
    {
        if (double.TryParse(token, out var number))
        {
            stack.Push(number);
            continue;
        }

        var b = stack.Pop();
        var a = stack.Pop();

        stack.Push(token switch
        {
            "+" => a + b,
            "-" => a - b,
            "*" => a * b,
            "/" => a / b,
            _ => throw new InvalidOperationException($"Nieznany operator: {token}")
        });
    }

    return stack.Pop();
}

// EvaluateRpn(["3", "4", "+", "2", "*"]) => (3 + 4) * 2 = 14

Częste pułapki

• Pop()/Peek() na pustym stosie rzuca InvalidOperationException — sprawdzaj Count albo, lepiej, użyj TryPop/TryPeek.
• Stack<T> nie jest bezpieczny wątkowo — do scenariuszy wielowątkowych użyj System.Collections.Concurrent.ConcurrentStack<T>.
• Kolejność w foreach jest odwrotna niż w Queue — iterowanie po Stack<T> zaczyna się od wierzchu (ostatnio dodanego elementu), a nie od pierwszego dodanego — łatwo o pomyłkę, jeśli myślisz o nim jak o liście.
• Contains() to O(n), nie O(1) — jeśli często sprawdzasz przynależność elementu, rozważ dodatkowy HashSet<T> obok stosu.
• Stack<T> to typ referencyjny — przekazanie go do metody przekazuje referencję do tej samej kolekcji, nie kopię.

Stack<T> w nowszych wersjach C#

Podobnie jak Queue<T>, od .NET 9 (C# 13) Stack<T> wspiera collection expressions z C# 12 — zwięzłą inicjalizację bez wywoływania Push w pętli:

// Skrócona inicjalizacja stosu (C# 12/13, .NET 9+)
// Kolejność ma znaczenie: ostatni element trafia na wierzch
Stack<int> stack = [1, 2, 3, 4, 5];

FAQ — najczęstsze pytania o Stack<T>

Czym różni się Stack<T> od Queue<T>?
Stack zwraca element ostatnio dodany (LIFO), Queue zwraca element dodany najwcześniej (FIFO). Reszta API (Count, Contains, Clear, wersje Try*) wygląda niemal identycznie.

Czy Stack<T> jest bezpieczny wątkowo?
Nie. Do scenariuszy wielowątkowych użyj ConcurrentStack<T> z przestrzeni System.Collections.Concurrent.

Dlaczego rekurencja rzuca StackOverflowException?
Bo każde wywołanie metody odkłada ramkę na stosie wywołań CLR. Zbyt głęboka rekurencja (np. brak warunku stopu) zapełnia ten stos do granicy dostępnej pamięci — i program się wywala, zamiast rzucić zwykły, przechwytywalny wyjątek.

Czy da się zamienić stos rekurencyjny (DFS) na iteracyjny?
Tak — przykład wyżej pokazuje dokładnie to: jawny Stack<T> zamiast wywołań rekurencyjnych, co eliminuje ryzyko przepełnienia stosu wywołań przy bardzo głębokich grafach.

Jaka jest złożoność Pop()?
O(1) — stały czas, niezależnie od liczby elementów na stosie.

DFS to tylko jedna z dwóch podstawowych strategii przechodzenia po grafie. Zobacz przeciwną — przeszukiwanie wszerz — w artykule o Queue w C#, na tym samym grafie, tylko z kolejką zamiast stosu.