Odstawiam na razie tematykę gier i wracam do serii artykułów o strukturach danych. Pewien czas temu przedstawiłem javascriptowa implementacje stosu, teraz przyszła pora na kolejna strukturę – kolejkę.
Kolejka jest używana w bardzo wielu sytuacjach jeśli chodzi o działanie komputera, od bardzo nisko poziomowej obsługi procesów, po zarządzanie takimi sprawami jak kolejność drukowania stron przez drukarkę.
W przeciwieństwie od stosu, kolejka to struktura FIFO (First In, First Out). Oznacza to, ze pierwszy opuszcza kolejkę, element który jest w niej najdłużej. Tak naprawdę, to najważniejsza różnica pomiędzy stosem a kolejką. Pod wieloma względami struktury te są do siebie bardzo podobne.
Bardzo łatwo przywołać ‚życiowy’ przykład kolejki. Wystarczy wyobrazić sobie chociażby kolejkę w sklepie czy na poczcie (z jakiegoś powodu niezbyt przyjemne konotacje 😛 ). Osoba, która stoi w kolejce najdłużej, na samym przedzie, będzie obsługiwana pierwsza. A ta która przyszła ostatnia, musi poczekać aż wszystkie osoby przed nią zostaną obsłużone, aż przyjdzie jej kolej.
Omawiana struktura danych działa bardzo podobnie. Element/proces, który przyszedł pierwszy, zostanie wywołany przed innymi.
Myślę, że jest to dość prosta do zrozumienia idea. Przejdę teraz do implementacji JavaScriptowej. Tak jak w przypadku stosu muszę określić, jakie funkcje będą potrzebne w mojej implementacji. Na pewno przyda się możliwość dodawania i usuwania elementów, to podstawa 🙂 Dodam również funkcję, która wyświetlać będzie element na szczycie kolejki, czyli ten, który zostanie rozpatrzony najszybciej. Opcja wyświetlenia zawartości kolejki, też może okazać się użyteczna, dodaję. Na koniec jeszcze dwie funkcje, jedna do sprawdzania ilości elementów w kolejce, druga do informowania, czy kolejka nie jest aby pusta. I tyle, tak jak pisałem, sporo podobieństw do stosu. Jednak, kolejka jest na tyle unikatowa, ze pozwala na wiele zastosowań, nie osiągalnych przy użyciu stosu.
Podsumowując, oto metody, które dodam do klasy kolejki:
- Dodawanie elementu
- Usuwanie elementu
- Wyświetlanie pierwszego elementu
- Wyświetlenie całej zawartości kolejki
- Wyświetlenie ilości elementów
- Wyświetlenie zawiera w ogóle jakieś elementy
Ok no to zaczynam. Najpierw oczywiście konstruktor:
|
1 2 3 |
function Queue() { this.data = []; } |
Póki co dodaję tylko jedno pole. Tablicę o nazwie data. Dzięki wielu pomocnym metodom tablicy, JavaScript pozwala na bardzo łatwą implementację struktur danych. A oto dwie pierwsze metody naszej klasy, potwierdzające to o czym piszę: metody służące do dodawania i usuwania elementów.
|
1 2 3 4 5 6 7 |
Queue.prototype.enqueue = function(elem) { this.data.push(elem); }; Queue.prototype.dequeue = function() { return this.data.shift(); }; |
Funkcja tablicowa push, wykorzystana w metodzie enqueue, dodaje element na końcu tablicy. Z kolei funkcja shift, której używam w metodzie dequeue, usuwa jej pierwszy element. Tak jak pisałem, idealnie nadają się do naszej implementacji kolejki.
Ponad to, metoda, usuwająca element dequeue także ten element zwraca, w razie jakby było potrzebne zarejestrowanie co zostało usunięte.
Następne dwie metody, które wezmę na tapetę to metody odpowiedzialne za zwrócenie pełnej listy elementów kolejki, oraz zwrócenie pierwszego elementu.
|
1 2 3 4 5 6 7 |
Queue.prototype.viewAll = function() { return this.data.join(', '); }; Queue.prototype.front = function() { return this.data[0]; }; |
Tym razem w metodzie viewAll wykorzystuje funkcję tablicową join. Łączy ona nam wszystkie elementy tablic w jeden łańcuch znaków, rozdzielające je tym co podaję w argumencie. W obecnym przypadku, metoda zwróci listę elementów, wypisanych po przecinku.
Metoda front zwraca po prostu to co znajduje się na początku (czyli pod indeksem 0) tablicy data.
Ostatnie dwie metody queueLength oraz isEmpty służą odpowiednio do zwrócenia ilości elementów w kolejce oraz wartości boolowskiej, mówiącej czy jest pusta czy nie.
|
1 2 3 4 5 6 7 8 9 10 11 |
Queue.prototype.queueLength = function() { return this.data.length; }; Queue.prototype.isEmpty = function() { if(this.data.length === 0) { return true; } else { return false; } }; |
I tutaj nie ma żadnych większych filozofii. queueLength korzysta z właściwości tablicy length, zwracając jej wartość. isEmpty, natomiast zwraca true, jeśli length pola data jest równe zero, w innym wypadku zwraca false.
I to wszystko. Cała implementacja kolejki. Nic skomplikowanego. W kolejnym podam przykładowe wykorzystania tej klasy.