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

Zanim zagłębimy się w świat typów generycznych w C#, warto zobaczyć, jakie wyzwania mogą nas spotkać, gdy ich nie używamy. W tym celu stworzymy naszą pierwszą własną, prostą kolekcję – stos. Pokaże nam to pewne ograniczenia i przygotuje grunt pod zrozumienie, dlaczego typy generyczne są tak potężnym narzędziem.

Czym jest Stos? Zasada LIFO

Stos (ang. Stack) to struktura danych działająca zgodnie z zasadą LIFO (Last-In, First-Out), czyli “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. Podobnie działa stos w programowaniu: element dodany jako ostatni jest usuwany jako pierwszy. Używamy stosu, gdy chcemy mieć szybki dostęp do ostatnio dodanego elementu.

Budujemy własny Stos: MyStack

Stwórzmy teraz naszą implementację stosu w C#. Poniżej znajduje się kod klasy MyStack. A jeśli chcesz zgłębić tajniki nie tylko stosów, ale i innych struktur danych, a także w pełni opanować moc typów generycznych, które wkrótce omówimy, zapraszam Cię do moich kompleksowych kursów: C# Kolekcje oraz C# Generics!
Znajdziesz tam wszystko, czego potrzebujesz, aby stać się mistrzem organizacji danych w C#.

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)
    {
        // Inicjalizacja tablicy o zadanej pojemności
        elementsStack = new double[capacity]; 
        // Ustawienie wskaźnika szczytu na -1 (stos jest pusty)
        topOfTheStack = -1; 
    }

    // Właściwość zwracająca pojemność stosu
    public int Capacity              
    {
        get { return elementsStack.Length; }
    }

    // Właściwość sprawdzająca, czy stos jest pusty
    public bool IsEmpty              
    {
        get { return topOfTheStack == -1; }
    }

    // Właściwość sprawdzająca, czy stos jest pełny
    public bool IsFull               
    {
        get { return topOfTheStack == (Capacity - 1); }
    }

    // Metoda dodająca element na szczyt stosu
    public void WriteElement(double element)  
    {
        if (IsFull) // Sprawdzenie, czy stos nie jest pełny
        {
            Console.WriteLine("Stos jest pełny!");     
            Console.WriteLine("Element nie został dodany!"); 
        }
        else
        {
            // Zwiększenie wskaźnika szczytu i dodanie elementu
            elementsStack[++topOfTheStack] = element; 
            Console.WriteLine("Element został pomyślnie dodany!");   
        }
    }

    // Metoda pobierająca (i usuwająca) element ze szczytu stosu
    public double ReadElement()          
    {
        if (IsEmpty) // Sprawdzenie, czy stos nie jest pusty
        {
            Console.WriteLine("Stos jest pusty!"); 
            return 0; // Zwraca 0, gdy stos jest pusty (uproszczenie)
        }
        else
        {
            // Zwrócenie elementu ze szczytu i zmniejszenie wskaźnika
            return elementsStack[topOfTheStack--]; 
        }
    }

    // Metoda sprawdzająca (bez usuwania) element na szczycie stosu
    public double CheckElement()         
    {
        if (IsEmpty) // Sprawdzenie, czy stos nie jest pusty
        {
            Console.WriteLine("Stos jest pusty!"); 
            return 0; // Zwraca 0, gdy stos jest pusty (uproszczenie)
        }
        else
        {
            // Zwrócenie elementu ze szczytu bez zmiany wskaźnika
            return elementsStack[topOfTheStack]; 
        }
    }

    // Metoda wyświetlająca wszystkie elementy stosu (od góry)
    public void DisplayAll()         
    {
        if (IsEmpty)
        {
            Console.WriteLine("Brak elementów do wyświetlenia!"); 
        }
        else
        {
            Console.WriteLine("Elementy na stosie (od góry):");
            // Pętla od szczytu stosu w dół
            for (int i = topOfTheStack; i > -1; i--) 
            {
                Console.WriteLine($"Element {(i + 1)} : {elementsStack[i]}");
            }
        }
    }
}

Analiza kodu:

• elementsStack: To tablica typu double, która przechowuje nasze dane. Na razie ograniczamy się tylko do liczb zmiennoprzecinkowych.
• topOfTheStack: To zmienna typu int, która śledzi indeks ostatniego dodanego elementu (szczytu stosu). Początkowo ustawiona na -1, co sygnalizuje pusty stos.
• Konstruktory: Pozwalają utworzyć stos o domyślnej pojemności (3) lub o pojemności zdefiniowanej przez użytkownika.
• Właściwości (Capacity, IsEmpty, IsFull): Dostarczają informacji o stanie stosu.
• Metody (WriteElement, ReadElement, CheckElement, DisplayAll): Implementują podstawowe operacje na stosie: dodawanie elementu (push), pobieranie elementu (pop), podglądanie elementu na szczycie (peek) oraz wyświetlanie zawartości.

Nasza implementacja jest celowo prosta, bez zaawansowanej obsługi błędów, ale wystarczająca do demonstracji podstawowych zasad działania stosu.

Testujemy nasz Stos

Aby upewnić się, że nasz stos działa poprawnie, napiszmy kilka testów jednostkowych. Użyjemy do tego atrybutów z frameworka MSTest (lub podobnego).

// Zakładając użycie MSTest lub podobnego frameworka
[TestClass]  Atrybut oznaczający klasę testową
public class MyStackTest
{
    [TestMethod] // Atrybut oznaczający metodę testową
    public void New_Stack_Is_Empty() // Test: Nowy stos jest pusty
    {
        var stack = new MyStack();
        Assert.IsTrue(stack.IsEmpty); // Sprawdzenie, czy IsEmpty zwraca true
    }

    [TestMethod]
    public void Four_Element_Stack_Is_Full_After_Add_Four_Element()
    { // Test: Stos o pojemności 4 jest pełny po dodaniu 4 elementów
        var stack = new MyStack(capacity: 4);
        stack.WriteElement(5.0); // Używamy double
        stack.WriteElement(10.0);
        stack.WriteElement(30.0);
        stack.WriteElement(400.0);
        Assert.IsTrue(stack.IsFull); // Sprawdzenie, czy IsFull zwraca true
    }

    [TestMethod]
    public void Last_In_First_Out() // Test: Zasada LIFO
    {
        var stack = new MyStack(capacity: 3);
        var value1 = 3.3; // Używamy double
        var value2 = 7.5;
        var value3 = 9.2;

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

        // Sprawdzenie, czy elementy są zdejmowane w odwrotnej kolejności
        Assert.AreEqual(value3, stack.ReadElement()); 
        Assert.AreEqual(value2, stack.ReadElement());
        Assert.AreEqual(value1, stack.ReadElement());
        Assert.IsTrue(stack.IsEmpty); // Sprawdzenie, czy stos jest pusty po zdjęciu wszystkich elementów
    }

    [TestMethod]
    public void The_Output_Element_Is_The_Top_Of_The_Stack()
    { // Test: Metoda CheckElement zwraca element ze szczytu bez usuwania
        var stack = new MyStack(capacity: 10);
        
        stack.WriteElement(1.0); // Używamy double
        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()); // Sprawdzenie elementu na szczycie
        Assert.IsFalse(stack.IsEmpty); // Stos nie powinien być pusty
        Assert.AreEqual(6.0, stack.ReadElement()); // Dopiero ReadElement usuwa element
    }
}

Te testy weryfikują kluczowe aspekty działania stosu: początkowy stan pusty, stan pełny po dodaniu maksymalnej liczby elementów oraz fundamentalną zasadę LIFO.

Użycie Stosu w Aplikacji Konsolowej

Teraz wykorzystajmy nasz MyStack w prostej aplikacji konsolowej, która pozwoli użytkownikowi na interakcję ze stosem poprzez menu.

using System;

class Program
{
    static void Main(string[] args)
    {
        var stack = new MyStack(); // Tworzymy instancję naszego stosu

        while (true) // Pętla główna programu
        {
            Console.Clear(); // Czyszczenie konsoli dla przejrzystości
            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ć: "); 
                               
            // Próba sparsowania wyboru użytkownika
            int.TryParse(Console.ReadLine(), out int choice); 

            switch (choice) // Obsługa wyboru użytkownika
            {
                case 1:
                    Console.Write("Podaj element (liczbę): "); // Prośba o podanie liczby
                    // Próba sparsowania wprowadzonej wartości
                    if (double.TryParse(Console.ReadLine(), out double value)) 
                    {
                        stack.WriteElement(value); // Dodanie elementu do stosu
                    }
                    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(); // Wyświetlenie zawartości stosu
                    break;
                case 5:                                    
                    Console.WriteLine("Koniec programu.");
                    Environment.Exit(0); // Zakończenie aplikacji
                    break;
                default:                                   
                    Console.WriteLine("Dokonałeś niewłaściwego wyboru!");
                    break;
            }
            // Pauza przed powrotem do menu
            Console.WriteLine("\nNaciśnij Enter aby przejść do Menu"); 
            Console.ReadKey();         
        }
    }

