Stos

Stos (ang. stack)

Stos można traktować jako kontener do którego możemy wrzucać kolejne obiekty określonego typu czyli wykonać operację push(). Istnieje do niej operacja przeciwna pop(), która pozwala nam wyjąć obiekt z wierzchu kontenera. Innymi słowy nie możemy wyjąć obiektu na którym coś zostało położone. Stos pozwala również sprawdzić czy kontener nie jest pusty operacją isEmpty().

Wyjaśnienie działania

Bierzemy pudełko. Jesteśmy w stanie określić czy jest puste zaglądając do środka. Włóżmy teraz kolejno dwie kartki: czerwoną, potem zieloną. Zajrzyjmy do pudełka. Nie widzimy dna, ale zieloną kartkę. Jednak możemy powiedzieć, że pudełko nie jest puste chociaż nie widzimy dna pudełka. Spróbujmy teraz wyjąć kartki. Najpierw wyjmiemy zieloną, a potem czerwoną kartkę.

Zalety

• prosta implementacja
• szybkie działanie
• minimalne obciążenie

Wady

• odwołanie tylko do pierwszego elementu
• mała ilość funkcji do manipulowania danymi
• w przypadku zbierania akcji do wykonania, brak możliwości nadawania priorytetów

Implementacja

Struktury

Deklarowana klasa Stos będzie typu ogólnego T. Pozwoli to na przechowywanie tam dowolnych obiektów, które zostaną określone podczas deklaracji zmiennej.

1. class Stos<T> {

Każdy odłożony obiekt na stos zostanie zapisany jako typ Element, który może przechowywać obiekt jak i będzie mogło wskazywać na konkretny element położony pod nim.

1. class Element {
2.   T wartosc;
3.   Element el;
5.   public T Wartość {
6.     get { return wartosc; }
7.   }
9.   public Element El {
10.     get { return el; }
11.   }
13.   public Element(T wartosc, Element el) {
14.     this.wartosc = wartosc;
15.     this.el = el;
16.   }
17. }

(2. - 3.) Deklaracja przechowywanych w obiekcie wartości i (5. - 7. oraz 9. - 11.) dostęp do każdej ze zmiennej. W celu ułatwienia elementów napisany został (13. - 16.) konstruktor.

Stos musi wiedzieć jaki element na nim leży, więc deklarowany jest element el, który będzie przechowywał pierwszy element od góry, albo wartość null jeśli stos jest pusty.

1. Element el;

Funkcje

Utworzenie nowego stosu polega jedynie na przypisaniu zmiennej el wartość null.

1. public Stos() {
2.   el = null;
3. }

Wiedząc, że jeśli nic nie leży na stosie to węzeł w nim jest równy null. W ten sposób funkcja czyPusty() zwróci prawdę tylko wtedy, gdy węzeł na stosie wynosi null:

1. public bool czyPusty() {
2.   return el == null;
3. }

Zauważywszy, że nasz stos jest pusty pora coś na niego położyć:

1. public void Połóż(T wartosc) {
2.   el = new Element(wartosc, el);
3. }

Funkcja Połóż() nic nie zwraca. Przyjmuje jedynie wartosc do położenia na stosie. Położenie nowego elementu (2.) polega na utworzeniu nowego węzła, który ma jako wartość przekazany argument i wskazuje na aktualny element na wierzchu el.

Brakuje już tylko jednej funkcji, która pozwoli zdjąć element (kartkę) z wierzchu:

1. public T Zdejmij() {
2.   T wartosc;
3.   if (czyPusty())
4.     return default(T);
5.   wartosc = el.Wartość;
6.   el = el.El;
7.   return wartosc;
8. }

Funkcja Zdejmij() zwraca element typu T dla danego stosu. Na początek (2.) deklarujemy zmienną value typu T. Następnie (3.) musimy sprawdzić czy stos nie jest pusty. Jeśli tak to (4.) zwracamy domyślną wartość elementu T. Będzie to znaczyło, że nie mamy czego zdjąć ze stosu. Jeśli jednak stos nie jest pusty to (5.) kopiujemy wartość elementu z wierzchu. (6.) Teraz stos musi wiedzieć, że kolejnym elementem już nie będzie pobrany, a ten na który wskazywał pobrany element. (7.) Na koniec zwracamy odczytaną wartość wartosc.

Testowanie implementacji

Na sam koniec testujemy naszą aplikację:

1. static void Main(string[] args) {
2.   Stos<int> st = new Stos<int>();
4.   Console.Write(" wrzucamy: ");
5.   for (int i = 1; i <= 5; i++) {
6.     st.Połóż(i);
7.     Console.Write("{0} ", i);
8.   }
9.   Console.Write("\nzdejmujemy: {0}", st.Zdejmij());
10.   Console.Write("\n wrzucamy: 10\n");
11.   st.Połóż(10);
13.   Console.Write("zdejmujemy: ");
14.   while (!st.czyPusty())
15.     Console.Write("{0} ", st.Zdejmij());
17.   Console.ReadKey();
18. }

i otrzymujemy:

1.   wrzucamy: 1 2 3 4 5
2. zdejmujemy: 5
3.   wrzucamy: 10
4. zdejmujemy: 10 4 3 2 1

• Kod źródłowy Implementacja