ALG9

5.3. Stos 129

angielskiego skrótu UFO: Last-In-First-Out, co w wolnym tłumaczeniu oznacza „ostatni będą pierwszymi”. Do odkładania danych na wierzchołek stosu służy zwyczajowo funkcja o nazwie push(X), gdzie Ajest daną pewnego typu. Może to być dowolna zmienna prosta lub złożona: liczba, znak. rekord...

Podobnie, aby pobrać element ze stosu, używa się funkcji o nazwie pop(X), która załadowuje zmienną X daną zdjętą z wierzchołka stosu. Obie te podstawowe funkcje oprócz swojego głównego zadania, które zostało wzmiankowane wyżej, zwracają jeszcze kod błędu¹. Jest to stała typu całkowitego, która informuje programistę, czy czasem nie nastąpiła sytuacja anormalna, np. próba zdjęcia czegoś ze stosu w momencie, gdy był on już pusty', lub też próba odłożenia na nim kolejnej danej, w sytuacji gdy brakowało w nim miejsca (brak pamięci). Programowe realizacje stosu różnią się między sobą drobnymi szczegółami (ostateczne słowo w końcu ma programista!), ale ogólna koncepcja jest zbliżona do opisanej wyżej.

Zasada działania stosu może zostać zatem podsumowana dwiema regułami:

•    po wykonaniu operacji push(X) element X sam staje się nowym wierzchołkiem stosu „przykrywając” poprzedni wierzchołek (jeśli oczywiście coś na stosie już było);

•    jedynym bezpośrednio dostępnym elementem stosu jest jego wierzchołek.

Dla dokładniejszego zobrazowania zasady działania stosu proszę prześledzić kilka operacji dokonanych na nim i efekt ich działania patrz rysunek 5 - 16.

Rysunek przedstawia stos służący do zapamiętywania znaków. Stałe symboliczne Stos Pusty. OK i SlosPelny są zdefiniowane przez programistę w module zawierającym deklarację stosu. Wyrażają się one w wartościach typu int (co akurat nic ma specjalnego znaczenia dla samego stosu...). Nasz stos ma pojemność dwóch elementów, co jest oczywiście absurdalne, ale zostało przyjęte na użytek naszego przykładu, aby zilustrować efekt przepełnienia.

Nie jest to bynajmniej obowiązkowe!