Kolekcje Javy – Interfejs Queue
W artykule o kolejkach przedstawiliśmy podstawowe operacje oraz budowę kolejek. Podobnie jak w przypadku list nie trzeba implementować algorytmów na własną rękę i można skorzystać z biblioteki udostępnionej przez Javę. Istnieje wiele implementacji interfejsów Queue
oraz Deque
.
Klasa ArrayDeque
Podobnie jak w przypadku ArrayList
w klasie ArrayDeque
jest użyta struktura danych oparta na tablicy o dynamicznym rozmiarze. Jej pojemność teoretycznie nie posiada ograniczeń (z wyjątkiem sprzętowych jak np. pamięć) i może zostać powiększona w razie potrzeby.
Klasa ArrayDeque
może zostać użyta zarówno jako stos (kolejka LIFO), jak i zwykła kolejka FIFO.
W bibliotece Javy istnieje klasa Stack
, która była dostępna już w pierwszej wersji Javy, jednak nie należy z niej korzystać, gdyż jest mniej wydajna. Podobnie w przypadku kolejek FIFO klasa ArrayDeque
radzi sobie lepiej niż klasa LinkedList
.
Klasa ta nie posiada mechanizmu synchronizacji między wątkami.
Konstruktory
ArrayDeque<E>()
– tworzy pustą listę o pojemności 16.ArrayDeque<E>(int countElements)
– Tworzy pustą listę o podanej w parametrze pojemności.
Aby utworzyć pustą listę można użyć następującego kodu. Niezmiennie polecamy używanie zmiennych interfejsowych.
1 |
Deque<String> stack = new ArrayDeque<String>(); |
Metody
void add(E element)
– dodaje element na końcu kolejki.void addFirst(E element)
– dodaje element na początku kolejki.E removeFirst()
– usuwa pierwszy element z kolejki. Jeśli kolejka jest pusta rzuca wyjątekNoSuchElementException
.void addLast(E element)
– dodaje element na końcu kolejki.E removeLast()
– usuwa ostatni element z kolejki. Jeśli kolejka jest pusta rzuca wyjątekNoSuchElementException
.E pollFirst()
– zwraca i usuwa pierwszy element kolejki lub null, gdy kolejka jest pusta. Nie rzuca wyjątku.E pollLast()
– zwraca i usuwa ostatni element kolejki lub null, gdy kolejka jest pusta. Nie rzuca wyjątku.void push(E element)
– dodaje element na początku kolejki.E pop()
– usuwa pierwszy element z kolejki. Jeśli kolejka jest pusta rzuca wyjątekNoSuchElementException
E getFirst()
– zwraca pierwszy element, ale go nie usuwa. Jeśli kolejka jest pusta rzuca wyjątekNoSuchElementException
.E getLast()
– zwraca ostatni element, ale go nie usuwa. Jeśli kolejka jest pusta rzuca wyjątekNoSuchElementException
.E peekFirst()
– zwraca pierwszy element kolejki lub null, gdy kolejka jest pusta. Nie rzuca wyjątku.E peeklLast()
– zwraca ostatni element kolejki lub null, gdy kolejka jest pusta. Nie rzuca wyjątku.void clear()
– usuwa wszystkie elementy z kolejki.<T> T[] toArray(T[] array)
– zwraca listę w postaci tablicowej.int size()
– zwraca rozmiar listy (liczbę aktualnie przechowywanych obiektów, a nie pojemności listy).
Porządek FIFO
Kolejka FIFO jest najbardziej znanym systemem kolejkowym. Pokażemy jej działanie na podstawie podchodzenia kolejnych osób do kasy sklepowej w celu opłacenia należności za kupowane produkty.
1 2 3 4 5 6 7 8 9 10 |
//Utwórz kolejkę Deque<String> kolejkaDoKasy = new ArrayDeque<String>(); kolejkaDoKasy.add("Kamil"); kolejkaDoKasy.add("Franek"); kolejkaDoKasy.add("Paula"); //Pokaż elementy kolejki System.out.println(kolejkaDoKasy.toString()); //Pierwsza osoba została obsłużona kolejkaDoKasy.pop(); System.out.println(kolejkaDoKasy.toString()); |
Wynik działania programu jest następujący.
1 2 |
[Kamil, Franek, Paula] [Franek, Paula] |
Kolejne osoby podchodzące do kasy są dodawane do kolejki przez metodę add()
. Jeżeli pierwsza osoba zostanie obsłużona, to metoda pop()
usunie ją z kolejki.
Porządek LIFO
Kolejka LIFO nie jest społecznie akceptowana, gdyż każdy kolejny dodawany element będzie obsłużony jako pierwszy. Nazywana jest również stosem. Wyobraźmy sobie półkę, na której trzymamy koszulki. Aby dostać się do tej na dnie musimy najpierw podnieść wszystkie te, które położyliśmy na niej.
1 2 3 4 5 6 7 8 9 10 11 |
//Utwórz kolejkę Deque<String> stosKoszulek = new ArrayDeque<String>(); stosKoszulek.push("Niebieska koszulka"); stosKoszulek.push("Czerwona koszulka"); stosKoszulek.push("Zielona koszulka"); //Pokaż elementy kolejki System.out.println(stosKoszulek.toString()); //Aby dostać się do niebieskiej koszulki musimy podnieść dwie dodane po niej stosKoszulek.pop(); stosKoszulek.pop(); System.out.println(stosKoszulek.toString()); |
Wynik działania programu.
1 2 |
[Zielona koszulka, Czerwona koszulka, Niebieska koszulka] [Niebieska koszulka] |
Koszulki były położone jedna na drugą, w związku z tym kolejność odczytu jest odwrotna niż ich dodawania. Aby dostać się do pierwszego dodanego elementu musimy najpierw zdjąć wszystkie później dodane koszulki.
ArrayDeque podsumowanie
Gdy potrzebujemy klasy, która implementuje kolejkę należy użyć ArrayDeque
. Jej porównanie w stosunku do ArrayList
wypada podobnie – różni je głównie strategia powiększania tablicy. Natomiast w porównaniu do LinkedList
lepiej sobie poradzi przy wykorzystaniu jako kolejka FIFO.