ArrayDeque: Dátová štruktúra array deque v Jave

Autor:  Jozef Wagner

Java • 5 min. čítania • 24. 7. 2025

Autor:  Jozef Wagner •

Java • 5 min. čítania • 24. 7. 2025

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.

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

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.

Java8 min.

4. 7. 2025

LinkedList (zoznam): Dátová štruktúra linked list v Jave

LinkedList sa hodí tam, kde ArrayList nestačí – pri častých zmenách v zozname. V článku sa dozvieš, ako funguje a ako si s ňou poradiť v Jave.

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.

Zdieľaj článok

ArrayDeque: Dátová štruktúra array deque v Jave

O autorovi

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.