Cozi și clasa ArrayDeque

Coziile reprezintă o structură de date care funcționează după principiul FIFO (first in - first out). Adică, cu cât un element a fost adăugat mai devreme în colecție, cu atât va fi eliminat mai devreme. Acesta este modelul standard al unei cozi unidirecționale. Totuși, există și cozi bidirecționale – adică acelea în care putem adăuga un element nu doar la început, ci și la sfârșit. Și, corespunzător, putem elimina un element nu doar din coadă, ci și din început.

Caracteristica claselor cozi este că implementează interfețele speciale Queue sau Deque.

Interfața Queue

Interfața generalizată Queue<E> extinde interfața de bază Collection și definește comportamentul clasei ca o coadă unidirecțională. Funcționalitatea sa este oferită prin următoarele metode:

E element(): returnează, dar nu elimină, elementul din capul cozii. Dacă coada este goală, generează excepția NoSuchElementException
boolean offer(E obj): adaugă elementul obj la sfârșitul cozii. Dacă elementul a fost adăugat cu succes, returnează true, altfel - false
E peek(): returnează fără a elimina elementul din capul cozii. Dacă coada este goală, returnează valoarea null
E poll(): returnează cu eliminare elementul din capul cozii. Dacă coada este goală, returnează valoarea null
E remove(): returnează cu eliminare elementul din capul cozii. Dacă coada este goală, generează excepția NoSuchElementException

Astfel, toate clasele care implementează această interfață vor avea metoda offer pentru adăugarea în coadă, metoda poll pentru extragerea unui element din capul cozii și metodele peek și element pentru a obține pur și simplu elementul din capul cozii.

Interfața Deque

Interfața Deque extinde interfața Queue descrisă mai sus și definește comportamentul unei cozi bidirecționale, care funcționează fie ca o coadă unidirecțională obișnuită, fie ca un stack care funcționează pe principiul LIFO (ultimul intrat - primul ieșit).

Interfața Deque definește următoarele metode:

void addFirst(E obj): adaugă un element la începutul cozii
void addLast(E obj): adaugă elementul obj la sfârșitul cozii
E getFirst(): returnează fără a elimina elementul din capul cozii. Dacă coada este goală, generează excepția NoSuchElementException
E getLast(): returnează fără a elimina ultimul element al cozii. Dacă coada este goală, generează excepția NoSuchElementException
boolean offerFirst(E obj): adaugă elementul obj la începutul cozii. Dacă elementul a fost adăugat cu succes, returnează true, altfel - false
boolean offerLast(E obj): adaugă elementul obj la sfârșitul cozii. Dacă elementul a fost adăugat cu succes, returnează true, altfel - false
E peekFirst(): returnează fără a elimina elementul din capul cozii. Dacă coada este goală, returnează valoarea null
E peekLast(): returnează fără a elimina ultimul element al cozii. Dacă coada este goală, returnează valoarea null
E pollFirst(): returnează cu eliminare elementul din capul cozii. Dacă coada este goală, returnează valoarea null
E pollLast(): returnează cu eliminare ultimul element al cozii. Dacă coada este goală, returnează valoarea null
E pop(): returnează cu eliminare elementul din capul cozii. Dacă coada este goală, generează excepția NoSuchElementException
void push(E element): adaugă un element la începutul cozii
E removeFirst(): returnează cu eliminare elementul din capul cozii. Dacă coada este goală, generează excepția NoSuchElementException
E removeLast(): returnează cu eliminare elementul din capătul cozii. Dacă coada este goală, generează excepția NoSuchElementException
boolean removeFirstOccurrence(Object obj): elimină primul element întâlnit obj din coadă. Dacă eliminarea a avut loc, returnează true, altfel returnează false
boolean removeLastOccurrence(Object obj): elimină ultimul element întâlnit obj din coadă. Dacă eliminarea a avut loc, returnează true, altfel returnează false

Astfel, existența metodelor pop și push permite claselor care implementează acest element să funcționeze ca un stack. În același timp, funcționalitatea existentă permite și crearea cozilor bidirecționale, ceea ce face ca clasele care aplică această interfață să fie destul de flexibile.

Clasa ArrayDeque

În Java, cozile sunt reprezentate de o serie de clase. Una dintre acestea este clasa ArrayDeque<E>. Această clasă reprezintă o coadă bidirecțională generalizată, moștenind funcționalitatea de la clasa AbstractCollection și aplicând interfața Deque.

În clasa ArrayDeque sunt definiți următorii constructori:

ArrayDeque(): creează o coadă goală
ArrayDeque(Collection<? extends E> col): creează o coadă plină cu elemente din colecția col
ArrayDeque(int capacity): creează o coadă cu capacitatea inițială capacity. Dacă nu specificăm explicit capacitatea inițială, capacitatea implicită va fi 16

Exemplu de utilizare a clasei:

import java.util.ArrayDeque;

public class Program{
     
   public static void main(String[] args) {
         
       ArrayDeque<String> states = new ArrayDeque<String>();
       // adăugare standard de elemente
       states.add("Germany");
       states.addFirst("France"); // adăugăm un element la început
       states.push("Great Britain"); // adăugăm un element la început
       states.addLast("Spain"); // adăugăm un element la sfârșitul colecției
       states.add("Italy");
         
       // obținem primul element fără a-l elimina
       String sFirst = states.getFirst();
       System.out.println(sFirst);     // Great Britain
       // obținem ultimul element fără a-l elimina
       String sLast = states.getLast();
       System.out.println(sLast);      // Italy
       
       System.out.printf("Dimensiunea cozii: %d \n", states.size());  // 5
       
       // parcurgerea colecției        
       while(states.peek()!=null){
           // extragere de la început
           System.out.println(states.pop());
       }
         
        // coadă de obiecte Person
       ArrayDeque<Person> people = new ArrayDeque<Person>();
       people.addFirst(new Person("Tom"));
       people.addLast(new Person("Nick"));
       // parcurgere fără extragere
       for(Person p : people){
         
           System.out.println(p.getName());
       }
   }
}
class Person{
     
   private String name;
   public Person(String value){
         
       name=value;
   }
   String getName(){return name;}
}