6. Stosy i kolejki

Jak wspominaliśmy w poprzednim rozdziale, abstrakcyjne typy danych umożliwiają wstrzymanie szczegółowej implementacji typu danych, dopóki nie będzie jasne, jakie operacje trzeba będzie wykonywać na danych. Faktycznie operacje te określają, jaka implementacja będzie najefektywniejsza w konkretnej sytuacji. Zasadę tę ilustrują dwa typy danych: stosy i kolejki, opisane przez listę wykonywalnych na nich operacji. Dopiero po określeniu listy wymaganych operacji zaprezentujemy kilka możliwych implementacji i porównamy je.

6.1. Stosy

Stos (ang. stack) jest liniową strukturą danych, dostępną do zapisywania i odczytywania tylko z jednego końca. Przypomina stos talerzy w restauracji: nowe talerze są dokładane na wierzch stosu i zdejmowane z wierzchu. Ostatni talerz położony na stosie będzie pierwszym z niego zdjętym. Z tego powodu stos jest nazywany strukturą LIFO (od ang. last in, first out).
Talerz może być zdjęty ze stosu tylko wtedy, kiedy na stosie są jakieś talerze, a nowy talerz można dołożyć na stos tylko wtedy, kiedy jest tam dosyć miejsca, to znaczy stos nie jest za wysoki. Stos można zatem zdefiniować za pomocą operacji, które zmieniają lub sprawdzają jego stan. Operacje te i ich parametry są następujące:

=> initialize(stack) - powoduje opróżnienie stosu stack;
=> empty(stack) - powoduje sprawdzenie, czy stos stack jest pusty;
=> full(stack) - powoduje sprawdzenie, czy stos stack jest zapełniony;
=> push(el, stack) - powoduje umieszczenie elementu el na stosie stack;
=> pop(stack) - powoduje zdjęcie najwyższego elementu ze stosu stack.

Ciąg operacji push() i pop() jest pokazany na rysunku 6.1. Przykład ten sugeruje, że do implementacji stosu można by użyć tablicy. Co jednak miałoby oznaczać, że tablica jest pusta? W tablicy zawsze są zapisane jakieś wartości, czy to umieszczone
#104
tam przez użytkownika, czy przez system operacyjny. Tablica nigdy nie jest naprawdę pusta. Z tego względu do oznaczania nie używanych komórek można wykorzystać specjalną wartość, na przykład zero. Czy będziemy jednak w stanie odróżnić zera oznaczające puste komórki od zer umieszczonych na stosie? Tablica mogłaby składać się ze struktur o dwóch polach: jednym na dane i drugim na znacznik. Taka implementacja byłaby jednak niepotrzebnie skomplikowana i wymagałaby poszukiwania najwyższego elementu. Prostsze rozwiązanie wykorzystuje zewnętrzną zmienną wskazującą pierwszą wolną pozycję (zob. rys. 6.2a). Zmienna ta przyjmuje początkowo wartość zero i jest zwiększana, kiedy nowy element jest dokładany na stos, a zmniejszana przy zdejmowaniu elementu ze stosu. Załóżmy, że zostały poczynione poniższe deklaracje:

#define Max 50
typedef int ElType;
typedef ElType StackType[Max];
int top;

Rys. 6.2. Pięć implementacji stosu przechowującego liczby 0, -11 i 15
#105
Rysunek 6.3 zawiera najprostszy kod funkcji operujÄ…cych na stosie.

initialize (StackType stack)
{
top = 0 ;
}
empty (StackType stack)
{
return top ==0 ;
}
full(StackType stack)
{
return top == Max;
}
push(ElType el, StackType stack)
{
if (full (stack) )
printf ("przepełnienie stosu");
else stack[top++] = el;
}
ElType pop (StackType stack)
{
if (empty (stack) )
printf ("niedobór na stosie");
else return stack[--top];
}

Rys. 6.3. Funkcje operujÄ…ce na stosie - pierwsza implementacja

Zaznaczmy jedną poważną wadę tego rozwiązania. Funkcja initialize () otrzymuje parametr stack, ale parametr ten nie jest odczytywany ani modyfikowany, gdyż funkcja jedynie przypisuje wartość zero zmiennej globalnej top. Oznacza to, że w całym programie można użyć tylko jednego stosu, ponieważ dla każdego stosu funkcja initialize () wyzerowałaby tę samą zmienną top. W innych funkcjach pojawia się ten sam problem. Chcielibyśmy móc używać tych funkcji dla dowolnej liczby stosów, a nie pisać nowy zestaw funkcji dla każdego stosu. Jakimś rozwiązaniem tego problemu jest dołączenie top do listy parametrów każdej funkcji. To jednak naruszałoby nieco pierwotne sformułowania funkcji operujących na stosie, które nie zawierają takiego parametru w sposób jawny. Na przykład funkcja push () powinna mieć dwa parametry, a nie trzy. Ujawniałoby to programowi użytkownika szczegóły implementacji, które powinny pozostać ukryte.
#106
Innym sposobem implementacji jest zaszycie wskaźnika wierzchołka wewnątrz stosu. Można to zrobić, wykorzystując pierwszą komórkę tablicy na taki wskaźnik. W tym celu w istniejącym kodzie top trzeba zastąpić przez stack[0], a 0 przez 1 (zob. rys. 6.2b). Nowa implementacja dwóch funkcji jest pokazana na rysunku 6.4.

