La coadă

Pentru majoritatea oamenilor, cuvântul „coadă” aduce în minte foarte puține asocieri plăcute. Dar astăzi vorbim despre diferite cozi — cozi Java. În Java, o coadă este orice moștenește interfața Queue , care, la rândul său, extinde interfața Collection . Asta înseamnă că cozile pot fi tratate ca colecții.

Cozile în Java acceptă două principii de funcționare: FIFO și LIFO .

Principiul FIFO (First In, First Out) guvernează o coadă obișnuită - primul element adăugat în coadă este primul care o părăsește.

Principiul LIFO (Last In, First Out) descrie comportamentul unei stive - ultimul element adăugat în coadă este primul care îl părăsește. De exemplu, așa lucrezi cu un pachet de cărți: scoți cărțile din partea de sus pe rând până ajungi la partea de jos a pachetului.

Ierarhia Cozii în Java arată astfel:

Aici puteți vedea că Queue are 3 clase de implementare: LinkedList , ArrayDeque și PriorityQueue . LinkedList și ArrayDeque moștenesc direct nu Queue , ci Deque .

Deque este o interfață care a fost adăugată în Java 6. Include mai multe metode care sunt utile pentru cozi și permite unei cozi să funcționeze ca o coadă dublu (sau bidirecțională). Asta înseamnă că poate fiFIFOșiLIFO.

Unul dintre cei doi descendenți ai interfeței Deque este ArrayDeque . Acceptă o coadă cu două capete care vă permite să introduceți și să eliminați elemente de la ambele capete. Este, de asemenea, o matrice dinamică care crește automat în dimensiune.

Există, de asemenea, o clasă PriorityQueue , care este un descendent direct al Queue : se comportă diferit față de clasele care implementează Deque .

PriorityQueue este o coadă de prioritate care organizează elementele în conformitate cu ordinea lor naturală în mod implicit. Aici sortarea folosește interfețele Comparabil și Comparator . Principiul este același ca și în cazul TreeSet sau TreeMap — clase care folosesc interfața Comparable și au propria lor ordine de sortare.

PriorityQueue<String> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(String::length));

priorityQueue.add("Andrew");
priorityQueue.add("John");
priorityQueue.add("Rob");

while (!priorityQueue.isEmpty()) {
   System.out.println(priorityQueue.remove());
}

Dacă rulați acest exemplu, iată ce veți vedea în consolă:

Deoarece lucrăm cu cozi și nu cu colecții obișnuite, trebuie să eliminăm elementele din listă. Pentru a face acest lucru, folosim acest construct:

while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.remove());
}

Interfața Deque moștenește metodele Queue și adaugă câteva dintre propriile sale metode interesante:

Să ne uităm acum la câteva dintre aceste metode în practică.

Mai întâi, să adăugăm un element la o coadă:

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

        deque.add("Apple"); // Adds "Apple" to the end of the queue
        deque.addFirst("Orange"); // Adds "Orange" to the front of the queue
        deque.addLast("Pineapple"); // Adds "Pineapple" to the end of the queue

        System.out.println(deque);

Acum să obținem valori dintr-o coadă:

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

deque.add("Apple");
        deque.addFirst("Orange");
        deque.addLast("Pineapple");


        System.out.println("The first element is: "+ deque.getFirst());

        System.out.println("The last element is: " + deque.getLast());

    }

Acest cod afișează primul și ultimul element al cozii.

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

        deque.add("Apple");
        deque.addFirst("Orange");
        deque.addLast("Pineapple");
        deque.add("Lemon");

System.out.println(deque.pop()); // Get and remove the first element of the queue
System.out.println(deque.poll()); // Get and remove the first element of the queue

System.out.println(deque);

Rulând acest cod, obținem:

Diferența dintre pop() și poll() este că pop() va arunca o NoSuchElementException dacă lista este o listă goală, dar poll() va returna null .

Acum vom lua în considerare metodele pollFirst() și pollLast() .

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

        deque.add("Apple");
        deque.addFirst("Orange");
        deque.addLast("Pineapple");
        deque.add("Lemon");

System.out.println(deque.pollFirst()); // Get and remove the first element of the queue
System.out.println(deque.pollLast()); // Get and remove the last element of the queue.
System.out.println(deque);

Ambele metode returnează și elimină o valoare din coadă.

Iată un exemplu de utilizare a metodelor peekFirst() și peekLast() :

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

friends.add("John");
friends.add("Rob");
friends.add("Greg");
friends.add("Max");
friends.add("Oliver");

System.out.println("The first element is: " + friends.peekFirst());
System.out.println("The last element is: " + friends.peekLast());

System.out.println(friends);

Ambele metode returnează primul/ultimul element din coadă și nu le elimină. Dacă coada este goală, va fi returnat null .

Bine făcut! Astăzi am învățat cum să lucrăm cu cozile în Java. Acum știi cum să le folosești în practică.