Preskoči na glavni sadržaj

Detaljno o Java dvostrukom redu (ArrayDeque sa analizom izvornog koda)

Chenmo Wang ErJava jezgroOkvir kolekcija (kontejneri)2496 reči8 minuta

U ovom odeljku nastavljamo — pozovimo učitelja Vanga na scenu da nam održi čas o ArrayDeque, pljesak dobrodošlice! 👏🏻.

U Javi postoji klasa koja se zove Stack, ali ne postoji klasa koja se zove Queue (to je samo ime interfejsa, za razliku od klase).

public interface Queue<E> extends Collection<E> {}

Kada nam je potreban stek, Java više ne preporučuje Stack, već efikasniji ArrayDeque (dvostruki red). Razlog smo već pomenuli kada smo prvi put pričali o okviru kolekcija — Stack je „primitivna” klasa čije sve ključne metode nose synchronized kako bi se obezbedila bezbednost niti, pa kada nam bezbednost niti nije potrebna (na primer u jednonitnom okruženju) performanse su lošije.

Drugim rečima, kada nam je potreban stek, prvi izbor treba da bude ArrayDeque.

// Deklarišemo dvostruki red
ArrayDeque<String> stack = new ArrayDeque<>();

// Dodajemo elemente
stack.push("Chenmo");
stack.push("Wang Er");
stack.push("Chen Qingyang");

// Dohvatamo element sa vrha steka
String top = stack.peek();
System.out.println("Element na vrhu steka: " + top); // Chen Qingyang

// Skidamo element sa vrha steka
String pop = stack.pop();
System.out.println("Skinuti element: " + pop); // Chen Qingyang

// Menjamo element na vrhu steka
stack.pop();
stack.push("Xiao Ming");
System.out.println("Stek nakon izmene: " + stack); // [Xiao Ming, Chenmo]

// Prolazimo kroz red i tražimo element
Iterator<String> iterator = stack.iterator();
int index = -1;
String target = "Wang Er";
while (iterator.hasNext()) {
    String element = iterator.next();
    index++;
    if (element.equals(target)) {
        break;
    }
}

if (index == -1) {
    System.out.println("Element " + target + " ne postoji u redu");
} else {
    System.out.println("Element " + target + " se nalazi na poziciji: " + index);
}

U gornjem primeru smo prvo kreirali objekat ArrayDeque, a zatim metodom push dodali tri elementa na stek. Zatim smo metodom peek dohvatili element sa vrha steka, metodom pop skinuli element sa vrha, kombinacijom pop i push promenili element na vrhu, i konačno iteratorom pronašli poziciju traženog elementa.

ArrayDeque takođe implementira Deque interfejs (a Deque proširuje Queue interfejs):

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{}

Zato, kada nam je potreban red, takođe možemo izabrati ArrayDeque.

ArrayDeque<String> queue = new ArrayDeque<>();

// Dodajemo elemente
queue.offer("Chenmo");
queue.offer("Wang Er");
queue.offer("Chen Qingyang");

// Dohvatamo element sa početka reda
String front = queue.peek();
System.out.println("Element na početku reda: " + front); // Chenmo

// Uklanjamo element sa početka reda
String poll = queue.poll();
System.out.println("Uklonjeni element: " + poll); // Chenmo

// Menjamo elemente u redu
queue.poll();
queue.offer("Xiao Ming");
System.out.println("Red nakon izmene: " + queue); // [Chen Qingyang, Xiao Ming]

// Tražimo element
Iterator<String> iterator = queue.iterator();
int index = 0;
while (iterator.hasNext()) {
    String element = iterator.next();
    if (element.equals("Wang Er")) {
        System.out.println("Element se nalazi na poziciji: " + index); // 0
        break;
    }
    index++;
}

U gornjem primeru smo prvo kreirali objekat ArrayDeque, a zatim metodom offer dodali tri elementa u red. Zatim smo metodom peek dohvatili element sa početka reda, metodom poll uklonili element sa početka, kombinacijom poll i offer promenili elemente u redu, i konačno iteratorom pronašli poziciju elementa.

Kao što smo već rekli, LinkedList nije samo List, već i Queue — on takođe implementira Deque interfejs.

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{}

Dakle, kada nam je potreban red, možemo izabrati i LinkedList.

// Kreiramo objekat LinkedList
LinkedList<String> queue = new LinkedList<>();

// Dodajemo elemente
queue.offer("Chenmo");
queue.offer("Wang Er");
queue.offer("Chen Qingyang");
System.out.println(queue); // Ispisuje [Chenmo, Wang Er, Chen Qingyang]

// Uklanjamo elemente
queue.poll();
System.out.println(queue); // Ispisuje [Wang Er, Chen Qingyang]

// Izmena elementa: elementi u LinkedList-u ne mogu se menjati direktno, prvo se uklanja pa dodaje
String first = queue.poll();
queue.offer("Wang Dasan");
System.out.println(queue); // Ispisuje [Chen Qingyang, Wang Dasan]

// Pretraga elementa: elementi u LinkedList-u mogu se naći metodom get()
System.out.println(queue.get(0)); // Ispisuje Chen Qingyang
System.out.println(queue.contains("Chenmo")); // Ispisuje false

// Pretraga elementa: korišćenjem iteratora tražimo Chen Qingyang
// Prolazimo kroz elemente redom i tražimo
Iterator<String> iterator = queue.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    if (element.equals("Chen Qingyang")) {
        System.out.println("Pronađeno: " + element);
        break;
    }
}

Kada LinkedList koristimo kao red, metodom offer() možemo dodavati elemente na kraj reda, metodom poll() uklanjati elemente s početka reda, a iteratorom ili metodom poll() redom prolaziti kroz elemente.

Stek i red

Da bismo pričali o steku i redu, prvo moramo objasniti interfejs Deque. Ime Deque znači „double ended queue”, odnosno dvostruki red — može se koristiti i kao stek i kao red. Sledeća tabela navodi metode Deque-a koji odgovaraju Queue interfejsu:

Queue MethodEquivalent Deque MethodObjašnjenje
add(e)addLast(e)Ubacuje element na kraj reda; pri neuspehu baca izuzetak
offer(e)offerLast(e)Ubacuje element na kraj reda; pri neuspehu vraća false
remove()removeFirst()Dohvata i briše element s početka; pri neuspehu baca izuzetak
poll()pollFirst()Dohvata i briše element s početka; pri neuspehu vraća null
element()getFirst()Dohvata bez brisanja element s početka; pri neuspehu baca izuzetak
peek()peekFirst()Dohvata bez brisanja element s početka; pri neuspehu vraća null

Sledeća tabela navodi metode Deque-a koji odgovaraju Stack interfejsu:

Stack MethodEquivalent Deque MethodObjašnjenje
push(e)addFirst(e)Ubacuje element na vrh steka; pri neuspehu baca izuzetak
—offerFirst(e)Ubacuje element na vrh steka; pri neuspehu vraća false
pop()removeFirst()Dohvata i briše element s vrha; pri neuspehu baca izuzetak
—pollFirst()Dohvata i briše element s vrha; pri neuspehu vraća null
peek()getFirst()Dohvata bez brisanja element s vrha; pri neuspehu baca izuzetak
—peekFirst()Dohvata bez brisanja element s vrha; pri neuspehu vraća null

Ove dve tabele zajedno definišu 12 metoda Deque interfejsa.

Dodavanje, brisanje i dohvatanje imaju po dva skupa metoda — iste funkcije, ali različito tretiranje neuspeha.

Jedan skup metoda pri neuspehu baca izuzetak, a drugi pri neuspehu vraća posebnu vrednost (false ili null). Osim kada implementacija ograničava kapacitet, u većini slučajeva operacija dodavanja neće otkazati.

Iako Deque ima čak 12 metoda, sve se svodi na operacije nad oba kraja kontejnera — dodavanje, brisanje ili uvid. Kada ovo razumemo, objašnjenje postaje vrlo jednostavno.

ArrayDeque i LinkedList su dve opšte implementacije Deque-a. Pošto zvanična preporuka za stek i red više ide na ArrayDeque, a LinkedList smo već obradili u prethodnom tekstu, ovde ćemo se fokusirati na konkretnu implementaciju ArrayDeque-a.

Iz imena se vidi da ArrayDeque u osnovi koristi niz. Da bi se zadovoljila potreba da se elementi ubacuju i uklanjaju na oba kraja niza, taj niz mora biti kružni — kružni niz (circular array), što znači da bilo koja tačka niza može biti shvaćena kao početak ili kraj.

ArrayDeque nije bezbedan za niti (not thread-safe); kada ga koristi više niti istovremeno, potrebna je ručna sinhronizacija. Takođe, ovaj kontejner ne dozvoljava null elemente.

Na gornjoj slici vidimo da head pokazuje na prvi validan element s prednje strane, a tail na prvu slobodnu poziciju na koju se može ubaciti element sa zadnje strane. Pošto je niz kružni, head ne mora uvek biti 0, a tail ne mora uvek biti veći od head.

Analiza metoda

addFirst()

addFirst(E e) ubacuje element na prednji kraj Deque-a, odnosno ispred head. Ako ima dovoljno prostora i indeks ne prelazi granice, dovoljno je izvršiti elements[--head] = e.

U praksi treba razmotriti:

  1. da li ima dovoljno prostora, i
  2. da li indeks prelazi granice.

Na gornjoj slici, ako je head jednak 0 i zatim pozovemo addFirst(), iako preostalog prostora ima, head postaje -1, što prelazi granice. Sledeći kod uspešno rešava oba problema.

//addFirst(E e)
public void addFirst(E e) {
    if (e == null)//ne dozvoljava null
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;//2. da li indeks prelazi granice
    if (head == tail)//1. da li ima prostora
        doubleCapacity();//proširenje kapaciteta
}

U ovom kodu vidimo da se problem prostora rešava nakon ubacivanja, jer tail uvek pokazuje na sledeću slobodnu poziciju, što znači da niz elements ima barem jednu slobodnu poziciju — prilikom ubacivanja elementa ne moramo brinuti o prostoru.

Rešavanje problema prelaska granica indeksa je vrlo jednostavno: head = (head - 1) & (elements.length - 1). Ovaj kod zapravo računa ostatak pri deljenju, a istovremeno rešava i slučaj kada je head negativan. Pošto elements.length mora biti stepen broja 2, elements - 1 u binarnom zapisu ima sve jedinice u nižim bitovima, pa AND operacija sa head - 1 radi kao modulo. Ako je head - 1 negativan (zapravo može biti samo -1), to odgovara dopuni (komplementu) u odnosu na elements.length.

Sada da kažemo nešto o funkciji za proširenje doubleCapacity(). Njena logika je da alocira veći niz (dvostruko veći od originalnog) i u njega kopira originalni niz. Proces je prikazan na slici ispod:

Na slici vidimo da se kopiranje obavlja u dva koraka: prvo se kopiraju elementi desno od head, a zatim elementi levo od head.

//doubleCapacity()
private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // broj elemenata desno od head
    int newCapacity = n << 1;//dvostruko od originalnog prostora
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);//kopira desnu polovinu, odgovara zelenom delu na slici iznad
    System.arraycopy(elements, 0, a, r, p);//kopira levu polovinu, odgovara sivom delu na slici iznad
    elements = (E[])a;
    head = 0;
    tail = n;
}

U implementaciji ove metode se prvo proverava da li su head i tail jednaki; ako nisu, baca se izuzetak. Zatim se izračunava broj elemenata desno od head, označen sa r, i novi kapacitet newCapacity; ako je newCapacity prevelik, baca se izuzetak.

Zatim se kreira novi Object niz a, u čiji se prednji deo kopiraju elementi desno od head originalnog ArrayDeque-a (zeleni deo na slici), a u zadnji deo elementi levo od head (sivi deo na slici). Na kraju se niz elements zamenjuje sa a, head postavlja na 0, a tail na n (dužina novog kapaciteta).

Treba napomenuti da, pošto se niz elements zamenjuje nizom a, nakon poziva metode stari niz elements više nije referenciran i sakupljač otpada će ga očistiti.

addLast()

addLast(E e) ubacuje element na zadnji kraj Deque-a, odnosno na poziciju tail. Pošto tail uvek pokazuje na sledeću slobodnu poziciju, dovoljno je izvršiti elements[tail] = e;. Nakon ubacivanja ponovo se proverava prostor; ako je prostor potrošen, poziva se doubleCapacity() radi proširenja.

public void addLast(E e) {
    if (e == null)//ne dozvoljava null
        throw new NullPointerException();
    elements[tail] = e;//dodela vrednosti
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)//obrada prelaska granica indeksa
        doubleCapacity();//proširenje kapaciteta
}

Način obrade prelaska granica indeksa već je objašnjen u addFirst(), pa nećemo ponavljati.

pollFirst()

pollFirst() briše i vraća element s prednje strane Deque-a, odnosno element na poziciji head. Ako kontejner nije prazan, dovoljno je direktno vratiti elements[head], uz obradu indeksa. Pošto se u ArrayDeque ne sme ubaciti null, kada je elements[head] == null to znači da je kontejner prazan.

public E pollFirst() {
    E result = elements[head];
    if (result == null)//null znači da je deque prazan
        return null;
    elements[h] = null;//neka GC radi
    head = (head + 1) & (elements.length - 1);//obrada prelaska granica indeksa
    return result;
}

pollLast()

pollLast() briše i vraća element sa zadnje strane Deque-a, odnosno element ispred pozicije tail.

public E pollLast() {
    int t = (tail - 1) & (elements.length - 1);//pozicija pre tail je poslednji element
    E result = elements[t];
    if (result == null)//null znači da je deque prazan
        return null;
    elements[t] = null;//neka GC radi
    tail = t;
    return result;
}

peekFirst()

peekFirst() vraća (bez brisanja) element s prednje strane Deque-a, odnosno element na poziciji head — dovoljno je direktno vratiti elements[head].

public E peekFirst() {
    return elements[head]; // elements[head] is null if deque empty
}

peekLast()

peekLast() vraća (bez brisanja) element sa zadnje strane Deque-a, odnosno element ispred pozicije tail.

public E peekLast() {
    return elements[(tail - 1) & (elements.length - 1)];
}

Kratak pregled

Kada je potrebno realizovati strukturu podataka sa first-in-first-out (FIFO) ili last-in-first-out (LIFO) ponašanjem, razmotrite ArrayDeque. Evo nekoliko scenarija za korišćenje ArrayDeque-a:

  • Upravljanje redom zadataka: ako treba realizovati red zadataka, ArrayDeque se može koristiti za čuvanje zadataka. Novi zadaci se dodaju na početak reda, a uzimaju s kraja radi obrade, čime se osigurava redosled izvršenja po principu FIFO.
  • Realizacija steka: ArrayDeque se može koristiti kao stek, uz podršku za push, pop, peek i slične operacije, pogodan za scenarije koji zahtevaju LIFO ponašanje.
  • Realizacija keša: kada je potrebno keširati određeni broj podataka, može se koristiti ArrayDeque. Kada količina keširanih podataka premaši kapacitet, najstariji podaci se uklanjaju s početka, a novi dodaju na kraj.
  • Realizacija obrađivača događaja: ArrayDeque može poslužiti kao osnova za obrađivač događaja — uzimanje događaja s početka radi obrade i dodavanje novih događaja na kraj.

Da ukratko sumiramo.

ArrayDeque je implementacija dvostrukog reda u standardnoj Java biblioteci, zasnovana na nizu. U poređenju sa LinkedList, ArrayDeque ima bolje performanse jer elemente čuva u kontinualnom memorijskom prostoru, bolje iskorišćava CPU keš i u većini slučajeva je brži.

Zašto to kažemo?

Zato što je u osnovi ArrayDeque-a niz, a u osnovi LinkedList-a povezana lista. Niz je jedan kontinualan memorijski blok, dok povezanu listu čini više čvorova, pri čemu svaki čvor čuva podatke i pokazivač na sledeći čvor. Zato pri korišćenju LinkedList-a često treba alokirati i oslobađati memoriju, dok ArrayDeque već pri kreiranju jednom alocira kontinualni memorijski prostor i ne zahteva čestu alokaciju i oslobađanje — na taj način bolje iskorišćava CPU keš i povećava efikasnost pristupa.

Moderni CPU-i snažno zavise od lokalnosti podataka: ako su podaci kojima se pristupa u memoriji uskladišteni kontinualno, može se iskoristiti mehanizam CPU keša i povećati efikasnost pristupa. Kada su podaci raspoređeni po različitim memorijskim blokovima, svaki pristup zahteva čitanje iz memorije, što smanjuje efikasnost.

Naravno, pri korišćenju ArrayDeque-a i kopiranje niza treba uzeti u obzir kao jedan od troškova performansi.

Kada broj elemenata u ArrayDeque-u premaši početni kapacitet, pokreće se operacija proširenja. Proširenje kreira novi niz i u njega kopira postojeće elemente. Vremenska složenost proširenja je O(n).

Međutim, strategija proširenja ArrayDeque-a (kada broj elemenata dostigne kapacitet niza, kapacitet se udvostručuje) u određenoj meri smanjuje broj i trajanje kopiranja niza, a istovremeno održava performanse i iskorišćenost prostora.

ArrayDeque ne samo da podržava uobičajene operacije reda — dodavanje elemenata, brisanje elemenata, dohvatanje elementa s početka i s kraja — već podržava i operacije steka, poput push, pop, peek. Time ArrayDeque postaje vrlo fleksibilna struktura podataka, pogodna za skladištenje i obradu podataka u raznim scenarijima.

Referenca: https://github.com/CarpenterLee/JCFInternals, autor: Li Hao, obrada: Chenmo Wang Er