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.

 

źródło

Tagi: