Stos

Koncepcja tej struktury dynamicznej jest bardzo prosta: stos przypomina wieżę budowaną z klocków. Nowe elementy układamy na szczycie.

W przypadku stosu mamy dostęp tylko do elementu ostatnio dodanego (umieszczonego najwyżej). Nie mamy do dyspozycji mechanizmu indeksowania, który pozwala odwołać się do pozostałych elementów. Możemy jedynie sprawdzić wartość znajdującą się na samym szczycie.

Podobnie dzieje się w przypadku usuwania elementów ze stosu. Możemy zdjąć z niego tylko element znajdujący się na szczycie.

RE8CO3B57HC65

Zasady dodawania i usuwania elementów ze stosu.
Na ilustracji znajduje się prostokąt po lewej stronie, od którego wychodzi strzałka do prostokątów poniżej z podpisem dodaj.
Po prawej stronie znajduje się prostokąt, do którego idzie strzałka z prostokąta poniżej z podpisem usuń.
Poniżej znajdują się cztery puste prostokąty ustawione jeden na drugim.

Bardzo ważną cechą opisanej struktury jest to, że element dodany do niej jako pierwszy, zostanie usunięty jako ostatni. Stos nazywamy strukturą typu LIFO (z ang. Last In First Out, czyli „ostatni na wejściu, pierwszy na wyjściu”).

Implementacja stosu z zastosowaniem tablicy

Stos jest strukturą dynamiczną – jego rozmiar może się zmieniać w trakcie działania programu. Dla ułatwienia zrozumienia stosu zaimplementujemy go na statycznej tablicy. Musimy jedynie zastanowić się, jaki maksymalny rozmiar powinien mieć budowany stos.

Do poprawnego działania stosu potrzebujemy tylko jednej zmiennej, która będzie przechowywała indeks szczytu stosu. Przy dodawaniu nowego elementu zwiększymy wartość zmiennej o jeden, a przy usuwaniu będziemy ją zmniejszać. Pierwszym („najniższym”) elementem stosu będzie pierwszy element przechowywany w tablicy.

R2LVGQ32UFH5S

Działanie stosu przy użyciu jednej zmiennej.
Na ilustracji znajduje się tablica podpisana jako: zawartość.
Tablica ta zawiera liczby: 8, 4, 3, nad czwartym polem widnieje podpis: szczyt stosu.
Reszta pól jest pusta.
Każde pole posiada swój indeks od 0 do 5, podpisany pod kolejnymi polami stosu.

Przeanalizujmy funkcje odpowiedzialne za dodawanie i usuwanie elementów stosu zapisane za pomocą pseudokodu. Zakładamy, że stos jest reprezentowany przez tablicę stos o rozmiarze $n$ elementów. Indeks wskazujący szczyt jest przechowywany jako zmienna indeks_szczytu. Tablicę indeksujemy od wartości $0$.

funkcja dodaj_na_stos(a):
	jeżeli indeks_szczytu >= n wykonaj:
		wypisz("Przepełnienie stosu")
	w przeciwnym razie wykonaj:
		stos[indeks_szczytu] ← a
		indeks_szczytu ← indeks_szczytu + 1

funkcja usun_ze_stosu():
	jeżeli indeks_szczytu = 0 wykonaj:
		wypisz("Stos jest już pusty")
	w przeciwnym razie wykonaj:
		indeks_szczytu ← indeks_szczytu - 1

funkcja odczytaj_ze_stosu():
	zwróć stos[indeks_szczytu - 1]

W zaprezentowanym programie bardzo ważne jest, że elementy nie są faktycznie usuwane z tablicy. Wystarczy jedynie zmniejszyć indeks przechowywany w zmiennej indeks_szczytu, ponieważ przy dodawaniu następnego elementu wartość komórki zostaje nadpisana. Jest to bardzo duże ułatwienie podczas implementowania struktury.

Przykładowe zastosowania stosu

Stos jest wykorzystywany powszechnie w przypadku programów pisanych w językach wysokiego poziomu. Używa się go do przechowywania adresów pamięci i zmiennych, a także jako miejsce do zapisywania zawartości rejestrów procesora.

Słownik