Antrian Prioritas Jawa: dudu antrian klasik

Ing artikel iki kita sinau antrian prioritas, kelas Java, sing ngleksanakake antarmuka Antrian. Apa programer ngerti Antarmuka Antrian biasa? Kaping pisanan, antarmuka iki adhedhasar prinsip FIFO utawa "first in first out". Sing ngelingake antrian biasa ing makna umum. Sampeyan pengin njaluk kopi saka McDrive? Yen mobil sampeyan pisanan ing cedhak jendhela, sampeyan bakal njupuk kopi sadurunge sopir sing sabanjure.

Pranyatan Antarmuka Antrian

public interface Queue<E> extends Collection<E>

Apa antrian Prioritas

Apa antrian Prioritas? Kaping pisanan iku kelas sing ngleksanakake antarmuka Antrian ing cilik saka masang unsur saka mburi lan njabut unsur saka sirah. Nanging ora antrian biasa ing njero. Urutan unsur antrian prioritas Jawa gumantung saka prioritas unsur kasebut. Unsur kanthi prioritas paling dhuwur bakal dipindhah menyang kepala antrian. Yen sampeyan mbusak (nglayani) unsur peringkat paling dhuwur, sing nomer loro menyang sirah kanggo njupuk kopi. Kepiye carane nemtokake prioritas? Miturut dokumentasi, unsur antrian prioritas diurutake miturut urutan alam, utawa dening Comparator sing diwenehake ing wektu konstruksi antrian, gumantung saka konstruktor sing digunakake. Antrian prioritas adhedhasar tumpukan min prioritas. Tegese, yen ana unsur antrian angka, unsur pisanan antrian bakal minimal nomer iki. Cukup asring sawise maca definisi iki siswa anyar wiwit mikir sing antrian prioritas diurutake ing pangertèn linear. Sing, yen, ngomong, kita nggunakake antrian kang unsur nomer alam, banjur unsur pisanan bakal paling cilik, lan pungkasan - paling gedhe. Iki ora sakabehe bener. Kanggo ngerti carane antrian prioritas bener lan apa menehi, sampeyan kudu ngerti carane numpuk bisa. We nimbang struktur internal saka antrian prioritas nggunakake conto dicokot mengko. Saiki ayo mikir babagan atribut eksternal. banjur unsur pisanan bakal paling cilik, lan pungkasan - paling gedhe. Iki ora sakabehe bener. Kanggo ngerti carane antrian prioritas bener lan apa menehi, sampeyan kudu ngerti carane numpuk bisa. We nimbang struktur internal saka antrian prioritas nggunakake conto dicokot mengko. Saiki ayo mikir babagan atribut eksternal. banjur unsur pisanan bakal paling cilik, lan pungkasan - paling gedhe. Iki ora sakabehe bener. Kanggo ngerti carane antrian prioritas bener lan apa menehi, sampeyan kudu ngerti carane numpuk bisa. We nimbang struktur internal saka antrian prioritas nggunakake conto dicokot mengko. Saiki ayo mikir babagan atribut eksternal.

Konstruktor lan deklarasi kelas PriorityQueue

Kelas PriorityQueue nyedhiyakake 6 cara kanggo mbangun antrian prioritas ing Jawa.

• PriorityQueue () - antrian kosong karo kapasitas dhisikan standar (11) sing pesenan unsur miturut urutan alam.
• PriorityQueue (Koleksi c) - antrian kosong sing ngemot unsur ing koleksi kasebut.
• PriorityQueue(int initialCapacity) - antrian kosong kanthi kapasitas awal sing ditemtokake sing ngurutake unsur-unsur kasebut miturut urutan alami.
• PriorityQueue(int initialCapacity, Comparator comparator) - antrian kosong kanthi kapasitas awal sing ditemtokake sing ngurutake unsur kasebut miturut komparator sing ditemtokake.
• PriorityQueue (PriorityQueue c) - antrian kosong sing ngemot unsur ing antrian prioritas sing ditemtokake.
• PriorityQueue (SortedSet c) - antrian kosong sing ngemot unsur ing set sing diurutake.

Antrian Prioritas ing Jawa diumumake kanthi cara ing ngisor iki:

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

Nggawe PriorityQueue

