Tworzymy własny Stos w C# – Krok po kroku

Zanim napiszesz choć jedną linijkę kodu własnej struktury danych, warto przejść przez proces projektowy — zestaw pytań, które oszczędzą Ci przepisywania kodu później. W artykule Implementowanie Stosu pokazałem gotową implementację z interfejsem IStack. Tutaj patrzymy na to samo zadanie z innej strony — jak dojść do takiej implementacji, jakie decyzje projektowe po drodze podjąć i dlaczego niektóre pozornie rozsądne wybory mają ukryte koszty.

Czym jest Stos? Zasada LIFO

Stos (ang. Stack) to struktura danych działająca zgodnie z zasadą LIFO (Last-In, First-Out) — “ostatni na wejściu, pierwszy na wyjściu”. Wyobraź sobie stos talerzy: nowy talerz kładziesz na wierzch i zdejmujesz również ten z wierzchu. Element dodany jako ostatni jest usuwany jako pierwszy.

Krok 1: Jakich operacji faktycznie potrzebujesz?

Pierwsze pytanie projektowe nie brzmi “jak to zakodować”, tylko “co ta struktura musi umieć zrobić”. Dla stosu minimalny, wystarczający zestaw operacji to:

• dodanie elementu na wierzch (push),
• zdjęcie elementu z wierzchu (pop),
• podejrzenie elementu na wierzchu bez usuwania (peek),
• sprawdzenie, czy stos jest pusty — potrzebne, żeby bezpiecznie wywołać pop/peek.

Zauważ, czego celowo nie ma na tej liście: dostępu po indeksie, wstawiania w środku, sortowania. Gdybyś tego potrzebował, to sygnał, że nie potrzebujesz stosu, tylko innej struktury (np. listy) — dobra struktura danych powinna udostępniać dokładnie tyle operacji, ile wynika z jej natury, nie więcej.

Krok 2: Stały czy dynamiczny rozmiar?

Kolejna decyzja: czy stos ma mieć z góry ustaloną, stałą pojemność, czy ma rosnąć w miarę potrzeby (tak jak robi to produkcyjny Stack<T> z .NET)? Stały rozmiar jest prostszy do zaimplementowania i zrozumienia — dobry punkt startowy do nauki mechaniki stosu, zanim skomplikujesz go o logikę realokacji. W tym artykule celowo wybieramy tę prostszą drogę.

Budujemy własny Stos: MyStack

using System;

public class MyStack
{
    // Tablica przechowująca elementy stosu (na razie tylko double)
    private double[] elementsStack;
    // Indeks wskazujący na szczyt stosu (-1 oznacza pusty stos)
    private int topOfTheStack;

    // Konstruktor domyślny: tworzy stos o pojemności 3
    public MyStack() : this(capacity: 3)
    {
    }

    // Konstruktor z określoną pojemnością
    public MyStack(int capacity)
    {
        elementsStack = new double[capacity];
        topOfTheStack = -1;
    }

    public int Capacity
    {
        get { return elementsStack.Length; }
    }

    public bool IsEmpty
    {
        get { return topOfTheStack == -1; }
    }

    public bool IsFull
    {
        get { return topOfTheStack == (Capacity - 1); }
    }

    public void WriteElement(double element)
    {
        if (IsFull)
        {
            Console.WriteLine("Stos jest pełny!");
            Console.WriteLine("Element nie został dodany!");
        }
        else
        {
            elementsStack[++topOfTheStack] = element;
            Console.WriteLine("Element został pomyślnie dodany!");
        }
    }

    public double ReadElement()
    {
        if (IsEmpty)
        {
            Console.WriteLine("Stos jest pusty!");
            return 0; // Zwraca 0, gdy stos jest pusty (uproszczenie)
        }
        else
        {
            return elementsStack[topOfTheStack--];
        }
    }

    public double CheckElement()
    {
        if (IsEmpty)
        {
            Console.WriteLine("Stos jest pusty!");
            return 0;
        }
        else
        {
            return elementsStack[topOfTheStack];
        }
    }

