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:
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
Podstawowe operacje zatem, które będziemy rozważali będą następujące:
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ą.
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:
type stos = record T : array[1..n] of typ; //Zakładamy, że wszystkiego elementy na stosie będą tego samego typu p : Integer //indeks pierwszego wolnego elementu end
procedure MakeEmpty(var s : stos); //Inicjalizacja stosu pustego begin s.p:=1 end;
function Empty(const s : stos) : Boolean; //Sprawdzenie pustości stosu begin Empty := s.p=1 end;
procedure Push(var s : stos; x:typ); //Włożenie na stos elementu o wartości x begin s.T[s.p]:=x; s.p:=s.p+1 end;
procedure Pop(var s : stos; var x:typ); //Zdjęcie ze stosu najświeższego elementu begin //i przypisanie jego wartości parametrowi x x:=s.T[s.p]; s.p:=s.p-1 end;
type stos = ^record w : typ; //Zakładamy, że wszystkie elementy na stosie będą tego samego typu nast : stos //wskaźnik do kolejnego elementu end
procedure MakeEmpty(var s : stos); //Inicjalizacja stosu pustego begin s := nil end;
function Empty(const s : stos) : Boolean; //Sprawdzenie pustości stosu begin Empty := s = nil end;
procedure Push(var s : stos; x:typ); //Włożenie na stos elementu o wartości x var pom: stos; begin new(pom); pom^.w:=x; if s= nil then pom^.nast:=nil else pom^.nast:=s; s:=pom end;
procedure Pop(var s : stos; var x:typ); //Zdjęcie ze stosu najświeższego elementu var pom:stos; begin //i przypisanie jego wartości parametrowi x x:=s^.w; pom := s; s := pom^.nast; dispose(pom) end;
Często procedury stosowe mają postać funkcji: wartością procedury Push jest nowy stos, wartością procedury Pop jest wartość zdjętego elementu x.
Dodatkowo czasami stosuje się procedury upraszczające korzystanie ze stosów. Do najważniejszych należą procedury, które podajemy w implementacji tablicowej:
function Full(const s : stos) : Boolean; //Sprawdzenie, czy na stosie jest miejsce na kolejny element begin Full := s.p>n end;
procedure Top(const s : stos; x:typ); //Pobranie wartości z wierzchołka stosu bez zdejmowania elementu begin x:=s.T[s.p]; end;
procedure Erase(var s : stos); //Wyczyszczenie stosu begin s.p:=1 end;
Zauważmy, że wszystkie te procedury można zaimplementować za pomocą procedur podstawowych. W szczególności wykonanie procedury Top(s,x) jest równoważne wywołaniu pary Pop(s,x); Push(s,x). Procedura Erase(s) jest równoważna pętli while not Empty(s) do Pop(s,x). Procedura Full wymagałaby użycia własnej zmiennej zliczającej liczbę elementów na stosie.
Z kolejkami sprawa jest o tyle trudniejsza, że musimy na nich operować z obu stron: z jednej wkładamy elementy, z drugiej wyjmujemy. Przedstawimy trzy implementacje kolejek: dwie pierwsze odpowiadają zaproponowanym implementacjom stosowym, trzecia jest oryginalna i wykorzystuje listę cykliczną. Dla rozróżnienia tych podobnych operacji będziemy w przypadku kolejek używać polskich nazw procedur.
Tym razem ponieważ będziemy pobierali z drugiego końca, niż wkładali, kolejka będzie się ,,przesuwać w tablicy. Gdy dojdzie do końca, zawiniemy ją tak, że kolejne elementy będą się pojawiać od początku. Z przyczyn technicznych
type kolejka = record T : array[0..n] of typ; //Zakładamy, że wszystkiego elementy w kolejce będą tego samego typu pocz,kon : Integer //pocz - indeks pierwszego elementu, kon - indeks pierwszego wolnego end
Tym razem tablica reprezentująca n-elementową kolejkę będzie miała n+1 elementów. Dlaczego? Wkrótce się wyjaśni.
procedure TwórzPustą (var k : kolejka); //Inicjalizacja pustej kolejki begin k.pocz:=0; k.kon:=0 end;
function Pusta(const k : kolejka) : Boolean; //Sprawdzenie pustości kolejki begin Empty := k.pocz=k.kon end;
procedure Wstaw(var k:kolejka; x:typ); //Włożenie do kolejki elementu o wartości x begin k.T[s.kon]:=x; k.kon:=k.kon+1; if k.kon>n then s.kon:=0 end;
procedure Pobierz(var k:kolejka; var x:typ); //Pobranie z kolejki najświeższego elementu begin //i przypisanie jego wartości parametrowi x x:=s.T[s.pocz]; k.pocz:=k.pocz+1; if k.pocz>n then k.pocz:=0 end;
type kolejka = ecord pocz,kon : lista //pocz - wskaźnik do pierwszego elementu, kon - do ostatniego end>
procedure TwórzPustą(var k : kolejka); //Inicjalizacja pustej kolejki begin k.pocz := nil end;
function Pusta(const k : kolejka) : Boolean; //Sprawdzenie pustości kolejki begin Empty := k.pocz = nil end;
procedure Wstaw(var k:kolejka; x:typ); //Włożenie do kolejki elementu o wartości x var pom: lista; begin new(pom); pom^.w:=x; if k.pocz = nil then k.pocz:=pom; else k.kon^.nast:=pom; //k.kon zawsze po wstawieniu pokazuje na ostatni element k.kon:=pom end;
procedure Pobierz(var k:kolejka; var x:typ); //Pobranie z kolejki najstarszego elementu var pom:lista; begin //i przypisanie jego wartości parametrowi x x:=k.pocz^.w; pom := k.pocz; if k.pocz=k.kon then k.pocz:=nil //Kolejka jednoelementowa else k.pocz := k.pocz^.nast; dispose(pom) end;
Podobnie, jak poprzednio, dodatkowe procedury, analogiczne do stosowych, można napisać tak:
Tym razem sprawdzenie w implementacji tablicowej, czy kolejka jest pełna nie jest tak proste. gdybyśmy sprawdzali, czy kolejka ma n+1 elementów, to naturalny warunek k.pocz=k.kon, który stwierdzałby pełność, dawałby odpowiedź true zarówno wtedy, gdy kolejka byłaby pełna, jak i wtedy, gdy byłaby pusta. Stąd umowa, że za pełną uznamy kolejkę, w której jeszcze jeden element jest niezapisany. Zatem musimy (cyklicznie) dodać jedynkę do k.pocz i sprawdzić, czy jest ona równa k.kon.
function Pełna(const k:kolejka) : Boolean; //Sprawdzenie, czy w kolejce jest miejsce na kolejny element var i:Integer; begin i:=k.kon+1; if i>n then i:=0; Full := k.pocz=i end;
procedure Pierwszy(const k.kolejka; var x:typ); //Pobranie wartości z początku kolejki bez pobierania elementu begin x:=k.T[k.pocz]; end;
procedure Usuń(var k : kolejka); //Wyczyszczenie kolejki begin k.pocz:=k.kon end;
Zauważmy, że tym razem byłyby kłopoty z implementacją procedury Pierwszy przez procedury podstawowe. Procedura Usuń(k) jest równoważna pętli while not Pusta(k) do Pobierz(k,x). Procedura Pełna też, tak jak w przypadku stosów, wymagałaby użycia własnej zmiennej zliczającej liczbę elementów w kolejce.
Oczywiście można wyobrazić sobie też inne procedury rozszerzające korzystanie z kolejek, na przykład wartość drugiego elementu, czy liczba elementów kolejki. Implementację takich funkcji pozostawiamy, jako ćwiczenie.
Ciekawym rozwiązaniem jest użycie listy cyklicznej. Koniec kolejki pamiętamy jako dowiązanie do ostatniego elementu listy. Jego następnikiem będzie pierwszy element kolejki, zatem wszystkie operacje kolejkowe można będzie zrobić w czasie stałym. Przy usuwaniu trzeba sprawdzać, czy kolejka nie jest jednoelementowa, przy dodawaniu elementu, czy nie jest pusta. W pozostałych przypadkach zawsze wstawiamy za ostatnim elementem (procedura wstawza z wykładu o listach), a pobieramy zza ostatniego elementu, usuwając element stojący za ostatnim. Zrealizowanie tej implementacji pozostawmy jako ćwiczenie.
Implementacja ta ma niewątpliwy walor estetyczny. Poszczególne operacje mogą być trochę kosztowniejsze - raptem jedno-dwa przypisania - ale nie powinno to stanowić powodu do odrzucenia tego pomysłu.
Rzecz jasna, porównując podane implementacje warto się zastanowić, która z nich jest najefektywniejsza. Implementacja tablicowa jest najszybsza. Wymaga jednak z góry zarezerwowanej pamięci. Jeśli mamy do czynienia z wieloma kolejkami o nieustalonej długości, to implementacja listowa daje elastyczność rezerwowania pamięci skrojonej na miarę problemu, co może być bardzo ważnym aspektem, szczególnie gdy liczba kolejek jest zależna od rozmiaru danych, a jednocześnie same kolejki są krótkie.