Ayo nggawe antrian prioritas integer. Implementasi Priority Queue, kode Java:

PriorityQueue<Integer> numbers = new PriorityQueue<>();

Kita wis nggawe antrian prioritas tanpa bantahan. Ing kasus iki, kepala antrian prioritas yaiku nomer minimal antrian. Yen sampeyan mbusak sirah, unsur paling cilik sabanjuré bakal njupuk Panggonan iki. Supaya sampeyan bisa mbusak unsur saka antrian ing urutan munggah. Yen perlu, sampeyan bisa ngganti prinsip pesenan nggunakake antarmuka Comparator.

Metode PriorityQueue Jawa

PriorityQueue kelas Java duwe cara penting kanggo nambah, mbusak lan mriksa unsur.

Lebokake Elemen menyang Antrian Prioritas

• boolean add(obyek) nglebokake unsur kasebut menyang antrian prioritas. Ngasilake bener ing kasus sukses. Yen antrian kebak, cara mbalang pangecualian.
• tawaran boolean (obyek) nglebokake unsur kasebut menyang antrian prioritas iki. Yen antrian kebak, cara ngasilake palsu.

Sampeyan bisa nggunakake loro saka operasi nambah, ora ana beda kanggo mayoritas kasus. Iki minangka conto wiwitan lan nambah unsur menyang antrian prioritas.

import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        for (int i = 5; i > 0; i--) {
            priorityQueue1.add(i);
        }
        System.out.println(priorityQueue1);
    priorityQueue1.offer(0);
        System.out.println(priorityQueue1);
    }
}

Output yaiku:

[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]

Urutan unsur-unsur kasebut katon aneh, mengko bakal dijlentrehake.

Njupuk lan mbusak unsur saka Antrian Prioritas

• boolean mbusak (obyek) mbusak conto siji saka unsur kasebut saka antrian iki, yen ana.
• Obyek jajak pendapat () retrieves lan mbusak sirah antrian iki. Ngasilake null yen antrian kosong.
• void clear () mbusak kabeh unsur saka antrian prioritas.
• Unsur obyek () njupuk kepala antrian iki tanpa njabut. Mbuwang NoSuchElementException yen antrian kosong.
• Ndeleng obyek () retrieves sirah antrian tanpa njabut. Ngasilake null yen antrian kosong.

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //put 5 elements to the queue using add
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of the queue = " + priorityQueue.peek());
        //removing element by element from the queue using poll and print it out
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
        //put 5 new elements into the empty queue using offer
        for (int i = 10; i > 5; i--) {
            priorityQueue.offer(i);
        }
        System.out.println("now the head of the queue = " + priorityQueue.peek());
        System.out.println("the queue before removing 9:");
        System.out.println(priorityQueue);
        priorityQueue.remove(9);
        System.out.println("the queue after removing 9:");
        System.out.println(priorityQueue);
        //removing all the elements from the queue
        priorityQueue.clear();
        System.out.println(priorityQueue);
        //trying to print out the head of the empty Queue using peek - we'll get null
        System.out.println(priorityQueue.peek());
        //trying to print out the head of the empty Queue using element - we'll get the exception
        System.out.println(priorityQueue.element());
    }
}

Output:

the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
  at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
  at Priority2.main(Priority2.java:32)

Nalika sampeyan bisa ndeleng, nyoba kanggo print metu sirah antrian kosong nggunakake unsur () cara ndadékaké kanggo NoSuchElementexception .

PriorityQueue Comparator

• Comparator comparator () ngasilake comparator sing digunakake kanggo supaya unsur ing antrian. Ngasilake null yen antrian wis diurutake miturut urutan alam unsur sawijining.

antrian prioritas Jawa, contone karo komparator

Kita nggunakake urutan alami (munggah) ing conto kode ing ndhuwur, nanging kadhangkala kita kudu ngganti. Punika conto antrian prioritas Jawa, ngendi kita nggawe kelas komparator internal dhewe sing ngleksanakake antarmuka Comparator. Komparator kita bakal ngurutake unsur saka sing paling gedhe nganti sing paling cilik.

import java.util.PriorityQueue;
import java.util.Comparator;
 
