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

Chcąc napisać stos musimy określić jaki typ danych będzie tam przechowywany. Przyjmijmy, że na potrzeby dzisiejszego przykładu typ T będzie aliasem zmiennej typu int:

1. typedef int T;

Potrzebujemy jeszcze zdefiniować tzw. węzły. Węzeł będzie nam przechowywać wartość danego elementu (np. kolor kartki papieru) oraz wskaźnik na inny węzeł (określi nam jaka kartka na nim leży).

1. struct Element{
2.   T value;
3.   Element* element;
4. };

I na sam koniec potrzebujemy określić strukturę stosu (pudełka). Struktura będzie przechowywać wskaźnik na węzeł (dno pudełka):

1. struct Stack{
2.   Element* element;
3. };

Funkcje

W celu uproszczenia sobie zadania napiszmy też funkcję, która stworzy dla nas nowy stos:

1. Stack* createStack(){
2.   Stack* st = new Stack;
3.   st->element = NULL;
4.   return st;
5. }

Funkcja zwraca nam wskaźnik na nowy stos. W środku funkcji (2.) tworzymy nowy stos, a następnie (3.) przypisujemy węzłowi wartość NULL. Będzie to oznaczało, że na stosie nic nie leży (widzimy dno pudełka). Na sam koniec (4.) zwracamy wskaźnik na nowy stos.

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 isEmpty() zwróci prawdę tylko wtedy, gdy węzeł na stosie wynosi NULL:

1. bool isEmpty(Stack* st){
2.   return st->element == NULL;
3. }

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

1. void push(Stack* st, T value){
2.   Element* el = new Element;
3.   el->value = value;
4.   el->element = st->element;
5.   st->element = el;
6. }

Funkcja push() nic nie zwraca. Przyjmuje dwa argumenty: wskaźnik na stos i element do umieszczenia na stosie. Pierwszy krok (2.) polega na utworzeniu nowego węzła. Następnie (3.) przypisujemy mu wartość daną jako argument T value. Używamy strzałki, ponieważ el jest wskaźnikiem. Wskaźnikowi nowego węzła (3.) przypisujemy adres jaki wskazuje stos. Od teraz stos wskazuje nam na nowo utworzony element.

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

1. T pop(Stack* st){
2.   T value;
3.   if(isEmpty(st)){
4.     value = NULL;
5.     return value;
6.   }
7.   Element* el = st->element;
8.   value = el->value;
9.   st->element = el->element;
10.   delete el;
11.   return value;
12. }

Funkcja pop() 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.) value ustawiamy na NULL i (5.) zwracamy. Będzie to znaczyło, że nie mamy czego zdjąć ze stosu. Jeśli jednak stos nie jest pusty to (6.) pobieramy wskaźnik węzła. (7.) Kopiujemy wartość węzła do value. (8.) Teraz stos musi wiedzieć, że kolejnym elementem już nie będzie pobrany, a ten na który wskazywał węzeł. (9.) Na sam koniec usuwamy z pamięci węzeł el i (10.) zwracamy value.

Testowanie implementacji

Na sam koniec testujemy naszą aplikację:

1. T pop(Stack* st){
2.   T value;
3.   if(isEmpty(st)){
4.     value = NULL;
5.     return value;
6.   }
7.   Element* el = st->element;
8.   value = el->value;
9.   st->element = el->element;
10.   delete el;
11.   return value;
12. }

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