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

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.

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 = record 
     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.