Java programátor expert
ArrayDeque: Dátová štruktúra array deque v Jave
ArrayDeque (Array Double-Ended Queue) je dynamická obojsmerná fronta postavená na prstencovom poli, ktorá vkladá aj odoberá prvky na oboch koncoch v konštantnom čase. V článku sa pozrieme na to, aké konštruktory ponúka, v ktorých situáciách sa po nej oplatí siahnuť a ako ju využiť pri modelovaní prioritného radu zákazníkov.
V článku sa dozvieš:
Pojem array deque označuje dvojstrannú frontu implementovanú na báze dynamického poľa. V Jave ju reprezentuje trieda ArrayDeque.
ArrayDeque v Java – predstavenie dátovej štruktúry
Java ArrayDeque (Array Double-Ended Queue) dátová kolekcia je implementácia (k dispozícii od Java 1.6) rozhrania Deque využívajúca prstencové (circular) dynamické pole, ktoré zdvojnásobí svoju veľkosť, keď sa naplní. Podporuje pridávanie aj odoberanie prvkov na oboch koncoch fronty v konštantnom čase O(1) a to preto, lebo si pamätá odkazy na začiatok/hlavičku poľa (head) a koniec poľa (tail).
Odporúčame ti…
ArrayDeque je jednou z množstva dátových štruktúr (kolekcií) na jednoduchšiu prácu s dátami. V našom seriáli si postupne predstavíme aj rôzne ďalšie dátové štruktúry. Ukážeme si, ako s nimi pracovať, aké operácie sa s nimi dajú robiť, aké sú najčastejšie používané metódy. Spomenieme výhody a nevýhody a kedy je vhodné konkrétnu dátovú štruktúru použiť.
Na rozdiel od LinkedList, ktorá tiež implementuje Deque, ArrayDeque má menšiu réžiu priestorového zápisu a je rýchlejšia v prístupe k prvkom. Implementáciu ArrayDeque možno použiť ako zásobník (LIFO – Last In First Out) alebo frontu (FIFO – First In First Out). Pole ArrayDeque nie je synchronizované. To znamená, že nie je bezpečný pre viacvláknové spracovanie. Nulové prvky sú v ArrayDeque zakázane.
ArrayDeque – konštruktory
Pre vytvorenie inštancie ArrayDeque máme k dispozícii niekoľko konštruktorov:
1. Prázdna ArrayDeque
Vytvorí prázdnu ArrayDeque s predvolenou kapacitou (16).
ArrayDeque()
2. ArrayDeque s definovanou počiatočnou kapacitou
Vytvorí ArrayDeque so zadanou počiatočnou kapacitou.
ArrayDeque(int numElements)3. ArrayDeque skonštruovaná z existujúcej kolekcie
Vytvorí ArrayDeque obsahujúca prvky z existujúcej kolekcie (v poradí iterácie).
ArrayDeque(Collection<? extends E> c)ArrayDeque – základné operácie
Medzi základné operácie, ktoré môžeme vykonávať s ArrayDeque, patria:
- Vkladanie prvkov
Pomocou metód addFirst(E e) alebo offerFirst(E e) sa vloží prvok na začiatok.
Pomocou metód addLast(E e) alebo offerLast(E e) sa vloží prvok na koniec. - Prístup ku prvkom
Pomocou metód getFirst(E e) alebo peekFirst(E e) získame referenciu na prvok na začiatku.
Pomocou metód getLast(E e) alebo peekLast(E e) získame referenciu na prvok na konci. - Odstraňovanie prvkov
Metóda removeFirst() alebo pollFirst() sa používa na odstránenie prvku zo začiatku.
Metóda removeLast() alebo pollLast() sa používa na odstránenie prvku z konca. - Vyprázdnenie kolekcie
Metóda clear() odstráni všetky prvky z ArrayDeque kolekcie. - Vyhľadávanie prvkov podľa kľúča alebo hodnoty
Metóda containsKey(Object o) zisťuje, či sa zadaný prvok nachádza v kolekcii. - Zistenie veľkosti kolekcie
Metóda size() vráti počet záznamov (objektov) danej ArrayDeque. - Iterácia cez prvky
Pri iterácii cez iterator() iterujeme prvkami od začiatku na koniec.
Pri iterácii cez descendingIterator() iterujeme prvkami od konca opačným smerom.
Poznámka: Dvojice vyššie uvedených metód robia to isté, rozdiel je v návratovej hodnote. Prvá uvedená metóda vyvolá v prípade neúspechu výnimku a druhá boolean hodnotu true/false.
Dokumentácia k Java ArrayDeque
Kompletný prehľad metód triedy ArrayDeque, nájdeš v oficiálnej dokumentácii.
Java ArrayDeque – výhody a nevýhody
Výhody ArrayDeque
- Rýchle operácie na oboch koncoch
S konštantnou časovou zložitosťou O(1) pre pridávanie a odoberanie prvkov. - Nízka réžia pamäte
Interná reprezentácia ArrayDeque je dynamické pole bez ďalších uzlov či odkazov. - Bez limitu kapacity
ArrayDeque sa automaticky zväčšuje podľa potreby.
Nevýhody ArrayDeque
- Nie je thread-safe
Ak potrebuješ viacvláknovú synchronizáciu, odporúčame použiť LinkedBlockingDeque. - Žiadny random access (náhodný) prístup
Ak je základom dynamické pole, funguje iba ako obojsmerná fronta.
Java ArrayDeque – kedy ju použiť?
ArrayDeque je ideálna v prípadoch, keď:
- Potrebujeme implementovať frontu alebo zásobník (Deque).
- Pri správe úloh ako je napr. Task Manager.
- Hodia sa pre Sliding Window Algorithms
Príklad použitia ArrayDeque v Jave
Teraz si ukážeme, ako s kolekciou ArrayDeque v Java prakticky pracovať. Dátová štruktúra ArrayDeque sa využíva v programoch, ktoré potrebujú pracovať s prvkami na začiatku a na konci poľa.
Na ilustráciu práce s ArrayDeque s využitím jej základných metód si naprogramujeme simuláciu fronty zákazníkov čakajúcich na kúpenie lístkov. Budeme mať obyčajných a VIP zákazníkov, obaja sa po príchode normálne zaradia na koniec radu. VIP zákazníci budú však okamžite presunutí dopredu na prioritné obslúženie. Výsledky v prehľadnej forme vypíše do konzoly.
Customer.java
public class Customer {
private final String name;
private final boolean vip;
public Customer(String name, boolean vip) {
this.name = name;
this.vip = vip;
}
public String getName() {
return name;
}
public boolean isVip() {
return vip;
}
@Override
public String toString() {
return name + (vip ? " [VIP]" : " [Regular]");
}
}TicketQueueSimulation.java
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Random;
public class TicketQueueSimulation {
private final Deque<Customer> queue = new ArrayDeque<>();
private final Random random = new Random();
public void simulateQueue() {
// Generate 8 customers
for (int i = 1; i <= 8; i++) {
boolean isVip = random.nextBoolean(); // Randomly decide if VIP
Customer customer = new Customer("Customer " + i, isVip);
if (isVip) {
// VIP customers will be prioritized at the front
queue.addFirst(customer);
System.out.println("🎟️ New VIP arrived and prioritized: " + customer);
} else {
// Regular customers join at the end
queue.addLast(customer);
System.out.println("🎟️ New regular customer arrived: " + customer);
}
}
System.out.println("\n🏁 Queue formed:");
printQueue();
// Start serving customers
System.out.println("\n🛎️ Starting service:");
while (!queue.isEmpty()) {
Customer customer = queue.pollFirst(); // Serve from the front
System.out.println("✅ Serving: " + customer);
simulateServiceTime();
}
System.out.println("\n🎉 All customers have been served!");
}
// Simulate time taken to serve a customer
private void simulateServiceTime() {
try {
Thread.sleep(500); // 500 ms delay
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
// Display the current queue status
private void printQueue() {
if (queue.isEmpty()) {
System.out.println("🔵 The queue is empty.");
return;
}
for (Customer customer : queue) {
System.out.println("🔹 " + customer);
}
}
public static void main(String[] args) {
TicketQueueSimulation simulation = new TicketQueueSimulation();
simulation.simulateQueue();
}
}Výstup z tohto príkladu môže vyzerať nasledovne:
Pripravili sme pre teba súbory so spomínaným príkladom vo forme kódu, ktorý si môžeš spustiť priamo v Jave. Stiahni si Java kód pre ArrayDeque tu.