    public void DisplayAll()
    {
        if (IsEmpty)
        {
            Console.WriteLine("Brak elementów do wyświetlenia!");
        }
        else
        {
            Console.WriteLine("Elementy na stosie (od góry):");
            for (int i = topOfTheStack; i > -1; i--)
            {
                Console.WriteLine($"Element {(i + 1)} : {elementsStack[i]}");
            }
        }
    }
}

Decyzje projektowe widoczne w tym kodzie: zwracanie 0 przy pustym stosie zamiast rzucania wyjątku to świadomy (choć uproszczony — w kodzie produkcyjnym lepszy byłby wyjątek lub TryPop) wybór; podobnie konstruktor domyślny z pojemnością 3 to arbitralna, ale jawna decyzja, a nie przypadek.

Krok 3: Jak zweryfikować, że decyzje projektowe działają?

Testy jednostkowe to nie dodatek na końcu — to sposób na zweryfikowanie założeń projektowych zanim zaczniesz z nich korzystać w większej aplikacji. Każdy test poniżej odpowiada jednej decyzji podjętej wyżej:

[TestClass] // Atrybut oznaczający klasę testową
public class MyStackTest
{
    [TestMethod]
    public void New_Stack_Is_Empty() // Weryfikuje decyzję: topOfTheStack = -1 oznacza pusty stos
    {
        var stack = new MyStack();
        Assert.IsTrue(stack.IsEmpty);
    }

    [TestMethod]
    public void Four_Element_Stack_Is_Full_After_Add_Four_Element() // Weryfikuje decyzję o stałej pojemności
    {
        var stack = new MyStack(capacity: 4);
        stack.WriteElement(5.0);
        stack.WriteElement(10.0);
        stack.WriteElement(30.0);
        stack.WriteElement(400.0);
        Assert.IsTrue(stack.IsFull);
    }

    [TestMethod]
    public void Last_In_First_Out() // Weryfikuje samą definicję stosu — najważniejszy test
    {
        var stack = new MyStack(capacity: 3);
        var value1 = 3.3;
        var value2 = 7.5;
        var value3 = 9.2;

        stack.WriteElement(value1);
        stack.WriteElement(value2);
        stack.WriteElement(value3);

        Assert.AreEqual(value3, stack.ReadElement());
        Assert.AreEqual(value2, stack.ReadElement());
        Assert.AreEqual(value1, stack.ReadElement());
        Assert.IsTrue(stack.IsEmpty);
    }

    [TestMethod]
    public void The_Output_Element_Is_The_Top_Of_The_Stack() // Weryfikuje, że CheckElement (peek) nie usuwa
    {
        var stack = new MyStack(capacity: 10);

        stack.WriteElement(1.0);
        stack.WriteElement(2.0);
        stack.WriteElement(3.0);
        stack.WriteElement(4.0);
        stack.WriteElement(5.0);
        stack.WriteElement(6.0);

        Assert.AreEqual(6.0, stack.CheckElement());
        Assert.IsFalse(stack.IsEmpty);
        Assert.AreEqual(6.0, stack.ReadElement()); // Dopiero ReadElement usuwa element
    }
}

Krok 4: Dogfooding — użycie stosu w aplikacji konsolowej

Ostatni krok procesu projektowego: użyj własnego API tak, jak użyłby go ktoś inny. To często ujawnia niewygody, których nie widać, patrząc tylko na definicję klasy:

using System;

class Program
{
    static void Main(string[] args)
    {
        var stack = new MyStack();

        while (true)
        {
            Console.Clear();
            Console.Write("\nMENU :");
            Console.WriteLine();
            Console.WriteLine("1. Zapisz element.");
            Console.WriteLine("2. Czytaj element.");
            Console.WriteLine("3. Sprawdź element.");
            Console.WriteLine("4. Wyświetl wszystko.");
            Console.WriteLine("5. Koniec programu.");
            Console.WriteLine();
            Console.Write("Dokonaj wyboru co chcesz zrobić: ");

            int.TryParse(Console.ReadLine(), out int choice);

            switch (choice)
            {
                case 1:
                    Console.Write("Podaj element (liczbę): ");
                    if (double.TryParse(Console.ReadLine(), out double value))
                    {
                        stack.WriteElement(value);
                    }
                    else
                    {
                        Console.WriteLine("Nieprawidłowa liczba!");
                    }
                    break;
                case 2:
                    Console.WriteLine("Odczytano element: {0}", stack.ReadElement());
                    break;
                case 3:
                    Console.WriteLine("Element na szczycie to: {0}", stack.CheckElement());
                    break;
                case 4:
                    stack.DisplayAll();
                    break;
                case 5:
                    Console.WriteLine("Koniec programu.");
                    Environment.Exit(0);
                    break;
                default:
                    Console.WriteLine("Dokonałeś niewłaściwego wyboru!");
                    break;
            }
            Console.WriteLine("\nNaciśnij Enter aby przejść do Menu");
            Console.ReadKey();
        }
    }
}