class Priority3 {
    public static void main(String[] args) {
        // Creating a priority queue with myComparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of Queue = " + priorityQueue.peek());
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}
 
class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value = number1.compareTo(number2);
        //sorting elements from maximal to minimal
        if (value > 0) {
            return -1;
        } else if (value < 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

Output:

the head of Queue = 5
5
4
3
2
1

Kepala Antrian saiki ora minimal, nanging unsur maksimal, lan urutane diganti dadi malik.

Iterasi liwat PriorityQueue nggunakake iterator

ProrityQueue minangka bagéan saka kerangka Koleksi lan ngleksanakake antarmuka Iterable<> . Kanggo iterate liwat unsur antrian prioritas sampeyan bisa nggunakake iterator () cara. Punika conto:

import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;
 
class Priority4 {
   public static void main(String[] args) {
       // Creating a priority queue
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       //put 5 elements to the queue using add
       for (int i = 5; i > 0; i--) {
           priorityQueue.add(i);
       }
       //Iterating via iterator() method
       Iterator<Integer> iterator = priorityQueue.iterator();
       while (iterate.hasNext()) {
           System.out.print(iterator.next() + " ");
       }
   }
}

Output:

1 2 4 5 3 

Cara PriorityQueue liyane

• boolean ngemot (Obyek o) ngasilake bener yen antrian ngemot unsur o.
• int size () ngasilake nomer unsur ing antrian iki.
• Obyek [] toArray () ngasilake array sing ngemot kabeh unsur ing antrian iki.

Punika conto:

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority5 {
   public static void main(String[] args) {
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       for (int i = 5; i > 0; i--) {
           priorityQueue.offer(i);
       }
 
       System.out.println("our queue: " + priorityQueue);
 
       System.out.println("Does our queue contain 8?  " + priorityQueue.contains(8));
       System.out.println("Does queue contain 5?  " + priorityQueue.contains(5));
 
       System.out.println("The quantity of queue elements: " + priorityQueue.size());
       Object[] myArray = priorityQueue.toArray();
       System.out.println("print out our array:");
       for (Object name : myArray) {
           System.out.println(name);
       }
   }
}

Output:

our queue: [1, 2, 4, 5, 3]
Does our queue contain 8?  false
Does our queue contain 5?  true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3

PriorityQueue Java 8 definisi

Yen sampeyan mbukak dokumentasi priorityqueue java 8, sampeyan bakal nemokake definisi sabanjure: Antrian prioritas tanpa wates adhedhasar tumpukan prioritas. Unsur antrian prioritas diurutake miturut urutan alam, utawa dening Comparator sing diwenehake ing wektu konstruksi antrian, gumantung saka konstruktor sing digunakake. Antrian prioritas ora ngidini unsur null. Antrian prioritas sing gumantung ing urutan alam uga ora ngidini nglebokake obyek sing ora bisa dibandhingake (mengkono bisa nyebabake ClassCastException). Heap minangka tembung sing penting banget ing kene. Iki nerangake sifat urutan unsur Antrian Prioritas.

Prinsip kerja PriorityQueue: Binary Heap

Ayo dadi miwiti karo conto. Ayo nggawe rong obyek sing ngetrapake antarmuka Antrian. Salah sijine LinkedList, sing nomer loro - PriorityQueue. Loro-lorone duwe 5 unsur Integer (1,2,3,4 lan 5) lan kita miwiti kanggo sijine unsur menyang antrian saka paling gedhe kanggo paling cilik. Dadi, sing pisanan teka 5, banjur 4, 3, 2 lan sing pungkasan bakal dadi 1. Banjur nyithak dhaptar loro kasebut kanggo mriksa pesenan kasebut.

   Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
       System.out.println("PriorityQueue: " + priorityQueue)

Asil saka kode kasebut yaiku ing ngisor iki:

LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]

Inggih, urutan linkedlist bisa ditebak lan bisa dingerteni. Diurutake miturut prinsip FIFO. Kita miwiti karo 5, supaya unsur iki paling pisanan ing baris, banjur dadi 4 lan ing. Apa kita bisa ngomong bab urutan antrian prioritas? Docs ngandika sing unsur antrian prioritas diurutake miturut urutan alam, utawa dening Comparator kasedhiya ing wektu construction antrian. Nanging urutan iki ora katon "alami" ing makna ngurutake linear. Kita luwih seneng nyana [1, 2, 3, 4, 5], ora [1, 2, 4, 5, 3]. Kanggo mangerteni kenapa urutan njupuk kaya iku, kita kudu ngelingi antrian prioritas adhedhasar tumpukan. Apa tumpukan? Iku struktur data adhedhasar wit binar. Properti utama tumpukan: prioritas saben wong tuwa luwih gedhe tinimbang prioritas anak-anake. Ayo kula ngelingake yen wit diarani binar lengkap yen saben wong tuwa ora duwe anak luwih saka loro, lan ngisi tingkat saka ndhuwur nganti ngisor (saka tingkat sing padha - saka kiwa menyang tengen). Binary heap reorganises dhewe saben wektu unsur ditambahake utawa dibusak saka iku. Ing cilik saka min-numpuk, unsur paling cilik menyang ROOT preduli saka urutan sisipan sawijining. Antrian prioritas adhedhasar tumpukan min iki. Tegese, ing cilik saka unsur antrian nomer, unsur pisanan saka antrian bakal minimal nomer iki. Yen sampeyan mbusak oyod, sing paling cilik sabanjure dadi oyod.

Ayo dadi conto kita.

Langkah 1. Kita sijine '5' menyang antrian prioritas. Iku dadi ROOT. Langkah 2. Kita nambah '4' menyang antrian prioritas. 4 <5, dadi unsur anyar kudu luwih dhuwur tinimbang sing lawas. Sing 4 dadi oyod, 5 dadi anak kiwa. Saiki struktur data ing Jawa yaiku [4, 5] Langkah 3. Kita nambah '3'. Sauntara iku dadi anak tengen saka ROOT (4). Nanging, 3 < 4, supaya kita kudu ngangkat munggah. Exchange 3 lan 4. Saiki kita duwe struktur kayata [3, 5, 4] Langkah 4. Kita nambah '2'. Dadi anak kiwa 5. 2<5, mula padha tukaran. 2 dadi anak kiwa 3, 2 < 3, dadi siji proses tukar maneh. Saiki kita duwe struktur [2,3,4,5] Langkah 5.Kita nambah '1'. Asalé saka anak tengen 3 kanggo anak kiwa 2, lan banjur menyang ROOT. Struktur data asil: [1,2,4,5,3] Proses penghapusan diwiwiti saka oyod, lan nyebabake prosedur mbalikke. Dadi, pisanan kita duwe 1 minangka root, banjur 2, 3, 4 lan pungkasan 5. Mulane nggunakake njabut operasi jajak pendapat ()

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

kita wis "diurutake" ing output pangertèn linier:

1
2
3
4
5

Dadi antrian prioritas bisa efektif kanggo sawetara operasi. Butuh O (log N) wektu kanggo masang lan mbusak saben unsur, lan sampeyan bisa njaluk unsur minimal ing O (1). Punika conto lengkap:

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

Penting kanggo mangerteni yen antrian prioritas adhedhasar tumpukan binar, supaya ora nyimpen unsur ing urutan sing diurutake kanthi linier. Saben cara saka oyod menyang rwaning diurutake, nanging cara sing beda saka oyod ora. Tegese sampeyan bisa entuk unsur minimal saka antrian kanthi cepet.

Apa sampeyan kudu ngerti babagan antrian prioritas. dhaftar Brief

• Antrian Prioritas ora ngidini obyek NULL.
• Sampeyan bisa nambah mung obyek sing bisa dibandhingake menyang PriorityQueue.
• Antrian prioritas dibangun minangka tumpukan min, sejenis wit binar. Unsur minimal yaiku ROOT. Objek saka antrian prioritas diurutake kanthi standar kanthi urutan alami.
• Sampeyan bisa nggunakake Comparator yen sampeyan butuh pesenan khusus.
• PriorityQueue ora aman, dadi luwih becik sampeyan nggunakake PriorityBlockingQueue kanggo nggarap lingkungan bebarengan.
• PriorityQueue nyedhiyakake wektu O(log(n)) kanggo cara nambah lan polling lan O(1) kanggo entuk unsur minimal.