Stosy i kolejki

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ą.

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:

Stosy tablicowo

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;

Stosy jako listy jednokierunkowe

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.

Dodatkowe procedury stosowe

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.

Implementacja kolejek

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.

Kolejki tablicowo

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;

Kolejki jako listy jednokierunkowe

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;

Dodatkowe procedury kolejkowe

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.

Implementacja za pomocą listy cyklicznej

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.