initialize(StackType stack)
{
stack[0] = 1;
}
push(ElType el, StackType stack)
{
if (full(stack))
printf("przepełnienie stosu");
else stack[stack[0]+1] = el;
}

Rys. 6.4. Funkcje operujÄ…ce na stosie - druga implementacja

Z implementacją tą wiążą się jednak inne problemy. W szczególności silnie ogranicza ona możliwości wyboru typu ElType, który powinien być teraz typem int lub char, ponieważ zawartość stack[0] jest zwiększana lub zmniejszana przy każdym wywołaniu push () lub pop (). Jeśli będzie to char, to stos będzie mógł pomieścić tylko 255 elementów. Nie można na stosie przechowywać struktur, a nawet liczby rzeczywiste mogą sprawiać kłopoty, jeśli nie użyjemy konwersji (jak stack[ (int) stack[0]-H-]). Tego ograniczenia nie było w pierwszej implementacji, ponieważ typ zmiennej top nie miał związku z typem elementu stosu stack. Druga implementacja z kolei łączy top i stack w jeden obiekt. Optymalnym rozwiązaniem jest połączenie najlepszych cech obydwu implementacji, eliminujące ich ograniczenia.
W kolejnej implementacji stos jest zdefiniowany jako struktura o dwóch polach. Jedno jest przeznaczone na umieszczenie właściwych danych, a drugie na zapamiętanie wierzchołka stosu (rys. 6.2c). Nowe funkcje są zdefiniowane na rysunku 6.5.
Chociaż ostatnia implementacja jest najlepsza, również nie jest pozbawiona słabych punktów. We wszystkich trzech implementacjach była wykorzystywana tablica, co ograniczało dopuszczalną liczbę elementów na stosie. Jeśli przyjmie się zbyt małą wartość Max, to łatwo o przepełnienie stosu, jeśli zbyt dużą, to niepotrzebnie zablokuje się pewną ilość pamięci. Z rozważań przedstawionych w poprzednim rozdziale wynika czwarta metoda: użycie listy do implementacji stosu jak na rysunku 6.2d. Rysunek 6.6 dotyczy operacji stosowanych z wykorzystaniem listy.
W tej implementacji należy pamiętać, że czasami zmienna stosowa jest przekazywana funkcjom jako parametr, a czasami jako wskaźnik do niej. Może to powodować błędy w programie, jeśli przez pomyłkę napiszemy pop (stack) zamiast
#107
pop(&stack). Kompilator może nie wygenerować ostrzeżenia, a program będzie działał błędnie. Bardziej konsekwentnie byłoby używać tylko jednego trybu przekazywania tego parametru. Jeśli zmienne stosowe zadeklarujemy jako wskaźniki do wskaźników, to nie będzie potrzeby przekazywania ich adresów, ponieważ i tak można w nich dokonać trwałych zmian (zob. rys. 6.2e). Rozwiązanie to jest jedynie rozszerzeniem ostatniej implementacji. Jeśli stosy zadeklarowalibyśmy jako wskaźniki, to w celu osiągnięcia trwałej ich zmiany trzeba by przekazywać jako parametry ich adresy (wskaźniki do wskaźników). Szczegóły implementacji pozostawiamy jako ćwiczenie.

struct StackRec {
ElType storage[Max] ;
int top;
}
typedef struct StackRec StackType;

initialize (StackType *stack)
{
(*stack) .top = 0;
}
empty (StackType stack)
{
return stack.top == 0;
}
full (StackType stack)
{
return stack.top == Max;
}
push (ElType el, StackType *stack)
{
if (full(*stack) )
printf ( "przepełnienie stosu" ) ;
else (*stack).storage[(*stack).top++] = el;
}
ElType pop ( StackType *stack)
{
if (empty ( *stack) )
printf ( "niedobór na stosie");
else return (*stack).storage[--(*stack).top];
}

Rys. 6.5. Funkcje operujÄ…ce na stosie - trzecia implementacja
#108

struct StackRec {
ElType storage;
struct StackRec *next;
};
typedef struct StackRec *StackType;

initialize(StackType *stack)
{
* stack = NULL;
}
empty(StackType stack)
{
return stack == NULL;
}
push(ElType el, StackType *stack)
{
StackType tmp = (StackType) malloc(sizeof(struct StackRec));

if (tmp == NULL)
printf("przepełnienie stosu - brak pamięci");
else {
tmp->storage = el;
tmp->next= *stack;
*stack = tmp;
}
}

ElType pop (StackType *stack)
{
if (* stack == NULL)
printf("niedobór na stosie");
else {
StackType tmp = * stack;
ElType el = (*stack)->storage;
*stack = ( *stack)->next;
free (tmp);
return el;
}
}

Rys. 6.6. Funkcje operujÄ…ce na stosie - czwarta implementacja

Innym sposobem na to, by móc przekazywać parametr stack, a nie & stack, jest zadeklarowanie zmiennej stack jako tablicy 1-elementowej, ponieważ wszystkie tablice są przekazywane przez wskaźnik, a nie przez wartość. Szczegóły implementacji również pozostawiamy jako ćwiczenie.
#109
main()
{
StackType OperandStack1, OperandStack2 , ResultStack;
int ResultNum = 0;
char ch;

printf ( "Podaj dwie liczby do dodania: " ) ;
while (isspace(ch = (char) getchar() )); /* pomiń wiodące białe znaki */
initialize (OperandStack1);
initialize (OperandStack2);
initialize (ResultStack);
while (isdigit(ch)) { /*umieść pierwszą liczbę na jej stosie */
push (ch- '0', OperandStack1);
ch = (char) getchar();
}
while (isspace(ch = (char) getchar())); /* pomiń białe znaki między liczbami */
while (isdigit(ch)) { /* umieść drugą liczbę na jej stosie */
push (ch-'0', OperandStack2);
ch = (char) getchar();
}
while (!empty(OperandStack1) || /* powtarzaj, dopóki oba stosy */
!empty(OperandStack2)) { /* nie będą puste */
if (!empty(OperandStack1))
ResultNum += pop(OperandStack1);
if (!empty(OperandStack2))
ResultNum += pop(OperandStack2);
if (ResultNum > 9) {
push(ResultNum-10, ResultStack);
ResultNum = 1; /* zapamiętaj przeniesienie na zmiennej ResultNum */
}
else {
push(ResultNum, ResultStack);
ResultNum = 0;
}
}
if (ResultNum > 0) /* włóż na stos ostatnie przeniesienie - jeśli jest */
push(ResultNum, ResultStack);
while (!empty(ResultStack))
printf("%d", pop(ResultStack));
}

Rys. 6.7. Program dodawania dużych liczb za pomocą dwóch stosów
#110
Jako przykład rozważmy dodawanie wielkich liczb. Zakres liczb całkowitych jest ograniczony, więc nie możemy dodać 18 274 364 583 929 273 748 459 595 684 373 i 8 129 498 165 026 350 236, ponieważ zmienne całkowite nie mogą pomieścić tak wielkich wartości, nie mówiąc już o ich sumie. Problem można rozwiązać, jeśli potraktujemy liczby jako ciągi cyfr, umieścimy liczby odpowiadające tym cyfrom na dwóch stosach i wykonamy dodawanie przez zdejmowanie liczb z tych stosów. Schemat tego algorytmu jest następujący:
wczytaj cyfry pierwszej liczby i umieść odpowiadające im liczby na pierwszym stosie ; wczytaj cyfry drugiej liczby i umieść odpowiadające im liczby na kolejnym stosie; result = 0; dopóki przynajmniej jeden stos jest niepusty
zdejmij po jednej liczbie z każdego niepustego stosu i dodaj je do zmiennej result;
umieść liczbę jedności na stosie wynikowym ;
umieść przeniesienie na zmiennej result;
jeśli przeniesienie jest niezerowe, umieść je na stosie wynikowym;
zdejmuj liczby ze stosu wynikowego i wypisuj je ;
Rysunek 6.7 zawiera implementacjÄ™ tego algorytmu.


6.2. Kolejki

Kolejka (ang. queue) to po prostu lista oczekujących, zwiększająca się przez dodawanie elementów na jej końcu, a malejąca przez wyjmowanie elementów z początku. W odróżnieniu od stosu kolejka jest strukturą, w której są wykorzystywane oba końce: jeden do wstawiania nowych elementów, a drugi do ich usuwania. Ostatni element musi zatem poczekać, aż wszystkie elementy poprzedzające go w kolejce zostaną usunięte. Kolejkę nazywa się inaczej strukturą FIFO (od ang. first in,first out).
Operacje na kolejce są podobne do operacji stosowych. Oto operacje niezbędne do zarządzania kolejką:
=> initialize(queue) - powoduje opróżnienie kolejki queue;
=> empty(queue) - powoduje sprawdzenie, czy kolejka queue jest pusta;
=> full(queue) - powoduje sprawdzenie, czy kolejka queue jest zapełniona;
=> enq(el, queue) - powoduje umieszczenie elementu el na końcu kolejki queue;
=> deq(queue) - powoduje usunięcie pierwszego elementu z kolejki queue.

Ciąg operacji enq() i deq() jest pokazany na rysunku 6.8. Tym razem - inaczej niż dla stosów - zmiany trzeba śledzić zarówno na początku, jak i na końcu kolejki.
Jedną z możliwych implementacji kolejki jest tablica, chociaż niekoniecznie jest to najlepszy wybór. Elementy dostawia się na koniec kolejki, ale usuwa się z jej początku, zwalniając w ten sposób komórki tablicy. Komórki te nie powinny się marnować. Używa się ich zatem do wstawiania nowych elementów, co powoduje, że
#111
koniec kolejki może się znaleźć na początku tablicy. Sytuację tę lepiej ilustruje tablica cykliczna, jak na rysunku 6.9c. Kolejka jest pełna, jeśli pierwszy element bezpośrednio poprzedza element ostatni w kierunku przeciwnym do ruchu wskazówek zegara. Ponieważ jednak tablica cykliczna jest implementowana za pomocą "zwykłej" tablicy, oznacza to, że kolejka jest pełna, jeśli albo pierwszy element jest w pierwszej komórce, a ostatni w ostatniej komórce tablicy (rys. 6.9a), albo pierwszy element jest zaraz za ostatnim (rys. 6.9b). Podobnie funkcje enq() i deq() muszą uwzględniać

Rys. 6.8. CiÄ…g operacji wykonywanych na kolejce
Rys. 6.9. (a-b) Dwie możliwe konfiguracje w tablicowej implementacji kolejki, kiedy kolejka jest pełna; (c) ta sama kolejka traktowana jako tablica cykliczna; (d) wstawienie liczby 6 do kolejki zawierającej liczby 2, 4 i 8; (e-f) ta sama kolejka traktowana jako tablica jednowymiarowa z ostatnim elementem na końcu (e) i w środku (f)
#112
możliwość zawinięcia naokoło tablicy przy wstawianiu lub usuwaniu elementów. Na enq() na przykład można patrzeć jak na funkcję działającą na tablicy cyklicznej (rys. 6.9c), jednak naprawdę operuje ona na tablicy jednowymiarowej. Z tego powodu jeśli ostatni element znajduje się w ostatniej komórce, a są wolne miejsca na początku tablicy, to tam właśnie jest umieszczany nowy element (rys. 6.9e). Jeśli ostatni element jest na dowolnej innej pozycji, to nowy element jest umieszczany za nim, jeżeli jest na to miejsce (rys. 6.9f). Te dwie sytuacje trzeba rozróżniać, implementując kolejkę jako tablicę cykliczną (rys. 6.9d).
Na rysunku 6.10 jest przedstawiona jedna z możliwych implementacji funkcji działających na kolejkach.
Bardziej naturalną implementacją kolejki jest lista. Można zastosować funkcje działające na listach: funkcję wstawiającą element na koniec listy i funkcję usuwającą element z jej początku. Implementację pozostałych funkcji na listach pozostawiamy jako ćwiczenie.
Kolejki są tak często wykorzystywane w różnych symulacjach, że powstała rozbudowana i matematycznie wyrafinowana teoria kolejek, w której analizuje się rozmaite scenariusze i buduje modele używające kolejek. W procesach kolejkowych mamy pewną liczbę klientów, zgłaszających się do usługodawców świadczących usługi. Możliwości wykonawcze usługodawcy mogą być ograniczone, dlatego klienci muszą czekać w kolejkach, zanim nie zostaną obsłużeni, a sama obsługa również zajmuje nieco czasu. Mówiąc o klientach, mamy na myśli niekoniecznie ludzi, ale i inne obiekty. Na przykład części na taśmie produkcyjnej w procesie montażu, ciężarówki czekające na obsługę na stacji przeładunkowej czy barki czekające na otwarcie śluzy, aby mogły przepłynąć przez kanał, także tworzą kolejki. Najbardziej znane przykłady to kolejki w sklepach, na pocztach i w bankach. Rodzaje problemów stawianych w symulacjach to: Ilu usługodawców potrzeba, aby uniknąć długich kolejek? Jak duża musi być przestrzeń dla oczekujących, żeby pomieścić całą kolejkę? Czy taniej będzie powiększyć tę przestrzeń, czy dodać kolejnego usługodawcę?
Rozważmy przykład Banku Głównego, który przez trzy miesiące notował liczbę odwiedzających go klientów i czas potrzebny do ich obsługi. Zestawienie pokazane na rysunku 6.11a dotyczy liczby klientów przybywających w okresach jednominutowych w ciągu dnia. W 15% takich okresów nie przybył żaden klient, w 20% tylko jeden itd. Obecnie jest zatrudnionych sześciu urzędników i nie tworzą się żadne kolejki, a zarząd banku chciałby wiedzieć, czy sześć osób to nie za dużo. Może wystarczyłoby pięć? Cztery? Może nawet trzy? Czy można się spodziewać kolejek o każdej porze? Aby odpowiedzieć na te pytania, napisano program symulacyjny, wykorzystujący nagromadzone dane i sprawdzający różne scenariusze.
Liczba klientów zależy od losowo wygenerowanej wartości zawartej między 1 a 100. Na rysunku 6.11a widać, że wyróżniono pięć zakresów liczb od 1 do 100, odpowiadających liczbie klientów (0-4) przychodzących do banku w przedziałach jednominutowych. Jeśli wylosowaną liczbą jest 21, to liczba klientów wynosi 1; jeśli 90, to liczba klientów wynosi 4. W ten sposób symuluje się szybkość przybywania klientów do Banku Głównego.

struct QStorage {
int first, last;
int storage[Max];
};
typedef struct QStorage QType[1];

QType Q;

initialize(QType Q)
{
Q[0].first = Q[0].last = -1;
}
full(QType Q)
{
return Q[0].first == 0 && Q[0].last == Max-1 ||
Q[0].first == Q[0].last+1;
}
empty(QType Q)
{
return Q[0].first == -1;
}
enq(int el, QType Q)
{
if (!full(Q))
if (Q[0].last == Max-1 || Q[0].last == -1) {
Q[0].storage[0] = el;
Q[0].last = 0;
if (Q[0].first == -1)
Q[0].first = 0;
}
else Q[0].storage[++Q[0].last] = el;
else printf("Kolejka jest przepełniona. \n");
}

deq (QType Q)
{ int tmp;
if (!empty(Q)) {
tmp = Q[0].storage[Q[0].first];
if (Q[0].first == Q[0].last)
Q[0].last = Q[0].first = -1;
else if (Q[0].first == Max-1)
Q[0].first = 0;
else Q[0].first++;
return tmp;
}
else printf("Kolejka jest pusta. \n");
}

Rys. 6.10. Funkcje operujÄ…ce na kolejce - pierwsza implementacja
#114
Oprócz tego analiza zgromadzonych danych wykazała, że w ciągu 10 lub 20 sekund nie można obsłużyć żadnego klienta; 10% spraw załatwia się w 30 sekund itd., jak widać z rysunku 6.11b. Tabela na rysunku 11b zawiera też zakresy liczb losowych do generowania czasu obsługi klienta w sekundach.
(a)
Liczba klientów na minutę; Procent przedziałów jednominutowych; Zakres
0; 15; 1-15
1; 20; 16-35
2; 25; 36-60
3; 10; 61-70
4; 30; 71-100

(b)
Czas obsługi w sekundach; Procent klientów; Zakres
0; 0; -
10; 0; -
20; 0; -
30; 10; 1-10
40; 5; 11-15
50; 10; 16-25
60; 10; 26-35
70; 0; -
80; 15; 36-50
90; 25; 51-75
100; 10; 76-85
110; 15; 86-100

Rys. 6.11. Przykład Banku Głównego: liczba klientów przybywających w przedziałach jednominutowych i czas obsługi klienta podany w sekundach

Rysunek 6.12 zawiera kod symulujący przybywanie klientów i ich obsługę w Banku Głównym. Program korzysta z trzech tablic. W tablicy arrivals[] przechowuje się udziały okresów jednominutowych w zależności od liczby przybywających klientów. W tablicy service[] jest zapamiętany rozkład czasu obsługi. Czas otrzymuje się, mnożąc indeks danej komórki tablicy przez 10. Na przykład service[3] wynosi 10, co oznacza, że w 10% przypadków obsługa klienta wymaga 3 * 10 sekund. W tablicy clerks[] umieszcza się czas obsługi podany w sekundach.
Wykonanie programu wykazuje, że pięciu urzędników to za dużo. Przy czterech obsługa odbywa się bezproblemowo; w ciągu 25% czasu pracy banku utrzymuje się krótka kolejka oczekujących. Jeśli jest jednak tylko trzech urzędników, to cały czas utrzymuje się długa kolejka. Zarząd banku na pewno zdecyduje się na zatrudnienie czterech urzędników.
#115

option(int percents[])
{ register int i=0, choice = random(100)+1, perc;
for (perc = percents[0]; perc < choice; perc += percents[i+1], i++);
return i ;
}

mam ()
{ int arrivals[] = {15, 20, 25, 10, 30};
int service[] = {0,0,0, 0,0, 10, 5, 10, 10, 0, 15, 25, 10, 15};
int clerks[] = {0, 0, 0,0, 0, 0};,
clerkssize = sizeof(clerks)/sizeof(int);
int customers, t, i ;

for (t = 1; t<=100; t++) /* wykonuj symulacjÄ™ 100 minut */
{ printf ( "t = %d " , t) ;
for (i = 0; i < clerkssize; i++f) /* po upływie każdej minuty */
if (clerks[i] < 60) /* odejmij co najwyżej 60 sekund */
clerks[i] = 0; /* od czasu pozostałego do obsługi */
else clerks[i] -= 60; /* bieżącego klienta przez i-tego urzędnika */

customers = option(arrivals)
for (i = 0; i < customers; i++) /* wstaw do kolejki nowych klientów */ ;
enq(option(service)*10); /* (a raczej czasy ich obsługi) */
for (i = 0; i < clerkssize && !empty() ; ) /* usuwaj klientów */
if (clerks[i] < 60) /* z kolejki, jeśli są wolni urzędnicy */
clerks[i] += deq() ; /* przypisz więcej niż jednego */
else i++; /* klienta do urzędnika, jeśli łączny czas obsługi jest */
/* wciąż poniżej 60 sekund */
ScanQ() /* wypisz zawartość kolejki */
}
}

Rys. 6.12. Przykład Banku Głównego: kod programu


6.3. Kolejki priorytetowe

W wielu sytuacjach zwykłe kolejki nie zdają egzaminu, ponieważ zasada obsługiwania według kolejności przybycia ustępuje pewnym kryteriom priorytetu. Na poczcie na przykład osoba niepełnosprawna ma priorytet w stosunku do pozostałych. Zatem, gdy jakiś urzędnik będzie wolny, obsłużona zostanie osoba niepełnosprawna, a nie ktoś z początku kolejki. Na płatnych drogach niektóre pojazdy mogą być przepuszczane natychmiast, nawet bez opłaty (samochody policyjne, karetki, wozy straży pożarnej itd.). W łańcuchu procesów dla poprawnego funkcjonowania systemu może być potrzebne wykonanie procesu P_2 przed P_1, chociaż P_1 został umieszczony w kolejce oczekujących procesów przed P_2. W sytuacjach takich jak te potrzebna jest
#116
zmodyfikowana wersja kolejki - kolejka priorytetowa (ang. priority queue). W kolejkach priorytetowych elementy są usuwane według ich priorytetu oraz bieżącej pozycji w kolejce.
Problemem w przypadku kolejki priorytetowej jest znalezienie efektywnej implementacji, umożliwiającej względnie szybkie wstawianie i usuwanie. Ponieważ elementy mogą przybywać w dowolnym porządku, nie ma gwarancji, że elementy z początku kolejki będą usuwane w pierwszej kolejności, a elementy z końca będą ostatnimi kandydatami do usunięcia. Sytuację komplikuje to, że w rozmaitych przypadkach może być stosowana szeroka gama możliwych kryteriów priorytetu, jak częstość użycia, data urodzin, zarobki, stanowisko, stan cywilny itd. Może to być także czas zaplanowanego wykonania w kolejce procesów, co tłumaczy przyjętą w omawianiu kolejek priorytetowych konwencję, zgodnie z którą wyższy priorytet jest oznaczony mniejszą liczbą.
Kolejki priorytetowe mogą być reprezentowane przez dwa typy list. Dla pierwszego typu list elementy są umieszczone w kolejności ich wstawiania, a dla drugiego typu list porządek zachowuje się, umieszczając nowy element na pozycji odpowiadającej jego priorytetowi. W obu przypadkach łączny czas operacji to O(n), ponieważ na liście nieuporządkowanej dodanie elementu jest natychmiastowe, ale wyszukanie elementu do usunięcia wymaga czasu O(n), natomiast na liście uporządkowanej usunięcie elementu odbywa się w czasie stałym, ale dodanie nowego może trwać O(n).
Kolejna reprezentacja wykorzystuje krótką listę uporządkowaną i drugą nieuporządkowaną oraz wyznacza pewną graniczną wartość priorytetu [2]. Liczba elementów na liście uporządkowanej zależy od tej granicznej wartości. Oznacza to, że niekiedy lista ta może być pusta, a wartość graniczna może się zmieniać w trakcie działania programu, aby wymusić umieszczenie niektórych elementów na tej liście. Innym sposobem jest utrzymywanie stale tej samej liczby elementów na liście uporządkowanej; liczba sqr n jest tu dobrym kandydatem. Wstawianie zajmuje średnio czas O(sqr n), a usuwanie jest natychmiastowe.
Inną implementację zaproponował J. O. Hendriksen [3], [4]. Używa się w niej zwykłej listy wraz z dodatkową tablicą wskaźników do tej listy, pomagającą znaleźć fragment listy, w który powinien zostać wstawiony nowy element.
Eksperymenty Douglasa W. Jonesa [5] wskazują, że implementacja listowa, pomimo jej złożoności O(n), jest najlepsza dla kolejek 10-elementowych i mniejszych. Efektywność wersji z dwiema listami bardzo zależy od rozkładu priorytetów i może być albo doskonała, albo równie słaba co prosta implementacja listowa dla dużej liczby elementów. Implementacja Hendriksena ze swoją złożonością O(sqr n) działa jednakowo dobrze dla kolejek dowolnego rozmiaru.


6.4. Przykład: płatek śniegu von Kocha

Stos jest przydatną strukturą danych, jeśli pewne decyzje muszą być odłożone i podjęte później w określonym porządku. Aby to zilustrować, zaprezentujemy konstrukcję płatka śniegu von Kocha.
#117
Rys. 6.13. Przykłady płatków śniegu von Kocha

Na rysunku 6.13 widać przykłady płatków śniegu von Kocha. Płatek śniegu będzie traktowany jako połączenie trzech identycznych łamanych narysowanych pod różnymi kątami. Sposób rysowania jednej takiej łamanej jest następujący:

1. Dzielimy odcinek długości side na trzy równe części.
2. Przesuwamy się na odległość jednej trzeciej side w kierunku określonym przez kąt angle.
3. SkrÄ™camy w lewo o 60° (tzn. skrÄ™camy o -60°) i przesuwamy siÄ™ naprzód o jednÄ… trzeciÄ… side.
4. SkrÄ™camy w prawo o 120° i przesuwamy siÄ™ naprzód o jednÄ… trzeciÄ… side.
5. SkrÄ™camy w lewo o 60° i przesuwamy siÄ™ naprzód o jednÄ… trzeciÄ… side.

Rysunek 6.14 ilustruje tych pięć kroków.

Rys. 6.14. Proces rysowania czterech odcinków jednego segmentu płatka śniegu von Kocha

Linia będzie bardziej postrzępiona, jeśli każdy z czterech odcinków zastąpimy miniaturą całej łamanej, to znaczy, jeśli proces rysowania czterech linii zastosujemy do każdego z odcinków długości size/3. W wyniku tego zostanie narysowanych 16 odcinków długości size/9. Proces ten można kontynuować w nieskończoność - przynajmniej teoretycznie. W praktyce musi nas powstrzymać rozdzielczość grafiki komputerowej, bo jeśli długość linii będzie mniejsza niż średnica punktu, to na ekranie i tak zobaczymy tylko jedną kropkę.
#118
Na każdym poziomie procesu dzielenia musimy zachowywać informację o dokonanych już podziałach, aby przy rysowaniu linii wiedzieć, o jaki kąt skręcić i w którą stronę rysować następny odcinek. Jedyną informacją, którą trzeba przechowywać, są kąty, o jakie należy skręcać, ponieważ długość rysowanego odcinka jest zawsze taka sama, równa side/3^level, gdzie level określa, ile razy odcinki są dzielone na pododcinki, pododcinki na podpododcinki itd.
Szczegółowa procedura jest zaprezentowana na rysunku 6.15. Na poczÄ…tku kÄ…ty -60stopni, 120stopni i -60stopni - dla odcinków rozmiaru side/3 - umieszcza siÄ™ na stosie stack (rys. 6.15a). NastÄ™pnie te same trzy kÄ…ty wkÅ‚ada siÄ™ na stos tmp_stack, wplatajÄ…c je miÄ™dzy wartoÅ›ci zdjÄ™te ze stosu stack (rys. 6.15b, c). Na koniec zawartość tmp_stack zostaje przeniesiona na stack (co opróżnia tmp_stack do nastÄ™pnej iteracji), dziÄ™ki czemu zostaje odtworzona prawidÅ‚owa kolejność rysowania (rys. 6.15d). Czemu sÅ‚uży ta ostatnia czynność? Z porównania rysunków 6.15c i 6.15d widać, że stosy majÄ… tÄ™ samÄ… zawartość, zatem to przeniesienie wydaje siÄ™ zbÄ™dne. Jest to prawda dla tego i podobnych przypadków. PoczÄ…tkowa symetria jest wciąż powielana w trakcie wykonywania algorytmu. Za każdym razem na stos sÄ… wkÅ‚adane trzy kÄ…ty: -60stopni, 120stopni oraz -60stopni, i nie ma znaczenia, czy pierwsze -60° jest kÄ…tem, o który trzeba skrÄ™cić po narysowaniu linii AB na rysunku 6.15a, czy też kÄ…tem, który trzeba uwzglÄ™dnić przed narysowaniem linii DE. Gdyby jednak byÅ‚y to na przykÅ‚ad kÄ…ty -70stopni, 120stopni i -30stopni, kolejność ich zapamiÄ™tania byÅ‚aby kluczowa dla otrzymania poprawnego rysunku.

Rys. 6.15. Rysowanie czterech boków jednego segmentu płatka śniegu von Kocha z użyciem dwóch stosów

/* Program w Turbo C */
#include
#include
#include

#define max_stack 100

int grboard=DETECT, grmode, grresult;
double angle, stack[max_stack], tmp_stack[max_stack];

void initialize(double stack[])
{
stack[0] = 0.0;
}
int empty(double stack[])
{
return stack[0] == 0.0;
}
int full(double stack[])
{
return (int) stack[0] == max_stack-1;
}
double pop(double stack[])
{
return stack[(int) stack[0]--];
}
void push(double angle, double stack[])
{
if (!full(stack))
stack[(int) ++stack[0]] = angle;
else outtext("Przepełnienie stosu");
}
/* Argumenty funkcji sin() muszą być kątami podanymi w radianach, dlatego niezbędny jest współczynnik Pi/180. */

void forward(float distance)
{
linerel((int) (cos(angle*M_PI/180)*distance),
(int) (sin(angle*M_PI/180)*distance));
}

Rys. 6.16. Kod algorytmu rysowania płatka śniegu von Kocha
#120
void three_pushes(double stack[])
{
push (-60.0, stack);
push (120.0, stack);
push (-60.0, stack);
}
void side(float size, int level)
{
char i;
three_pushes (stack) ; /* patrz rysunek 6.15a */
initialize (tmp_stack);
for (i = 2; i <= level; i++) {
size /= 3;
while (!empty(stack)) { /* patrz rysunek 6.15b */
three_pushes(tmp_stack);
push(pop(stack), tmp_stack);
}
three_pushes (tmp-stack) ; /* patrz rysunek 6.15c */
while (!empty(tmp_stack)) /* patrz rysunek 6.15d */
push(pop(tmp_stack),stack);
}
forward (size);
while (!empty(stack)) {
angle 4-= pop(stack);
forward (size);
}
}

void snowflake(float size, int level)
{ int i;
for (i = 1; level > 0 && i <= 3; i++) {
initialize (stack);
side (size,level);
angle += 120;
}
}

Rys. 6.16. Kod algorytmu rysowania płatka śniegu von Kocha (cd.)
#121
main ()
{
detectgraph(&grboard,&grmode);
switch(grboard) {
case EGA: grmode = EGAHI; break;
case EGA64 : grmode = EGA64LO; break;
case VGA: grmode=YGAHI; break;
default: fprintf (stderr, "Program wymaga przynajmniej karty \
EGA \n");
return 1;
}
initgraph(&grboard,&grmode, "");
if ((grresult - graphresult()) <0) {
fprintf (stderr, "%s\n", grapherrormsg(grresult));
}
setcolor(WHITE);
setbkcolor(BLUE);
moveto(200,150);
angle = 0.0;
snowflake(300,2);
}

Rys. 6.16. Kod algorytmu rysowania płatka śniegu von Kocha (cd.)

Rysunek 6.16 zawiera kompletny kod omówionego algorytmu.

6.5. Ćwiczenia

1. Odwróć zawartość stosu S:
(a) używając dwóch pomocniczych stosów;
(b) używając jednej pomocniczej kolejki;
(c) używając jednego pomocniczego stosu i kilku zmiennych.
2. Ustaw elementy na stosie S w porządku rosnącym, używając jednego pomocniczego stosu i kilku zmiennych.
3. Przenieś elementy ze stosu S, na stos S2 tak, by elementy na S2 były w tej samej kolejności co na S,:
(a) używając jednego pomocniczego stosu;
(b) nie używając dodatkowego stosu, a jedynie kilku zmiennych.
#122
4. Zaproponuj implementację stosu przechowującego elementy dwóch różnych typów, na przykład struktur i liczb rzeczywistych.
5. Wykorzystując dodatkowe zmienne, uporządkuj elementy w kolejce, używając do tego:
(a) dwóch pomocniczych kolejek;
(b) jednej pomocniczej kolejki.
6. Napisz szkic programu sprawdzającego poprawność rozstawienia nawiasów okrągłych, kwadratowych i klamrowych w tekście programu w języku C.
7. Napisz funkcje implementujące wersję kolejki priorytetowej z dwiema listami. Mogą tu być co najmniej dwa warianty: jeden z użyciem dwóch oddzielnych list, uporządkowanej i nieuporządkowanej, i drugi z użyciem tylko jednej listy wraz z odpowiednimi wskaźnikami.

Rys. 6.17. Linie, które można narysować, modyfikując program z rysunku 6.16

8. Jakich zmian trzeba by dokonać w programie z przykładu z płatkiem śniegu von Kocha, aby narysować figury z rysunku 6.17? Wypróbuj te i inne możliwości w celu otrzymania różnych figur.

6.6. Zadania programistyczne

1. Napisz program sprawdzający, czy dany napis jest palindromem, to znaczy, czy jest taki sam czytany od początku i od końca. W danej chwili wolno Ci odczytać tylko jeden znak napisu wejściowego; nie używaj tablicy, aby najpierw zapamiętać cały napis, a później go analizować (oprócz, być może, implementacji stosu). Rozważ użycie wielu stosów.
2. Napisz program dokonujący konwersji liczby z zapisu dziesiętnego na dwójkowy, ósemkowy i szesnastkowy.
3. Napisz program wykonujący cztery podstawowe działania arytmetyczne (+, -, *,/) na bardzo dużych liczbach całkowitych (wynik dzielenia powinien być także liczbą
#123
całkowitą). Zastosuj te operacje do obliczenia 123^45 albo setnego wyrazu ciągu 1*2 + 3,2*3,2 + 4,3*43 + 5, .... Użyj ich też do obliczania liczb Godła wyrażeń arytmetycznych.
Numeracja Godła GN ustala najpierw odpowiedniość między symbolami języka a liczbami:

Symbol; Liczba G dla GN
=; 1
+; 2
*; 3
-; 4
/; 5
(; 6
); 7
^; 8
O; 9
S; 10
x^i; 11+2*i
X^i; 12+2*i

gdzie S jest funkcją następnika. Z kolei dla dowolnej formuły F=s#1 s#2... s#n:

GN('S#1 s#2...s#n') = 2^[CM(s#1)] * 3^[CM(s#2)] * ... * p(#n;^[CM(s#n)])

gdzie p#n jest n-tą liczbą pierwszą. Na przykład

GN(1) = GN(S0) = 2^10*3^9

natomiast

GN('x#1+x#3'x#4') = 2^(11+2)*3^2*5^(11+6)*7^1*11^(11+8)

W ten sposób każdemu wyrażeniu arytmetycznemu można jednoznacznie przyporządkować liczbę naturalną. Metody tej użył austriacki matematyk Kurt Godeł w dowodach twierdzeń o ogromnym znaczeniu dla podstaw matematyki.
4. Napisz program dodający bardzo duże liczby zmiennopozycyjne. Rozszerz go na inne operacje arytmetyczne.

Bibliografia

Kolejki
[1] Sloyer C., Copes W., Sacco W., Starek R.: Queues: Will this wait never end! Providence, RI, Janson 1987.
#124
Kolejki priorytetowe
[2] Blackstone J.H., Hogg G.L., Philips D.T.: A two-list synchronization procedure for discrete event simulation. Communications ofthe ACM, 1981, 24, s. 825-829.
[3] Hendriksen J.O.: AÅ„ improved events list algorithm. Proceedings ofthe 1977 Winter Simulation Conference, Piscataway, NJ, IEEE 1977, s. 547-557.
[4] Hendriksen J.O.: Event list management - A tutorial. Proceedings of the 1983 Winter Simulation Conference, Piscataway, NJ, IEEE 1983, s. 543-551.
[5] Jones D.W.: AÅ„ empirical comparison of priority-queue and event-set implementations. Communications ofthe ACM, 1986, 29, s. 300-311.