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)