2. Kolejki

Kolejki, podobnie jak stosy, służą do reprezentowania skończonych ciągów i dopuszczają wykonywanie na nich prostych operacji wkładanie usuwania, badania, czy kolejka jest pusta. Organizacja kolejki przypomina organizację kolejki klientów przed okienkiem na poczcie: obsługiwana jest zwykle najpierw pierwsza osoba z kolejki, a nowoprzybyły klient ustawia się na jej końcu. Zasadę rządzącą kolejką przyjęło się określać z angielskiego FIFO: first in - first out.

Definicja 6.2

Standardową strukturą kolejek nazywamy strukturę

Q(E) = < E + Q, in out, first, empty, = >,

gdzie E jest zbiorem elementów, Q zbiorem skończonych ciągów nad E, a operacje struktury są określone dla dowolnych q = (e₁,e₂,...,e_n) , q'= (e'₁,e'₂,...,e'_m) następująco:

in(e, q) =^df (e₁,e₂,...,e_n,e),
out(q) =^df (e₂,...,e_n), gdy n>1 i nieokreślone w pp.
first(q) =^df e₁, gdy n>1 i nieokreślone w pp.
empty(q) =^df true wttw q jest ciągiem pustym, tzn. n=0,
s = s' wttw^df n = m oraz e_i = e'_i dla i=1,...,n.

Zasada wykonywania operacji w kolejce jest inna niż w stosach: operacje usuwania elementu z kolejki i wkładania nowego elementu do kolejki, odbywają się na różnych jej końcach. Kolejność elementów w kolejce jest związana z kolejnością ich wstawiania do kolejki.

Podobnie jak stosy, kolejki można w komputerze reprezentować na różne sposoby. Omówimy tu dwie z nich: Kolejkę w postaci tablicy i kolejkę w postaci listy.

Implementacja I

Jako pierwszą omówimy implementację kolejki z użyciem tablicy. Kolejka jest reprezentowana przez tablicę TAB, zawierającą elementy składowe kolejki i dwa wskaźniki head i tail, wskazujące pozycje początku i końca kolejki. Jest to więc obiekt o trzech atrybutach TAB, head, tail, jak na rysunku 6.3.



	head				tail
	¯				¯
TAB:	1	2	3	...	i	...	n
	e₁	e₂	e₃	...	e_i
	e₁	e₂	e₃	...	e_i


			Rysunek 6.3

Operację wkładania do kolejki realizujemy przez wpisanie nowego elementu na pozycję tail+1. Usunięcie elementu z kolejki, to po prostu przesunięcie wskaźnika head o jedną pozycję w prawo. Oczywisty kłopot powstaje wtedy, gdy do kolejki zawierającej n elementów chcemy dodać jeszcze jeden element. Możemy go rozwiązać tak jak w przypadku stosów: przepisać zawartość tablicy do tablicy większej. W kolejkach mamy jednak jeszcze jeden problem. Usuwanie elementów z początku tablicy powoduje powstanie "dziury", którą moglibyśmy wykorzystać, o ile tablicę będziemy wypełniać cyklicznie: jeśli pozycja n-ta jest zapełniona to następny element wkładamy na pozycję pierwszą, o ile jest ona wolna. Na rysunku 6.4 pokazano kolejne stany kolejki w wyniku wykonania ciągu operacji wkładania i usuwania.

head

tail

TAB:

stan początkowy kolejki q

head

tail

TAB:

stan po wykonaniu operacji: in(m,q); out(q); out(q); out(q);

tail

head

TAB:

stan po wykonaniu operacji: in(n,q); in(o,q); in(p,q);

Rysunek 6.4

Przyjmujemy, że kolejka jest pusta, jeśli head = 0. Operację first można zrealizować wykonując jedną instrukcję przypisania {if (q.head¹0) then return q.TAB[head] fi}. Oczywiście wynik nie będzie poprawny, gdy kolejka jest pusta, dlatego zwykle obsługujemy ten błąd. Operację wkładania elementu można zrealizować następująco:

in(x,q){ if (q.head = 0) then
               q.head :=1; q.tail :=1
           else
                if not ((q.tail mod n)+1 = q.head ) then
                   q.tail := (q.tail mod n) + 1
              fi ;
            fi;
         q.TAB[q.tail] := x;
         return q
}.

Jeżeli kolejka q jest pusta, to w wyniku wykonania operacji in(x,q) zarówno atrybut head, jak i tail, wskazują pierwszy element tablicy TAB. W przeciwnym przypadku musimy zbadać, czy jest wolne miejsce w tablicy. Jeśli tak, to zwiększamy wartość wskaźnika tail o jeden i umieszczamy tam x. Tak zrealizowana operacja wkładania będzie funkcjonować poprawnie przy założeniu, że liczba elementów w kolejce nigdy nie przekroczy n.

