Stos, czyli struktura danych typu LIFO w języku C#

STOS

Stos to kolekcja elementów, w której ostatni dodany do niej element jest pierwszym, który możemy z niej odczytać.

Stos nazywamy również strukturą danych typu LIFO (ang. Last in First Out) ponieważ możemy wyciągnąć z niego najpierw element, który został do niego dodany najpóźniej. 

Stos działa dokładnie tak jak stos talerzy ułożonych jeden na drugim. Możemy zdjąć z niego tylko ten talerz, który znajduje się na samej górze. Nie możemy natomiast wyciągnąć talerza który jest na przykład na samym dole.

Wewnętrzna reprezentacja stosu

W języku C# istnieje wbudowana klasa System.Stack<T>. Jest to generyczna klasa, która przechowuje elementy takiego typu jaki podamy w nawiasach kątowych.

Stos jest w pamięci zapisywany tak samo jak tablica obiektów, która ma domyślnie rozmiar 4MB (a w starszych komputerach z procesorem 32-bitowym był to tylko 1 MB).  

Klasa ta posiada 4 metody:

• Push – metoda sprawdza najpierw czy pojemność stosu (czyli domyślnie 4 MB) pozwala na włożenie do niego jeszcze jednego elementu. Jeśli jest miejsce na stosie to element jest dodawany na samą jego górę. Jeśli na stosie nie ma już miejsca bo znajduje się na nim więcej niż 4 MB danych to następuje alokacja pamięci o większym rozmiarze.
• Pop – usuwa element ze szczytu stosu i ustanawia element poniżej nowym szczytem stosu 
• Peek – umożliwia sprawdzenie jaki jest element na szczycie stosu ale bez usuwania go
• Contains – sprawdzenie czy dany element znajduje się na stosie

Wydajność

Stos jako struktura danych najbardziej przydaje się kiedy odczytujemy elementy od najnowszego do najstarszego. Stosy są wykorzystywane na przykład przez środowisko uruchomieniowe .NET przy śledzeniu wywołań kolejnych metod. W przeciwieństwie do tablicy stos nie umożliwia odczytania dowolnego elementu. Możemy odczytać tylko jeden okreslony element, który znajduje się na szczycie stosu. 

Przykład użycia Stosu w języku C#

using System;
using System.Collections.Generic;

namespace ConsoleApp
{

  class Program
  {
    static void Main(string[] args)
    {
        var customers = new Stack<string>();
        customers.Push("Darek");
        customers.Push("Jan");
        customers.Push("Anna");
        customers.Push("Maria");

        if(customers.Contains("Jan"))
        {
            Console.WriteLine("Jan jest obecny na stosie");
        }

        Console.WriteLine(customers.Peek());
        Console.WriteLine(customers.Pop());
        Console.WriteLine(customers.Pop());
        Console.WriteLine(customers.Pop());
        Console.WriteLine(customers.Pop());
    }
  }
}

}