ArrayDeque, Java, Kolejka (Queue), Kolekcje

Kolekcje Javy – Interfejs Queue

by Red 26 marca 2020

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.

Deque<String> stack = new ArrayDeque<String>();

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ą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.

//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());

//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.

[Kamil, Franek, Paula]
[Franek, Paula]

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.

//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());

//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();

System.out.println(stosKoszulek.toString());

Wynik działania programu.

[Zielona koszulka, Czerwona koszulka, Niebieska koszulka]
[Niebieska koszulka]

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.

Tweetuj

Udostępnij

Przypnij

0 Udostępnień