Stosy i kolejki jako elementarne struktury danych
Kolejka, czyli struktura FIFO
Najważniejsze właściwości kolejki, która jest często określana mianem FIFO (First In – First Out), co wolnym tłumaczeniu znaczy “pierwszy wchodzi – pierwszy wychodzi”.
Otóż kolejka jest rodzajem struktury przechowującej zbiór danych. Do tego zbioru mogą być dodawane nowe elementy, jak również “wyjmowane” z niego. W przypadku składowania danych w strukturze FIFO, nowy element jest wstawiany na koniec kolejki, natomiast pobieranie danych (wyjmowanie) z kolejki jest możliwe jedynie poprzez wyciągnięcie elementu znajdującego się na jej początku
Tak więc jedyne możliwe operacje do wykonania na kolejce to:
- dodanie elementu na koniec kolejki
- usunięcie (pobranie) pierwszego elementu z kolejki
Stos, czyli struktura LIFO
Stos (ang. stack) jest jedną z najważniejszych struktur danych używanych w algorytmach komputerowych. Podstawowe cechy można zawrzeć w stwierdzeniu “ostatni wchodzi – pierwszy wychodzi”, czyli w skrócie LIFO (Last In – First Out).
Obsługa stosu wygląda następująco: dostęp do danych ułożonych na stosie mamy umożliwiony tylko od góry – możemy sobie wyobrazić, że mamy przykładowo stos kart do gry. Kładziemy karty jedna na drugiej, potem kolejną, i jeszcze następną. Gdy przyjdzie nam ochota zobaczyć pierwszą z położonych kart, musimy najpierw zdjąć jedną kartę położoną jako ostatnia, potem jeszcze kilka kolejnych aż w końcu „dobrniemy” do interesującej nas karty. Musieliśmy się dostać aż na sam spód tego stosu.
Zazwyczaj przy implementacji stosu definiuje się dwie funkcje operujące na nim – najczęściej są nazywane w ten sposób:
- push(x) – czyli odłożenie obiektu na stos;
- pop() – ściągnięcie obiektu ze stosu i zwrócenie jego wartości;
Pierwsza z nich ma za zadanie odłożenie wartości zmiennej x na stos, natomiast funkcja pop pobiera argument leżący na wierzchu stosu i zwraca jego wartość. Podczas implementacji obu tych funkcji należy pamiętać o właściwej obsłudze błędów. Przed położeniem elementu na stosie należy sprawdzić, czy nie jest on pełny – jeśli tak, to program powinien sygnalizować błąd przepełnienia stosu. Podobnie jest w przypadku wywołania funkcji pop – na samym początku ciała funkcji powinno się stwierdzić, czy dany stos jest pusty – w razie odpowiedzi twierdzącej wypadałoby poinformować o błędzie niedomiaru.
Pliki do pobrania
