Queue

Ko'pchilik uchun "navbat" so'zi juda yoqimli assotsiatsiyalar uyg'otmasligi mumkin. Lekin bugun biz Java dagi boshqa navbatlar haqida gaplashamiz. Java da navbat deb, interfeysni Queue meros qilib oladigan narsalarga aytiladi, bu esa o'z navbatida Collection kengaytiradi. Bu degani, navbatlar bilan kollektsiyalar kabi ishlash mumkin.

Java dagi navbatlar ikki prinsipda ishlaydi: FIFO va LIFO.

FIFO — First In First Out, oddiy navbat prinsipi (albatta, agar kimdir "faqat so'roq" qilmasa), bu yerda birinchi element navbatga tushadi va birinchi chiqadi.

LIFO — Last In First Out, bu stekning prinsipi, bu yerda oxirgi navbatga qo'shilgan element birinchi chiqadi. Masalan, kartochka to'plami bilan o'yin: oxiridan birma-bir kartalarni olasan.

Java da Queue ierarxiyasini quyidagi ko'rinishda ko'rish mumkin:

Bu yerda Queuening 3 ta realizatsiya sinf ekanligini ko'rish mumkin: LinkedList, ArrayDeque va PriorityQueue. LinkedList va ArrayDeque to'g'ridan-to'g'ri Queue dan emas, balki Dequedan meros qilib oladi.

Deque — Java ning 6-versiyasida kiritilgan interfeys. Bu navbatlar uchun foydali metodlar qatorini o'z ichiga oladi va navbatlar ikki tomonlama navbat sifatida ishlashni imkonini beradi. Ya'ni FIFO yoki LIFO prinsipida ishlash imkoniyatini beradi.

Dequening ikki merosxo'rlaridan biri ArrayDeque. U ikki tomonlama navbat tuzilmasini qo'llab-quvvatlaydi, bu esa elementlarni ikki tomondan qo'shish va o'chirish imkonini beradi. Shuningdek, u — dinamik massiv bo'lib, o'z hajmini avtomatik ravishda oshirish imkoniyatiga ega.

Boshqa bir sinf esa PriorityQueue, Queuening to'g'ridan-to'g'ri merosxo'ri: uning ishlash prinsipi Dequeue ning merosxo'rlari bilan farq qiladi.

PriorityQueue — bu oldindan tartiblangan navbat bo'lib, u elementlarni tabiiy tartibga ko'ra joylashtiradi. Bu yerda Comparable va Comparator yordamida tartiblanadi. Bu prinsip TreeSet yoki TreeMap bilan bir xil — interfeysga muvofiq bo'lgan sinflar Comparable va o'z tartibiga ega.

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

// Qo'shish
priorityQueue.add("Andrew");
priorityQueue.add("John");
priorityQueue.add("Rob");

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

Ushbu misolni konsolda ishga tushirsang, quyidagini olasan:

Chunki biz navbatlar bilan ishlayapmiz, oddiy kollektsiyalar bilan emas, biz ro'yxatdan elementni o'chirishimiz kerak. Ushbu konstruktsiyadan foydalanamiz:

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

Deque interfeysi Queue metodlarini meros qilib oladi va o'zining bir qator qiziqarli metodlarini qo'shadi:

Keling, endi ulardan bir nechtasini amaliyotda ko'rib chiqamiz.

Birinchi navbatda element qo'shamiz:

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

        deque.add("Apple"); // Apple elementini navbat oxiriga qo'shadi
        deque.addFirst("Orange"); // Orange elementini navbat boshiga qo'shadi
        deque.addLast("Pineapple"); // Pineapple elementini navbat oxiriga qo'shadi
  
        System.out.println(deque);
    

Endi navbatdan qiymatlarni olamiz:

	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());
                          
    }
    

Bu kod konsolda birinchi va oxirgi navbat elementini chiqaradi.

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

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

System.out.println(deque.pop()); // navbatdagi yuqori elementni chiqaradi va o'chiradi
System.out.println(deque.poll()); // navbatdagi yuqori elementni chiqaradi va o'chiradi

System.out.println(deque);
    

Ushbu kodni ishga tushirsang, quyidagini olasan:

pop() va poll() metodlari o'rtasidagi farq: pop() bo'sh ro'yxat uchun NoSuchElementException istisnosini yaratadi, poll() esa null qaytaradi.

Endi pollFirst() va pollLast() metodlarini ko'rib chiqamiz.

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

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

System.out.println(deque.pollFirst()); // birinchi navbat elementini chiqaradi va o'chiradi
System.out.println(deque.pollLast()); // oxirgi navbat elementini chiqaradi va o'chiradi.
System.out.println(deque);
    

Har ikkala metod qiymatni navbatdan chiqaradi va o'chiradi.

peekFirst() va peekLast() metodlarining foydalanish misoli:

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

Har ikkala metod birinchi/oxirgi navbat elementini qaytaradi va uni o'chirmaydi. Agar navbat bo'sh bo'lsa, null qaytariladi.

Umuman olganda, bugun biz Java da navbatlar bilan ishlashni o'rgandik. Endi ularni amaliyotda qanday ishlatishni bilasan.