Właśnie tutaj ujawnia się pierwsza realna niewygoda: metoda Main robi zbyt wiele naraz (wyświetla menu, obsługuje wybór, czeka na klawisz). W większej aplikacji wydzieliłbyś to do osobnych metod (DisplayMenu, WorkWithAChoice, BackToMenu) — to sygnał z etapu dogfoodingu, że struktura kodu wymaga refaktoryzacji, zanim urośnie jeszcze bardziej.

Krok 5: Jaki typ elementów — i dlaczego to najważniejsza decyzja

Nasz stos ma jedno istotne ograniczenie: przechowuje tylko wartości typu double — wynika to wprost z private double[] elementsStack i sygnatur WriteElement(double)/ReadElement(). Co jeśli chcesz przechowywać stringi, liczby całkowite albo własne obiekty? W obecnej formie — nie da się.

Opcja A: osobna klasa dla każdego typu

MyIntStack, MyStringStack, MyProductStack… To prowadzi do duplikacji tego samego kodu N razy — jedyna różnica między klasami byłby typ tablicy. Odrzucamy tę opcję od razu.

Opcja B: object[] — podejście z Implementowania Stosu

W artykule Implementowanie Stosu rozwiązaliśmy ten sam problem inaczej — tablicą object[] zamiast double[]. To pozwala przechowywać dowolny typ, ale ma dwa realne koszty, które warto świadomie zaakceptować lub odrzucić:

• Boxing/unboxing — gdy wkładasz do tablicy object[] typ wartościowy (jak double czy int), CLR musi go “zapakować” (boxing) w obiekt na stercie, a przy odczycie “rozpakować” (unboxing). To dodatkowe alokacje i narzut wydajnościowy, którego nie ma przy tablicy double[].
• Utrata bezpieczeństwa typów w czasie kompilacji — object stack.ReadElement() trzeba zrzutować na właściwy typ w miejscu użycia ((double)stack.ReadElement()). Jeśli ktoś pomyli się i wrzuci na stos mieszankę int i string, błąd ujawni się dopiero w czasie działania programu (InvalidCastException), nie podczas kompilacji.

Innymi słowy: object[] naprawia problem elastyczności, ale płaci za to wydajnością i bezpieczeństwem typów. To nie jest darmowe rozwiązanie — to inny kompromis niż double[], nie strictly lepszy.

Opcja C: typy generyczne — rozwiązanie bez kompromisów z opcji B

Typy generyczne (Generics) pozwalają napisać kod, który działa z różnymi typami danych, bez określania ich w momencie pisania kodu — typ jest podawany dopiero przy użyciu. Klasa MyStack<T> mogłaby działać jako stos dla int, string, double czy dowolnego innego typu, zachowując przy tym pełne bezpieczeństwo typów w czasie kompilacji i unikając boxing/unboxing dla typów wartościowych. To dokładnie to, jak działa produkcyjny Stack<T> z .NET — i temat na osobny artykuł.

Podsumowanie — proces, nie tylko kod

Przeszliśmy przez pełny proces projektowy: jakie operacje są potrzebne, jaki rozmiar wybrać, jak zweryfikować decyzje testami, jak dogfooding ujawnia niewygody, i wreszcie — jak wybór typu elementów prowadzi przez trzy opcje o różnych kompromisach (duplikacja kodu → object[] z boxing i utratą bezpieczeństwa typów → generyki bez tych kosztów). To dokładnie ten sam finałowy wniosek, do którego dochodzi Implementowanie Stosu od strony gotowego kodu z interfejsem — tutaj doszliśmy do niego od strony pytań, które warto zadać, zanim napiszesz pierwszą linijkę własnej struktury danych.