Kolekcje Javy – Interfejs Queue

ByKamil

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 ArrayList również w przypadku ArrayDeque użyta jest implementacja oparta na tablicy o dynamicznym rozmiarze. Jest to pojemność bez ograniczeń (z wyjątkiem sprzętowych jak np. pamięć) i może zostać powiększona w razie potrzeby.

Tak jak wcześniejsze klasy ta również nie posiada mechanizmu synchronizacji między wątkami.

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.

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ątkiem NoSuchElementException.
  • void addLast(E element) – dodaje element na końcu kolejki.
  • E removeLast() – usuwa pierwszy element z kolejki. Jeśli kolejka jest pusta rzuca wyjątkiem 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ątkiem NoSuchElementException
  • E getFirst() – zwraca pierwszy element, ale go nie usuwa. Jeśli kolejka jest pusta rzuca wyjątkiem NoSuchElementException.
  • E getLast() – zwraca ostatni element, ale go nie usuwa. Jeśli kolejka jest pusta rzuca wyjątkiem 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 przychodzenia kolejnych osób ko kasy sklepowej w celu opłacenia należności za kopowane produkty.

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

Kolejne osoby podchodzące do kasy są dodawane do kolejki przez metodę add(). Jeżli 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 kładzione 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ąć wszystki 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.

About the author

Kamil editor