Metody programowania /StosyKolejki
Spośród wielu struktur danych używanych w informatyce dwie mają szczególne znaczenie. Charakteryzuje je prostota koncepcji, łatwość implementacji i przydatność w rozwiązywaniu rozmaitych problemów algorytmicznych. Są to stosy i kolejki. Ogólnie chodzi o niezwykle ważny w informatyce problem reprezentacji zbiorów skończonych. Bardzo często bowiem potrzebujemy przechowywać zbiory elementów pewnej przestrzeni, potencjalnie bardzo dużej (np. wszystkie możliwe rezerwacje lotnicze dla wszystkich ludzi na świecie) w taki sposób, żeby efektywnie móc wykonywać podstawowe trzy operacje:
- sprawdzenie, czy dany element znajduje się w zbiorze
- dodanie elementu do zbioru
- usunięcie elementu ze zbioru.
Problem ten dokładnie jest opisany w kursie "Algorytmy i struktury danych", tu jednak chcemy zająć się jego wersją, związaną z pewną specyfiką, gdy zależy nam na wykonaniu jakiejś czynności dla każdego elementu zbioru i to w kolejności narzuconej przez nasze wymagania. O ile na wkładanie elementu do zbioru nie mamy wpływu - po prostu trzeba akceptować każde żądanie - o tyle w przypadku pobierania elementów ze zbioru mamy pewną dowolność. Podstawowe dwie strategie, które będziemy tu rozważać, to
- strategia stosowa, kiedy pobieramy elementy w kolejności odwrotnej do wkładania, czyli jako pierwszy będzie pobrany element, który został włożony jako ostatni (LIFO: Last-In-First-Out)
- strategia kolejkowa, kiedy pobieramy elementy w kolejności zgodnej z kolejnością wkładania, czyli jako pierwszy będzie pobrany element, który został włożony najdawniej (FIFO: First-In-First-Out)
Podstawowe operacje zatem, które będziemy rozważali będą następujące:
- Utwórz pusty zbiór
- Sprawdź, czy zbiór jest pusty (chodzi m.in. o zabezpieczenie przed próbą pobrania elementu z pustego zbioru)
- Dodaj element do zbioru
- Pobierz element ze zbioru, usuwając go z niego.
W zależności od tego, czy stosujemy strategię stosową, czy listową, zastosujemy różne implementacje. Zacznijmy od stosów.
Przedstawimy tu dwie najpopularniejsze implementacje stosów: tablicową i listową.
Tablicowa implementacja stosów
Stosy będziemy reprezentować jako parę (tablica T, indeks p pierwszego wolnego miejsca). Włożenie nowego elementu będzie polegać na wstawieniu go pod indeksem p i zwiększenie indeksu p o 1. Pobranie będzie polegało na zmniejszeniu indeksu p o 1 i odczytaniu znajdującej się tam wartości. Utworzenie pustego stosu będzie sprowadzało się do inicjalizacji wskaźnika na 1, a sprawdzenie, czy stos jest pusty na sprawdzeniu, czy indeks p jest równy 1. Oto komplet procedur stosowych:
