Pojęcia "stos" używamy w języku naturalnym w odniesieniu do grupy przedmiotów w pewien sposób ułożonych. Mówimy o stosie listów, stosie spraw do załatwienia, stosie książek lub talerzy itd. Każdy wie, że próba wyciągnięcia czegoś ze środka stosu, kończy się zwykle jego zburzeniem. Wobec tego bierzemy zwykle, np. list ze szczytu stosu i odkładamy na szczyt stosu.

Stos w informatyce jest pewną abstrakcją tego pojęcia. Służy do przechowywania skończonego zbioru elementów i umożliwia wykonywanie operacji wkładania i usuwania elementów. Obowiązuje przy tym zasada, że obie operacje są wykonywane na tym samym końcu ciągu. Krótko zasadę rządzącą stosami zapisujemy jako LIFO -  last in, first out.

Operacja push pozwala wstawić nowy element do ciągu, operacja pop pozwala usunąć ostatnio włożony do stosu element. Wynikiem operacji top jest ostatnio włożony element. Obie operacje pop i top są operacjami częściowymi, nieokreślonymi dla ciągu pustego. Empty jest relacją odpowiadającą na pytanie, czy stos jest pusty, a równość stosów jest zdefiniowana tak, jak równość ciągów.

Stos może być reprezentowany  w komputerze na wiele różnych sposobów. W dalszym ciągu tego punktu przedstawimy dwie jego implementacje.

Implementacja I

Implementacja tablicowa stosu jest jedną z prostszych. Zasadnicza jej idea została przedstawiona na rysunku 6.1. Stos jest tu obiektem pewnej klasy STACK o dwóch atrybutach TAB i idx. Tablica  TAB służy do zapamiętania wkładanych na stos elementów, a wskaźnik idx zawsze wskazuje indeks elementu będącego aktualnie na szczycie stosu. Na rysunku 6.1, na szczycie stosu znajduje się element e_i. Wcześniej włożono do tego stosu elementy e₁, e₂, ..., e_i-1.

Metodami, dostępnymi dla obiektów klasy stos, powinny być  funkcje  push, pop, top i empty. Ustalmy, że stos jest pusty, gdy atrybut idx wskazuje  zero. Operacja włożenia elementu x do stosu s przedstawionego na rysunku 6.1, może być zaimplementowana następująco:

push(x,s){ if empty(s) then s.idx := 1 else s.idx := i+1 fi; s.TAB[idx] := x; return s}.

Oczywiście treścią funkcji top(s) jest {return s.TAB[idx];}. Jest to funkcja częściowa, nieokreślona dla stosu pustego. W praktyce zwykle w treści funkcji top umieszcza się obsługę błędu pustości. Operacja pop, która ma powodować usunięcie elementu ostatnio wstawionego na stos może mieć następującą treść

pop(s){s.TAB[idx] := null; s.idx := s.idx-1; return s;}

Operacja pop, jak już wspomniano wcześniej,  jest też operacją częściową: daje poprawny wynik tylko wtedy, gdy stos s nie jest pusty. Utworzenie nowego, pustego, stosu powinno polegać na utworzeniu obiektu z pustą tablicą TAB i wskaźnikiem idx równym 0. J

Kłopot, z przedstawioną implementacją I, polega na tym, że na ogół nie wiemy, ile elementów znajdzie się jednoczenie na stosie. W związku z tym, trudno jest  powiedzieć w chwili tworzenia stosu pustego, jaka powinna być wartość n. Jest na to rada. Jeżeli element, który chcemy włożyć do stosu jest (n+1)-szym przechowywanym w nim elementem, to przepisujemy wszystkie elementy do większej (np. dwa razy większej) tablicy. Komplikuje to jednak kod operacji push, a przede wszystkim, istotnie zwiększa jej koszt: z kosztu stałego przechodzimy do kosztu rzędu n, gdzie n jest aktualną długością tablicy. Unikniemy tego problemu, jeśli zamiast tablicy użyjemy dynamicznej struktury dowiązaniowej, o której mowa w następnej implementacji.

Implementacja II

Niech LINK będzie pewnym typem obiektów, z których każdy ma dwa atrybuty: val - typu element  i prev - typu  LINK,

 val -wartość przechowywanego elementu, prev - wskaźnik do elementu poprzedniego. 

Przedstawimy teraz stos, jako obiekt pewnej klasy abstrakcyjnej STACK z jednym tylko atrybutem head typu LINK. Jeśli na stosie znajdują się trzy elementy a, b, c, to stos może mieć postać przedstawioną na rysunku 6.2 

Sprawdzenie, jaki element został ostatnio włożony na stos, polega na sprawdzeniu atrybutu val  w obiekcie wskazanym przez głowę stosu, head. Włożenie elementu na stos powoduje stworzenie nowego obiektu typu LINK i dowiązanie do niego starej zawartości stosu (wskazanej przez atrybut head). W ten sposób na szczycie stosu znajduje się zawsze ten element, który był ostatnio do niego wkładany. Operacje na stosach tego typu mogą wyglądać następująco:

ELEMENT top(s){return s.head.val}

STACK push(x,s){pom := new LINK(); pom.val := x; pom.prev := s.head; s.head := pom; return s}

STACK pop(s){s.head := s.head.prev; return s}

s jest zmienną typu STACK, a x zmienną pewnego typu ELEMENET. Natura elementów typu ELEMENT nie jest istotna i może być dowolnie zdefiniowana przez użytkownika. J

Pytanie 1

Na stos s włożono kolejno litery a,b,c,d,e, a następnie odczytano i wypisano zawartość stosu. W jakiej kolejności pojawią się litery na wyjściu?

Zauważmy, że te dwie wymienione implementacje różnią się wieloma elementami. Czym mamy się kierować w wyborze tej lub innej implementacji? Jak rozpoznać, czy implementacja stosów jest poprawna? Co to znaczy, że implementacja stosów jest poprawna?  Na ogół interesują nas pewne specjalne cechy, które odróżniają stosy od innych struktur i pozwalają zaakceptować lub odrzucić przedstawioną implementację. Taki zbiór własności nazywamy specyfikacją struktury danych (por. wykład I, p.3).

Specyfikacja struktury stosów

Niech s oznacza dowolny stos, a x dowolny element. Następujące formuły charakteryzują podstawowe własności stosów i operacji na nich.

(S1) Ø empty(push(x,s)),

(S2) top(push(x,s)) = x,

(S3) pop(push(x,s)) = s,

(S4) Ø empty(s) => push(top(s),pop(s)) = s,

(S5)  każdy stos składa się ze skończonej liczby elementów,

(S6) dwa stosy są równe, jeśli składają się z tych samych elementów i jeśli umieszczono je w takiej samej kolejności.

Pierwszy z postulatów stwierdza, że po włożeniu elementu x stos nie jest pusty. Drugi postulat stwierdza, że funkcja top zwraca ten element, który był ostatnio na stos włożony. Następne dwa postulaty charakteryzują zależności między pop i push. Jeśli modyfikacja stosu s polegała na włożeniu elementu x, to wykonanie operacji pop na zmodyfikowanym stosie spowoduje powrót do stanu poprzedniego. Jeśli stos nie jest pusty oraz x=top(s) jest na jego szczycie, to po wykonaniu operacji pop, a następnie włożeniu na stos elementu  x wrócimy do początkowego stanu stosu. 

Postulaty (S5) i (S6) mają nieco inny charakter niż pozostałe, nie można ich wyrazić przez formuły logiki klasycznej. Łatwo jest natomiast opisać, odpowiadającą im własność, za pomocą programów. Jeżeli program:

P1{while not empty(s) do s := pop(s) od}

nie zapętla się, to tylko skończona liczba elementów znajdowała się na stosie s. I odwrotnie, jeśli na stosie znajdują się elementy e₁,e₂,..., e_n, to po n wykonaniach operacji pop, stos zostanie opróżniony. Zatem program P1 zatrzyma się. Możemy więc przyjąć, że cechą charakterystyczną stosów, jest niezapętlanie się tego programu.

Podobnie, niech P2 będzie następującym algorytmem, w którym s i s* są dowolnymi stosami:

P2{bool := true;
while (not empty(s) and not empty(s*) and bool) do
        bool := (top(s) = top(s*));
        s:= pop(s); s*:= pop(s*);
od }

Jeżeli program P2 zatrzymuje się i wartością zmiennej bool jest true, to znaczy, że stosy s i s* mają po tyle samo elementów, a elementy na tych samych pozycjach w stosach s i s* są identyczne: zmienna bool może zmienić wartość na false, tylko wtedy, gdy elementy na szczytach stosów są różne. Wynika stąd, że własność mówiąca, że po wykonaniu programu P2 spełniona jest formuła (bool Ù empty(s)  Ù empty(s*)) charakteryzuje równość stosów.

Zauważmy, że niezależnie od tego, czy myślimy o stosie jako ciągu, tak jak standardowej strukturze stosów, czy jako o obiekcie przedstawionym w implementacji pierwszej lub drugiej, wszystkie wymienione postulaty są spełnione. Co więcej, postulaty te możemy traktować jak definicję struktury stosów, ponieważ każdy model zbioru postulatów (S1),..., (S6) jest izomorficzny z modelem standardowym wyznaczonym przez ten sam zbiór elementów. Mamy w ten sposób kryterium, które pozwoli rozstrzygnąć, czy dana implementacja stosów jest poprawna: wystarczy sprawdzić prawdziwość formuł (S1), ..., (S6).

Pytanie 2: Jaki jest koszt wyszukania dowolnego elementu w stosie składającym się z n elementów?

« poprzedni punkt

następny punkt »