    // --- Refactoring (Koncepcja) ---
    // W bardziej złożonej aplikacji, logikę z pętli while 
    // można by wydzielić do osobnych metod dla lepszej organizacji:
    // 
    // private static int DisplayMenu() 
    // { 
    //     // Kod wyświetlający menu i zwracający wybór użytkownika
    // }
    //
    // private static void WorkWithAChoice(MyStack stack, int choice)
    // {
    //     // Kod obsługujący konkretny wybór (switch)
    // }
    //
    // private static void BackToMenu()
    // {
    //     // Kod pauzy przed powrotem do menu
    // }
    //
    // Wtedy pętla w Main wyglądałaby czyściej:
    // while(true)
    // {
    //     int choice = DisplayMenu();
    //     WorkWithAChoice(stack, choice);
    //     if (choice == 5) break; // Wyjście z pętli
    //     BackToMenu();
    // }
}

Ten kod tworzy prostą pętlę, wyświetla menu opcji, pobiera wybór użytkownika i wykonuje odpowiednią akcję na stosie.

Refactoring dla Lepszej Struktury

Jak widać w komentarzach w powyższym kodzie, metoda Main staje się dość długa. W realnych aplikacjach dobrą praktyką jest dzielenie kodu na mniejsze, bardziej wyspecjalizowane metody. Moglibyśmy wydzielić logikę wyświetlania menu (DisplayMenu), obsługi wyboru użytkownika (WorkWithAChoice) i pauzy (BackToMenu), co uczyniłoby metodę Main znacznie czytelniejszą i łatwiejszą w zarządzaniu.

Problem: Nasz Stos działa tylko dla double!

Nasz stos działa, ale ma jedno istotne ograniczenie – może przechowywać tylko i wyłącznie wartości typu double. Wynika to bezpośrednio z deklaracji tablicy private double[] elementsStack; oraz sygnatur metod WriteElement(double element) i ReadElement() zwracającej double.

Co jeśli chcielibyśmy użyć naszego stosu do przechowywania napisów (string), liczb całkowitych (int), obiektów własnych klas, czy jakiegokolwiek innego typu danych? W obecnej formie jest to niemożliwe.

Moglibyśmy stworzyć osobne klasy stosu dla każdego typu (MyIntStack, MyStringStack itd.), ale to prowadzi do duplikacji kodu i jest bardzo nieefektywne. Innym podejściem mogłoby być użycie typu object jako typu przechowywanych elementów, ale to z kolei wiązałoby się z koniecznością rzutowania typów przy odczycie i utratą bezpieczeństwa typów w czasie kompilacji.

Rozwiązanie na Horyzoncie: Typy Generyczne

I tu właśnie z pomocą przychodzą typy generyczne (Generics). Pozwalają one na pisanie kodu (np. klas, metod), który może działać z różnymi typami danych, bez konieczności ich określania w momencie pisania kodu. Typ danych jest specificowany dopiero w momencie użycia generycznej klasy lub metody.

Dzięki typom generycznym moglibyśmy stworzyć jedną klasę MyStack<T>, która mogłaby działać jako stos dla int, string, double lub dowolnego innego typu, który wskażemy, zachowując przy tym pełne bezpieczeństwo typów. Ale to już temat na kolejny wpis!

Podsumowanie

Przeszliśmy przez proces tworzenia własnej, prostej implementacji stosu w C#. Zobaczyliśmy, jak działa zasada LIFO, jak zaimplementować podstawowe operacje i jak przetestować naszą klasę. Co najważniejsze, napotkaliśmy na fundamentalne ograniczenie naszego podejścia – brak elastyczności co do przechowywanych typów danych. To doskonały punkt wyjścia do zrozumienia potrzeby i potęgi typów generycznych w C#, które rozwiązują ten problem w elegancki sposób.