Implementowanie Stosu

Mariusz Jurczenko Mariusz Jurczenko

Stos to struktura danych typu LIFO (Last In, First Out), co oznacza, że ​​pierwszy element dodany do stosu jest ostatnim, 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.

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 interface.

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 (Last In, First Out). Poniżej krok po kroku wyjaśniono działanie każdej metody i używanych zmiennych:

1. 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.

2. 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 i inicjuje tablicę item.

3. Metody:

  • isEmpty():Sprawdza, czy stos jest pusty. Zwraca true, jeśli top jest równy -1 (wskaźnik wskazuje na pozycję przed pierwszym elementem), co oznacza brak elementów.
  • Push(object element):Dodaje nowy element 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. * Umieszcza element na pozycji top tablicy item.
  • Pop():Usuwa i zwraca element z wierzchołka stosu. Sprawdza, czy stos jest pusty (gdy top jest równy -1). Jeśli tak, wyświetla komunikat o błędzie i zwraca wartość "Bez elementów". W przeciwnym razie: * Pobiera element z pozycji top tablicy item. * Zmniejsza top` o 1. * Zwraca pobrany element.
  • Peek():Zwraca wartość elementu z wierzchołka stosu bez usuwania go. Sprawdza, czy stos jest pusty (gdy top jest równy -1). Jeśli tak, wyświetla komunikat o błędzie i zwraca wartość "Bez elementów". W przeciwnym razie zwraca element z pozycji top tablicy item`.
  • Display():Wyświetla wszystkie elementy stosu. Sprawdza, czy stos jest pusty (gdy top jest równy -1`). Jeśli tak, wyświetla komunikat o braku elementów. W przeciwnym razie iteruje po elementach stosu od wierzchołka do dołu i wyświetla je wraz z ich numerami.

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();
        }
    }
}

Użycie klasy MyStack w programie

Ten kod przedstawia przykładowe wykorzystanie klasy MyStack w programie konsolowym, który pozwala użytkownikowi na operowanie stosem.

1. Program MyStack.Program:

  • Metoda Main tworzy instancję klasy MyStack i wchodzi w pętlę while.
  • W pętli:
    • Wyświetla menu z dostępnymi opcjami.
    • Pobiera wybór użytkownika.
    • Wywołuje metodę WorkWithAChoice do wykonania wybranej operacji na stosie.
    • Wyświetla komunikat “Nacisnij Enter…” i czeka na naciśnięcie klawisza Enter, aby powrócić do menu.

2. Metoda DisplayMenu:

  • Wyświetla czyste okno konsoli.
  • Wyświetla nagłówek “Stos MENU” i informację o domyślnym rozmiarze stosu (10).
  • Wyświetla listę dostępnych opcji (dodanie elementu, usunięcie elementu, itp.) wraz z ich numerami.
  • Podaje instrukcje dotyczące wprowadzania wyboru.
  • Pobiera wybór użytkownika z konsoli i próbuje przekonwertować go na liczbę całkowitą (int).
  • Zwraca wprowadzoną liczbę całkowitą (wybór użytkownika).

3. Metoda WorkWithAChoice:

  • Przyjmuje instancję stosu (stack) i wybraną opcję (choice) jako argumenty.
  • Używa instrukcji switch do wykonania odpowiedniej operacji na podstawie wyboru użytkownika:
    • Przypadek 1: Dodanie elementu.
      • Pobiera element od użytkownika z konsoli.
      • Wywołuje metodę Push stosu, aby dodać element do stosu.
      • Wyświetla komunikat potwierdzający dodanie elementu.
    • Przypadek 2: Usunięcie elementu.
      • Wywołuje metodę Pop stosu, aby usunąć element z wierzchołka.
      • Sprawdza, czy operacja się udała.
        • Jeśli tak, wyświetla usunięty element.
        • Jeśli nie, wyświetla komunikat o pustym stosie.
    • Przypadek 3: Podgląd elementu na szczycie.
      • Wywołuje metodę Peek stosu, aby uzyskać element na szczycie.
      • Sprawdza, czy operacja się udała.
        • Jeśli tak, wyświetla element na szczycie.
        • Jeśli nie, wyświetla komunikat o pustym stosie.
    • Przypadek 4: Wyświetlenie wszystkich elementów.
      • Wywołuje metodę Display stosu, aby wyświetlić wszystkie elementy w stosie.
    • Przypadek 5: Zakończenie programu.
      • Wywołuje metodę Environment.Exit(1), aby zakończyć program z kodem błędu 1.
    • Domyślny:
      • Wyświetla komunikat o błędnym wyborze.

4. Metoda BackToMenu:

  • Wyświetla komunikat “Nacisnij Enter, aby przejść do menu”.
  • Czeka na naciśnięcie klawisza Enter, aby powrócić do menu głównego.

W skrócie:

Ten program demonstruje, jak wykorzystać klasę MyStack do tworzenia stosu i wykonywania podstawowych operacji na nim. Użytkownik może dodawać, usuwać, wyświetlać elementy i sprawdzać stan stosu za pomocą interaktywnego menu.

Wnioski

Przedstawiony kod demonstruje implementację stosu LIFO (Last In, First Out) w języku C#. Klasa MyStack implementuje interfejs IStack, definiując podstawowe operacje stosu: dodawanie (Push), usuwanie (Pop), podgląd (Peek) i wyświetlanie (Display) elementów. Program demonstruje przykładowe użycie klasy MyStack w aplikacji konsolowej, która pozwala użytkownikowi na interakcję ze stosem.

Istotne cechy implementacji:

  • Klasa MyStack wykorzystuje tablicę item do przechowywania elementów stosu.
  • Zmienna top wskazuje na aktualny wierzchołek stosu.
  • Metody Push i Pop aktualizują wskaźnik top i tablicę item, aby dodawać lub usuwać elementy.
  • Metoda Peek zwraca element z wierzchołka stosu bez usuwania go.
  • Metoda Display wyświetla wszystkie elementy stosu.

Program konsolowy umożliwia użytkownikowi wybór operacji, takich jak dodawanie, usuwanie, podgląd lub wyświetlanie elementów stosu. Wyświetla również komunikaty o błędach i informacje o stanie stosu.

Zakończenie

Powyższy kod stanowi przykład implementacji stosu LIFO w języku C#. Demonstruje podstawowe operacje stosu i sposób ich wykorzystania w aplikacji konsolowej. Można go rozbudować o dodatkowe funkcje, takie jak sprawdzanie rozmiaru stosu, dodawanie możliwości usuwania wielu elementów naraz, czy implementację stosu dynamicznego.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *