Strona główna » Algorytmy » Artykuły » Kolejka
 

Kolejka

https://mattomatti.com/a0009

Wstęp

Kolejka jest to struktura danych, która umożliwia porządkowanie danych w celu wykonania obliczeń według kolejności zgłoszeń. W swoim działaniu jest bardzo podobna do kolejki osób w sklepie. Ilustruje to poniższy schemat:

Ilustracja kolejka

Każda kolejka ma swój początek i koniec. W rzeczywistości sprzedawca widzi pierwszego klienta. Co prawda końca nie widzi, ale może mieć recepcje, która wskaże kto aktualnie jest ostatni w kolejce. Ponadto każdy z klientów wie kto za nim stoi.

W komputerowej kolejce sprzedawca nazywany jest głową, a ostatni klient ogonem. Ze względu na to, że w kolejce może się znaleźć dowolny obiekt to jest on nazywany węzłem. W węźle przechowywane są dwie informacje: obiekt oczekujący czyli np. osoba oraz wskaźnik, który węzeł się za nim znajduje.

Kiedy używać?

Jak sama nazwa wskazuje kolejka powinna być wykorzystana wszędzie tam gdzie istnieje potrzeba ustawienia elementów w kolejce. Przykładowo serwer jeśli może na raz obsłużyć tylko jedno żądanie ustawi pozostałe żądania w kolejce i wywoła je kiedy będzie mógł je obsłużyć.

Zaletą kolejki jest teoretycznie możliwość stworzenia nieskończonej listy. Należy jednak pamiętać, że problematyczne jest wypisanie elementów wspak czy wstawienie elementów na wybraną pozycję. Jest to spowodowane faktem, że do k-tego elementu należy odwiedzić k elementów i prześledzić wszystkie ich wskaźniki.

Implementacja

Implementacja kolejki zostanie oparta o struktury i będzie zawierać funkcje, które pozwolą utworzyć listę, dodać do niej elementy oraz pobrać z niej elementy. Na liście przechowywane będą liczby całkowite. Oczywiście przechowywana wartość może być dowolnego typu.

Węzeł

Najważniejszą częścią kolejki jest implementacja węzła. Węzeł jak to wcześniej zostało wskazane zawiera pewną wartość i wskazuje co za nim się znajduje. W tej implementacji struktura wezel wygląda następująco:

  1. struct wezel {
  2.   int wartosc;
  3.   wezel* nastepny;
  4. };

Następnie należy napisać konstruktor, który ustawi nowemu węzłowi odpowiednie wartości:

  1. wezel* utworzWezel(int wartosc) {
  2.   wezel* w = new wezel;
  3.   w->wartosc = wartosc;
  4.   w->nastepny = NULL;
  5.   return w;
  6. }

Do dopełnienia brakuje jeszcze funkcji, która wypisz wartość przechowywaną w węźle.

  1. void wypiszWezel(wezel* w) {
  2.   cout << w->wartosc << endl;
  3. }

Kolejka

Teraz w oparciu o napisane funkcje można przejść do deklaracji listy. Jak zostało wspomniane we wstępie każda kolejka ma swoją głowę i swój ogon, dlatego kolejka musi zawierać dwa wskaźniki.

  1. struct kolejka {
  2.   wezel* glowa;
  3.   wezel* ogon;
  4. };

Na początku utworzona kolejka jest pusta, dlatego potrzebny jest konstruktor, który ustali domyślne wartości zmiennych. Zarówna głowa jak i ogon muszą wskazywać na NULL. W ten sposób będzie można łatwo stwierdzić czy w kolejce jest jakikolwiek element. Oto konstruktor:

  1. kolejka* utworzKolejke() {
  2.   kolejka* dane = new kolejka;
  3.   dane->glowa = NULL;
  4.   dane->ogon = NULL;
  5.   return dane;
  6. }

W zależności od tego czy kolejka jest pusta zależeć będzie zachowanie poszczególnych funkcji. Zgodnie z ustaleniami jeśli kolejka nie zawiera elementów to głowa wskazuje na NULL (tj. na NIC).

  1. bool czyPustakolejka(kolejka* kolejka) {
  2.   return (kolejka->glowa == NULL);
  3. }

W celu stwierdzenia czy funkcje będą dobrze działać bardzo przydatne będzie wypisywanie elementów. W tym celu należy napisać funkcję wypiszDane(), która dla podanej kolejki wypisze wszystkie jej elementy, albo czy kolejka jest pusta.

  1. void wypiszDane(kolejka* kolejka) {
  2.   if (czyPustakolejka(kolejka)) {
  3.     cout << "kolejka jest pusta!\n";
  4.     return;
  5.   }
  6.   wezel* w = kolejka->glowa;
  7.   while (w != NULL) {
  8.     wypiszWezel(w);
  9.     w = w->nastepny;
  10.   }
  11. }

(2.) Jeśli kolejka jest pusta to (3.) wypisz o tym informacje i (4.) zakończ działanie funkcji. (6.) W przeciwnym razie pobierz wskaźnik na pierwszy element i (7. - 10.) dopóki wskazany element istnieje kontynuuj (8.) wypisanie wartości i (9.) przechodzenie do następnego węzła.

Dodawanie elementów

Elementy do kolejki można dodawać na dwa sposoby: do głowy oraz do ogona. Choć z reguły ustawiając się w kolejce należy ustawić się na ostatnim miejscu (tj. ogonie) to może się okazać, że niektóre elementy powinny zostać wykonane szybciej. Obie implementacje są bardzo podobne.

W celu dodania elementu do głowy możliwe są dwa scenariusze. Pierwszy zakłada, że kolejka jest pusta. Wtedy zarówno głowa jak i ogon muszą wtedy wskazywać ten sam węzeł. Z kolei, gdy istnieje w kolejce chociaż jeden element to należy ustawić, że nowy węzeł staje się głową, a dodany węzeł wskazuje na starą głowe.

  1. void dodajDoGlowy(kolejka* kolejka, int wartosc) {
  2.   wezel* w = utworzWezel(wartosc);
  3.   if (kolejka->glowa == NULL) {
  4.     kolejka->glowa = w;
  5.     kolejka->ogon = w;
  6.   } else {
  7.     w->nastepny = kolejka->glowa;
  8.     kolejka->glowa = w;
  9.   }
  10. }

(2.) Utwórz węzeł. (3.) Jeśli kolejka jest pusta to: (4. - 5.) ustaw glowa i ogon kolejki na utworzony węzeł. (6.) W przeciwnym razie (7.) ustal, że nowy węzeł wskazuje na głowe i (8.) ustaw nowy element jako głowe.

Analogicznie należy postępować w przypadku dodawania elementu do ogona. Należy pamiętać, że do rozpatrzenia ponownie są dwa scenariusze.

  1. void dodajDoOgona(kolejka* kolejka, int wartosc) {
  2.   wezel* w = utworzWezel(wartosc);
  3.   if (kolejka->ogon == NULL) {
  4.     kolejka->glowa = w;
  5.     kolejka->ogon = w;
  6.   } else {
  7.     kolejka->ogon->nastepny = w;
  8.     kolejka->ogon = w;
  9.   }
  10. }

(2.) Utwórz nowy węzeł. (3.) Jeśli kolejka jest pusta to (4. - 5.) wykonaj to samo co przy dodawaniu go głowy: ustal, że głowa i ogon wskazują na nowy węzeł. (6.) Jednak w przypadku, gdy istnieje chociaż jeden element to (7.) wskaż, że ogon wskazuje na nowy węzeł, a następnie (8.) przestaw wskaźnik na ogon na nowy węzeł.

Pobieranie wartości

Pobierane wartości będą pobierane z początku kolejki. Możliwe są tutaj dwa przypadki. Jeśli lista będzie pusta to należy zgłosić odpowiedni wyjątek. W przeciwnym razie należy pobrać węzeł. Nadać elementowi, który wskazuje, że jest teraz głową kolejki i zwrócić wartość uprzednio usuwając węzeł. Jest to bardzo ważne, ponieważ programista nie musi znać kodu kolejki i nie należy do niego dbanie o usuwanie węzłów.

  1. int pobierzWartosc(kolejka* kolejka) {
  2.   if (czyPustakolejka(kolejka))
  3.     throw "kolejka jest pusta!\n";
  4.   wezel* w = kolejka->glowa;
  5.   if (kolejka->glowa->nastepny == NULL) {
  6.     kolejka->glowa = NULL;
  7.     kolejka->ogon = NULL;
  8.   } else {
  9.     kolejka->glowa = kolejka->glowa->nastepny;
  10.   }
  11.   int wartosc = w->wartosc;
  12.   delete w;
  13.   return wartosc;
  14. }

(2.) Jeśli kolejka jest pusta to (3.) zgłoś odpowiedni wyjątek. (4.) Pobierz węzeł. (5.) W przypadku, gdy był to jedyny element na liście to (6., 7.) ustal, że ogon i głowa mają wartości domyślne. Jednak (8.) gdy istnieje więcej elementów to (9.) ustal, że głową jest teraz drugi element. Po odpowiednim wyłączeniu elementu z kolejki pozostaje: (11.) odczytać jego wartość, (12.) usunąć węzeł i (13.) zwrócić odczytaną wartość.

Testowanie implementacji

Poniżej znajduje się funkcja, która testuje działanie napisanej implementacji kolejki.

  1. int main() {
  2.   kolejka* dane = utworzKolejke();
  3.   dodajDoGlowy(dane, 2);
  4.   dodajDoGlowy(dane, 1);
  5.   dodajDoOgona(dane, 3);
  6.   dodajDoOgona(dane, 4);
  7.   cout << "Dane na liscie:\n";
  8.   wypiszDane(dane);
  9.   cout << "\nPobierane dane:\n";
  10.   for (int i = 0; i < 5; i++) {
  11.     try {
  12.       cout << pobierzWartosc(dane) << endl;
  13.     }
  14.     catch (const char* msg) {
  15.       cout << msg;
  16.     }
  17.   }
  18.   system("pause");
  19.   return 0;
  20. }

Zadania

Zadanie 1

Napisz funkcję void dodajDoOgona2(kolejka* kolejka, int wartosc), która doda na końcu kolejki wartosc bez wykorzystywania zmiennej ogon.

Zadanie 2

Napisz funkcję void wypiszDaneWspak(kolejka* kolejka), która wypisze dane od końca do początku. Porównaj czasy wypisywania danych przy pomocy napisanej funkcji oraz wcześniej dostępnej wypiszDane(). Wyjaśnij na podstawie charakterystyki kolejki, dlaczego zachodzi taka zależność.