Implementowanie stosu (Stack) w C#

Stos to struktura danych typu LIFO (Last In, First Out), co oznacza, że ostatni element dodany do stosu jest pierwszym, który zostanie z niego usunięty. Stosy są powszechnie używane w informatyce do różnych celów, takich jak cofanie operacji, wyrażenia arytmetyczne i wywoływanie funkcji.

W tym artykule zbudujemy własną implementację stosu od podstaw — na tablicy o stałym rozmiarze, z własnym interfejsem. Skupiamy się na gotowym kodzie: interfejsie, mechanice, kompletnej implementacji. Jeśli interesuje Cię proces dochodzenia do takiego rozwiązania — jakie pytania projektowe zadać, jak wybrać typ elementów i dlaczego object[] ma swoje koszty (boxing, utrata bezpieczeństwa typów) — zobacz artykuł od strony projektowej: Tworzymy własny Stos — proces projektowania. A jeśli zależy Ci na gotowej, produkcyjnej implementacji z .NET (dynamiczny rozmiar, TryPop/TryPeek, złożoność O(1), zastosowania w DFS i ONP), zobacz: Stack<T> w C#.

Implementowanie stosu

Podstawowe operacje wykonywane na stosie to Push i Pop.
Dane są dodawane do stosu za pomocą metody Push.
Dane są usuwane ze stosu za pomocą metody Pop.
Można zajrzeć do następnego elementu, który wyjdzie ze stosu i służy do tego metoda Peek.

Utworzymy teraz nasz własny stos. Rozpoczniemy od zdefiniowania interfejsu.

namespace ConsoleApp.MyStack;

interface IStack
{
    void Push(object element);
    object Pop();
    object Peek();
    bool isEmpty();
    void Display();
}

Teraz zaimplementujemy nasz stos.

using System;

namespace ConsoleApp.MyStack;

public class MyStack : IStack
{
    private int stackSize;
    public int top;
    public object[] item;

    public int StackSize
    {
        get { return stackSize; }
        set { stackSize = value; }
    }
    public MyStack()
    {
        StackSize = 10;
        item = new object[StackSize];
        top = -1;
    }
    public MyStack(int capacity)
    {
        StackSize = capacity;
        item = new object[StackSize];
        top = -1;
    }
    public bool isEmpty()
    {
        if (top == -1) return true;

        return false;
    }
    public void Push(object element)
    {
        if (top == (stackSize - 1))
            Console.WriteLine("Stos jest pełny!");
        else
            item[++top] = element;
    }
    public object Pop()
    {
        if (isEmpty())
        {
            Console.WriteLine("Stos jest pusty!");
            return "Bez elementów";
        }
        else
            return item[top--];
    }
    public object Peek()
    {
        if (isEmpty())
        {
            Console.WriteLine("Stos jest pusty!");
            return "Bez elementów";
        }
        else
            return item[top];
    }
    public void Display()
    {
        if (isEmpty())
            Console.WriteLine("Brak elementów do wyświetlenia");

        for (int i = top; i > -1; i--)
            Console.WriteLine("Element{0}: {1}", (i + 1), item[i]);
    }
}

Wyjaśnienie implementacji klasy MyStack

Klasa MyStack implementuje interfejs IStack, definiując operacje na stosie typu LIFO. Poniżej krok po kroku wyjaśniono działanie każdej metody i używanych zmiennych:

Pola klasy:

• stackSize: Przechowuje rozmiar stosu (domyślnie 10).
• top: Wskaźnik na wierzchołek stosu. Początkowo wskazuje na -1 (pusty stos).
• item: Tablica przechowująca elementy stosu. Rozmiar tablicy odpowiada stackSize.

Konstruktory:

• MyStack(): Domyślny konstruktor tworzy stos o rozmiarze 10 i inicjuje tablicę item.
• MyStack(int capacity): Konstruktor z parametrem capacity tworzy stos o podanym rozmiarze.

Metody:

• isEmpty(): Sprawdza, czy stos jest pusty. Zwraca true, jeśli top jest równy -1.
• Push(object element): Dodaje nowy element do stosu. Sprawdza, czy stos jest pełny (gdy top jest równy stackSize - 1). Jeśli tak, wyświetla komunikat o błędzie. W przeciwnym razie zwiększa top o 1 i umieszcza element na tej pozycji tablicy item.
• Pop(): Usuwa i zwraca element z wierzchołka stosu. Jeśli stos jest pusty, wyświetla komunikat o błędzie i zwraca wartość “Bez elementów”. W przeciwnym razie pobiera element z pozycji top, zmniejsza top o 1 i zwraca pobrany element.
• Peek(): Zwraca wartość elementu z wierzchołka stosu bez usuwania go, analogicznie sprawdzając pustość stosu.
• Display(): Wyświetla wszystkie elementy stosu, iterując od wierzchołka do dołu.

Ograniczenia tej implementacji

Warto świadomie zauważyć dwie rzeczy, które odróżniają MyStack od wbudowanej klasy Stack<T> z .NET:

• Stały rozmiar — MyStack nie powiększa się automatycznie. Po osiągnięciu stackSize metoda Push po prostu wypisuje komunikat i milcząco nie dodaje elementu — nie rzuca wyjątku, co w kodzie produkcyjnym łatwo przeoczyć. Wbudowany Stack<T> realokuje tablicę wewnętrzną automatycznie.
• Brak typowania generycznego — object[] item oznacza, że na stos trafi dosłownie wszystko, a odczyt wymaga rzutowania. Produkcyjna wersja powinna być generyczna: IStack<T> i T[] item, tak jak robi to Stack<T> z biblioteki standardowej.

To nie błędy — to świadome uproszczenia dydaktyczne, dzięki którym widać goły mechanizm stosu bez szumu generyków i zarządzania pamięcią. W kodzie produkcyjnym sięgnij po gotowy Stack<T> opisany w powiązanym artykule.

Stos w aplikacji konsolowej

I teraz skorzystamy z naszego stosu w aplikacji:

using System;

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

            while (true)
            {
                int choice = DisplayMenu();

                WorkWithAChoice(stack, choice);

                BackToMenu();
            }
        }

        private static int DisplayMenu()
        {
            Console.Clear();
            Console.WriteLine("\nStos MENU (rozmiar -- 10)");
            Console.WriteLine();
            Console.WriteLine("1. Dodaj element.");
            Console.WriteLine("2. Usuń element.");
            Console.WriteLine("3. Zobacz element.");
            Console.WriteLine("4. Wyświetl elementy stosu.");
            Console.WriteLine("5. Koniec programu");
            Console.WriteLine();
            Console.Write("Dokonaj wyboru co chcesz zrobić: ");
            int.TryParse(Console.ReadLine(), out int result);

            return result;
        }

        private static void WorkWithAChoice(MyStack stack, int choice)
        {
            switch (choice)
            {
                case 1:
                    Console.WriteLine("Wpisz element: ");
                    stack.Push(Console.ReadLine());
                    Console.WriteLine("Element został pomyślnie dodany!");
                    break;
                case 2:
                    Console.WriteLine("Element usunięty: {0}", stack.Pop());
                    break;
                case 3:
                    Console.WriteLine("Element na szczycie stosu to: {0}", stack.Peek());
                    break;
                case 4:
                    stack.Display();
                    break;
                case 5:
                    Environment.Exit(1);
                    break;
                default:
                    Console.WriteLine("Dokonałeś niewłaściwego wyboru!");
                    break;
            }
        }
        private static void BackToMenu()
        {
            Console.WriteLine("Nacisnij Enter aby przejsc do Menu");
            Console.ReadKey();
        }
    }
}

Program prezentuje interaktywne menu i pozwala użytkownikowi dodawać, usuwać, podglądać i wyświetlać elementy stosu — dobry poligon do samodzielnego eksperymentowania z mechanizmem LIFO, zanim sięgniesz po gotowy Stack<T> w prawdziwym projekcie.

Podsumowanie

Klasa MyStack implementuje interfejs IStack, definiując podstawowe operacje stosu LIFO: dodawanie (Push), usuwanie (Pop), podgląd (Peek) i wyświetlanie (Display) elementów na tablicy o stałym rozmiarze. To dobre ćwiczenie do zrozumienia mechaniki stosu “od środka” — w kodzie produkcyjnym użyj wbudowanego, dynamicznego i generycznego Stack<T>.