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.

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ątek NoSuchElementException.
  • void addLast(E element) – dodaje element na końcu kolejki.
  • E removeLast() – usuwa ostatni element z kolejki. Jeśli kolejka jest pusta rzuca wyjątek NoSuchElementException.
  • 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ątek NoSuchElementException
  • E getFirst()– zwraca pierwszy element, ale go nie usuwa. Jeśli kolejka jest pusta rzuca wyjątek NoSuchElementException.
  • E getLast() – zwraca ostatni element, ale go nie usuwa. Jeśli kolejka jest pusta rzuca wyjątek NoSuchElementException.
  • 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.

Wynik działania programu jest następujący.

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.

Wynik działania programu.

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.