I_R_W13A_M03_JAVA Zaawansowane struktury danych
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.

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.

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 elementów. Indeks wskazujący szczyt jest przechowywany jako zmienna indeks_szczytu. Tablicę indeksujemy od wartości .
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.
Kolejka
Każdy z nas miał do czynienia z kolejką w sklepie. Zasada jej działania jest dosyć prosta: osoba, która znajduje się przed nami, pojawiła się wcześniej, a więc zostanie wcześniej obsłużona. Tak samo działa struktura danych zwana kolejką.
Kolejka jest przeciwieństwem stosu, jeśli chodzi o sposób dodawania i usuwania elementów. Nazywamy ją strukturą typu FIFO (z ang. First In First Out, czyli „pierwszy na wejściu, pierwszy na wyjściu”). Nowy element jest dodawany na końcu kolejki. Natomiast jako pierwszy usuwany jest element z początku kolejki.
Kolejka może być wykorzystana np. w teorii grafów w algorytmie przeszukiwania grafu wszerz.

Tak jak w przypadku stosu, nie możemy użyć indeksowania, aby odwołać się do dowolnych elementów składających się na kolejkę. Jesteśmy w stanie tylko odczytać wartości znajdujące się na jej początku.
Implementacja kolejki z zastosowaniem tablicy
Kolejka także jest strukturą dynamiczną, lecz możemy ją zaimplementować, używając statycznej tablicy. Jedynym ograniczeniem jest maksymalna liczba przechowywanych w kolejce elementów.
Aby kolejka działała poprawnie, konieczne jest użycie dwóch zmiennych. Jedna z nich będzie wskazywała początek kolejki, natomiast druga jej koniec.

Poniżej znajdują się zapisane za pomocą pseudokodu funkcje wykorzystywane podczas dodawania i usuwania elementów kolejki. Zakładamy, że kolejka jest reprezentowana przez tablicę kolejka o rozmiarze elementów. Indeksy początku oraz końca kolejki są przechowywane w postaci zmiennych indeks_poczatek oraz indeks_koniec. Początkowa wartość indeks_poczatek wynosi . Zmienną indeks_koniec inicjalizujemy z kolei wartością o jeden mniejszą, czyli . Tablicę indeksujemy od wartości .