Realizacja usuwania jest też prosta.

out(q){ if (q.head > 0) then
              if q.head = q.tail then
                    q.tail :=0; q.head := 0
             else
                   q.head := (q.head mod n) +1;
             fi fi;
          return q
}.

Zauważmy jeszcze, że koszt operacji in, out, first jest stały, przy założeniu, że tablica reprezentująca kolejkę ma dostatecznie duży rozmiar, tak by nigdy nie było w kolejce więcej niż n elementów.

Implementacja II

W tej implementacji będziemy myśleli o kolejce jako o obiekcie typu queue, mającym dwa atrybuty head i tail, wskazujące odpowiednio pierwszy i ostatni element kolejki. head i tail będą same obiektami typu LINK, o dwóch atrybutach val i next. Wartością atrybutu val jest przechowywany w kolejce element, a next jest referencją do obiektu typu LINK. Na rysunku 6.5 przedstawiono przykładową kolejkę, złożoną z n obiektów typu LINK. Elementami tej kolejki są e₁,...,e_n. Atrybut head wskazuje pierwszy element kolejki, a atrybut tail - ostatni. Przy takiej realizacji kolejki, nie ma problemów z przepełnieniem: nowy element dowiązujemy do końca kolejki, a usuwamy element wskazany przez head.

e₁

e₂

...

e_n-1

e_n

null

head

tail

Rysunek 6.5

Kolejka jest pusta, jeśli wartością head jest null. Realizacja operacji jest niezwykle prosta:

first(q){if (q.head ¹ null) then return q.head.val fi }

in(x,q){pom := new LINK(); pom.val := x;
            if (q.head ¹ null) then
                 q.tail.next := pom
            else
                 q.head := pom
           fi;
         q.tail := pom;
         return q
}

out(q){if (q.head ¹ null) then q := q.head.next fi}

empty (q){ return (q.head = null) }.

Operacje first i out są operacjami częściowymi, tak jak to sygnalizowaliśmy w strukturze standardowej.

Zastanówmy się, jakie wspólne cechy mają te dwie implementacje struktury kolejek? Jakie własności charakteryzują kolejki?

Specyfikacja kolejek

Rozważmy następujący zestaw formuł (Q1)-(Q7), w których q jest zmienną typu kolejka, a x jest zmienną typu element kolejki.

(Q1) empty(q) ® out(in(x,q)) = q

(Q2) empty(q) ® first(in(x,q)) = x

(Q3) Ø empty(in(x,q))

(Q4) Ø empty(q) ® first(in(x,q)) = first(q)

(Q5) Ø empty(q) ® in(x,out(q)) = out(in(x,q))

(Q6) każda kolejka jest skończona

(Q7) kolejki q i q' są równe wttw dla każdego i, albo first(outⁱ(q)) = first(out ⁱ(q'))

Zauważmy najpierw, że niezależnie od tego, czy rozważamy strukturę standardową, czy jedną z opisanych implementacji kolejek, wszystkie te formuły są prawdziwe. Rzeczywiście, pierwsze dwie opisują sytuację, gdy kolejka jest pusta: włożenie i usunięcie jednego elementu pozostawia znów kolejkę pustą, a po włożeniu elementu, to on jest tym, który zwraca funkcja first. W przypadku, gdy kolejka jest niepusta, operacja in nie zmienia wartości first, a ponadto operacje in i out są przemienne.

Postulaty (Q6) i (Q7) mają nieco inny charakter i nie mogą być zapisane jako zwykłe formuły logiki klasycznej. Podobnie jak w przypadku stosów możemy je zapisać jako własności pewnych algorytmów. Niezapętlanie się programu

{while not empty(q) do q := out(q) od}

oznacza, że kolejka q jest skończona. A program

{bool := true;
while (not empty(q) and not empty(q') and bool) do
bool := (first(q) = first(q));
q := out(q); q':= out(q');
od
}

o ile kończy się spełnieniem warunku (bool and empty(q) and empty(q')) stwierdza równość dwóch kolejek q i q'.

Można udowodnić, że każda struktura danych, w której formuły (Q1)-(Q7) są prawdziwe jest izomorficzna z pewnym modelem standardowym kolejek. Wynika stąd, że postulaty (Q1)-(Q7) możemy przyjąć jako definicję abstrakcyjnej struktury kolejek. Nieważne jak naprawdę reprezentowana jest kolejka i jak zrealizowane są jej operacje. Wystarczy wiedzieć, że ma własności opisane w specyfikacji, by móc się nią poprawnie posłużyć.

Pytanie 3: Do początkowo pustej kolejki q, włożono kolejno elementy a, b, c, d, e. Ile operacji first, in, out trzeba wykonać, aby utworzyć kolejkę, w której kolejność elementów jest odwrotna niż w kolejce q?

« poprzedni punkt następny punkt »