ALG0

130

Rozdział 5. Struktury danych

Symboliczny stos znajdujący się pod każdą z sześciu grup instrukcji ukazuje I zawsze stan po wykonaniu „swojej” grupy instrukcji. Jak można łatwo zauważyć, I operacje na stosie przebiegały pomyślnie do momentu osiągnięcia jego całkowitej pojemności; wówczas stos zasygnalizował sytuację błędną.

Jakie są typowe realizacje stosu? Najpopularniejszym sposobem jest użycie | tablicy i zarezerwowanie jednej zmiennej w celu zapamiętania liczby danych I aktualnie znajdujących się na stosie. Jest to dokładnie taki sam pomysł, jak ten zaprezentowany na rysunku 5 - 10, z jednym zastrzeżeniem: mimo iż wiemy, jak stos jest zbudowany „od środka”, nie zezwalamy nikomu na bezpośredni dostęp do niego. Wszelkie operacje odkładania i zdejmowania danych ze stosu muszą się odbywać za pośrednictwem metod jnish i pop. Jeśli zdecydujemy się na zamknięcie danych i funkcji służących do ich obsługi w postaci klasy, to wówczas automatycznie uzyskamy „bezpieczeństwo” użytkowania - zapewni je sama koncepcja programowania zorientowanego obiektowo. Taki właśnie sposób postępowania obierzemy.

Możliwych sposobów realizacji stosu jest mnóstwo; wynika to z faktu, iż ta struktura danych nadaje się doskonale do ilustracji wuelu zagadnień algorytmicznych. Dla naszych potrzeb ograniczymy się do bardzo prostej realizacji tablicowej, która powinna być uważana raczej za punkt wyjścia niż za gotową implementację.

W związku z założonym powyżej celowym uproszczeniem, definicja klasy STOS jest bardzo krótka:

stos. li

const int DLUGOSC_MAX=300; oonst int STOS_PELNY-3; const int STOS_PUSTY=2; const int OK-1;

template <class TypPodst> class STOS (

TypPodst t[U„UGOSC_MAX+l|; stos=t[0]...t(DLUGOSC_MAX]

int szczyt;    // szczyt = pierwsza WOLNA komórka

public:

STOS() ( szczyt=0;I    II konstruktor

void clearO ( szczyt=0; ) II zerowanie stosu int push(TypPodst x); int pop (TypPodst Sw); int StanSt03u();

); // koniec definicji klasy STOS

Nasz stos będzie mógł potencjalnie służyć do przechowywania danych wszelakiego rodzaju, z tego też powodu celowe wydało się zadeklarowanie go w postaci tzw. klasy szablonowej, co zostało zaznaczone przez słowo kluczowe template.

^J Czyli dokonamy tzw. hermetyzacji.