Burada Java Kuyruğu arayüzünü tartışacağız. Queue veri yapısının ne olduğunu, Java'da nasıl temsil edildiğini, tüm kuyruklar için hangi yöntemlerin en önemli olduğunu öğreneceksiniz . Ayrıca, Sıranın hangi uygulamaları Java dilindedir. Ardından en önemli uygulamaları yakından inceliyor ve örneklerle öğreniyoruz.
Kuyruk veri yapısı
Kuyruk, belirli işlem gerçekleştirme sırasına sahip doğrusal bir soyut veri yapısıdır - İlk Giren İlk Çıkar (FIFO). Bu, yalnızca yapının sonuna bir öğe ekleyebileceğiniz (veya kuyruğa koyabileceğiniz, kuyruğa koyabileceğiniz) ve bir öğeyi yalnızca başından alabileceğiniz (kuyruğa alma veya sıradan çıkarma) anlamına gelir. Kuyruk veri yapısını çok kolay hayal edebilirsiniz. Gerçek hayatta bir kuyruk veya müşteri kuyruğu gibi görünüyor. İlk gelen müşteriye de ilk hizmet verilecek. McDonalds'ta veya başka bir yerde sırada dört kişi varsa, sıraya ilk giren mağazaya ilk giren olur. Yeni müşteri gelirse hamburger almak için 5. sırada olacak. Yani bir sıra ile çalışırken en sona yeni elemanlar eklenir ve eğer bir eleman almak istenirse baştan alınır. Klasik kuyruk veri yapısı çalışmasının ana prensibi budur.
Java'da sıra
Java'da kuyruk bir arayüzdür. Oracle belgelerine göre, Queue arabirimi 2 süper arabirime, sıradan devralan 4 farklı arabirime ve son derece etkileyici bir sınıf listesine sahiptir.
Bu ne anlama geliyor? Her şeyden önce Java Kuyruğu, Koleksiyon Çerçevesinin bir parçasıdır ve Koleksiyon arayüzünü uygular. Bu nedenle, ekleme, silme vb. gibi Koleksiyon arayüzünün tüm yöntemlerini destekler. Queue, bir nesnenin "for-each loop" ifadesinin hedefi olmasına izin veren Yinelenebilir arabirimi uygular.
Kuyruk Yöntemleri Java
Kuyruk, bir dizi yöntem bildirir. Arayüzün yöntemleri olarak, Queue'yu uygulayan tüm sınıflarda temsil edilmelidirler. En önemli Kuyruk Yöntemleri, Java:
Boolean Offer() – mümkünse kuyruğa yeni bir öğe ekler
Boolean add(E e) – mümkünse kuyruğa yeni bir eleman ekler. Başarı durumunda true döndürür ve boşluk yoksa bir IllegalStateException atar.
Object poll() – bir öğeyi alır ve kafasından kaldırır. Kuyruk boşsa null döndürür.
Object remove() – sıranın başından bir öğeyi alır ve kaldırır.
Object peek() – sıranın başından bir öğeyi alır, ancak kaldırmaz. Kuyruk boşsa null döndürür.
Object element() – sıranın başından bir öğeyi alır, ancak kaldırmaz.
Java Kuyruğunun alt arayüzleri
Kuyruk arabirimi 4 alt arabirim tarafından devralınır – BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . Bunları 3 gruba ayırabilirsiniz: Deques, Blocking Queues ve BlockingDeque ilk ikisine ait olan Transfer Kuyrukları. Gelin bu gruplara bir göz atalım.
Deques
Deque, Çift Uçlu Kuyruk anlamına gelir ve bir kuyruk (ilk giren ilk çıkar/FIFO) olarak verilerin kuyruğundan veya yığın (son giren) adı verilen başka bir popüler veri yapısı olarak kafadan ekleme veya çıkarma işlemini destekler. ilk çıkar/LIFO). Deque Arayüzünü uygulayan sınıflar: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.
Kuyrukları Engelleme
Engelleme sırası, bir iş parçacığını iki durumda engelleyen bir sıradır:
iş parçacığı boş bir sıradan öğeleri almaya çalışıyor
iş parçacığı öğeleri tam kuyruğa koymaya çalışıyor
Bir iş parçacığı boş bir sıradan öğeler almaya çalıştığında, başka bir iş parçacığı öğeleri kuyruğa koyana kadar bekler. Benzer şekilde, bir iş parçacığı öğeleri tam bir kuyruğa koymaya çalıştığında, öğeler için boş alan elde etmek üzere başka bir iş parçacığının öğeleri sıradan almasını bekler. Elbette, "tam sıra" kavramı, sıranın genellikle yapıcıda belirtilen sınırlı bir boyuta sahip olduğunu ima eder. Standart Engelleme Kuyrukları arasında LinkedBlockingQueue, SynchronousQueue ve ArrayBlockingQueue bulunur. BlockingQueue arabiriminin uygulama sınıfları : ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. EngellemeDequeBlockingQueue için bir alt arayüzdür. BlockingQueue gibi BlockingDeque, bir engelleme sırasıdır, ancak çift yönlüdür. Böylece Deque arayüzünün özelliklerini devralır. Çok iş parçacıklı yürütmeye yöneliktir, sıfır öğeye izin vermez ve kapasite sınırlandırılabilir. BlockingDeque arabiriminin uygulamaları, sıra boşsa öğe alma ve doluysa kuyruğa öğe ekleme işlemini engeller.
Aktarım Kuyrukları
TransferQueue arabirimi, BlockingQueue arabirimini genişletir. Ancak, sıra boşsa (okuma) veya sıra doluysa (yazma) iş parçacıklarının bloke edilebildiği BlockingQueue arabirim kuyruklarının uygulanmasından farklı olarak, TransferQueue arabirim kuyrukları, başka bir akış öğeyi alana kadar yazma akışını engeller. Bunun için bir aktarım yöntemi kullanın. Başka bir deyişle, BlockingQueue uygulaması Üretici tarafından oluşturulan öğenin kuyrukta olması gerektiğini garanti ederken, TransferQueue uygulaması Üretici öğesinin Tüketici tarafından "alındığını" garanti eder. TransferQueue arayüzünün yalnızca bir resmi Java uygulaması vardır - LinkedTransferQueue.
Java Kuyruk Uygulamaları
Kuyruk arayüzünü uygulayan birçok sınıf vardır:
AbstractQueue, Queue Java 8 belgelerine göre, bu soyut sınıf, bazı Queue işlemlerinin temel uygulamalarını sağlar. Boş öğelere izin vermez. Sırasıyla klasik Queue , poll ve peek'e dayalı 3 yöntem daha vardır, add, remove ve element . Ancak, yanlış veya boş dönüşlerle başarısızlığı belirtmek yerine istisnalar atarlar.
ArrayBlockingQueue — bir dizi tarafından desteklenen sabit boyutlu bir FIFO engelleme sırası
ArrayDeque — Deque arayüzünün yeniden boyutlandırılabilir dizi uygulaması
ConcurrentLinkedDeque — bağlantılı düğümlere dayalı sınırsız bir eşzamanlı deque.
ConcurrentLinkedQueue — bağlantılı düğümlere dayalı, sınırsız, iş parçacığı açısından güvenli bir sıra.
DelayQueue — bir yığın tarafından desteklenen zamana dayalı bir zamanlama kuyruğu
LinkedBlockingQueue — bağlantılı düğümler tarafından desteklenen, isteğe bağlı olarak sınırlandırılmış bir FIFO engelleme kuyruğu
LinkedList — List ve Deque arayüzlerinin çift bağlantılı liste uygulaması. Tüm isteğe bağlı liste işlemlerini uygular ve tüm öğelere izin verir (null dahil)
LinkedTransferQueue — bağlantılı düğümleri temel alan sınırsız bir TransferQueue
PriorityBlockingQueue — bir yığın tarafından desteklenen sınırsız bir engelleme önceliği sırası
PriorityQueue — yığın veri yapısına dayalı bir öncelik kuyruğu
SynchronousQueue — her ekleme işleminin başka bir iş parçacığı tarafından karşılık gelen bir kaldırma işlemini beklemesi gereken bir engelleme sırası ve bunun tersi de geçerlidir.
En popüler uygulamalar LinkedList, ArrayBlockingQueue ve PriorityQueue'dur. Onlara bakalım ve daha iyi anlamak için bazı örnekler yapalım.
Bağlantılı liste
Java'daki Class LinkedList, List ve Deque arayüzlerini uygular. Bu nedenle, her iki taraftan öğe eklemeyi ve kaldırmayı destekleyen, iki yönlü bir sıra olan List ve Deque'nin bir birleşimidir. Java'da LinkedList çift bağlantılı bir Listedir: List'in her öğesi Node'u çağırır ve bir nesne ile önceki ve sonraki iki komşu nesneye referanslar içerir. LinkedList'in bellek kullanımı açısından pek etkili olmadığını söyleyebilirsiniz. Bu doğrudur, ancak bu veri yapısı, ekleme ve silme işlemlerinin performansı durumunda yararlı olabilir. Ancak, yalnızca onlar için yineleyiciler kullanırsanız gerçekleşir (bu durumda, sabit zamanda gerçekleşir). İndeks bazında erişim işlemleri, sonun başından (hangisi daha yakınsa) istenilen elemana kadar arama yapılarak gerçekleştirilir. Ancak, öğeler arasında referansları depolamak için ek maliyetleri unutmayın. LinkedList, Java'daki en popüler kuyruk uygulamasıdır. List ve Deque'nin de bir uygulamasıdır ve null dahil herhangi bir nesneden oluşan çift yönlü bir sıra oluşturmamıza izin verir. LinkedList bir öğeler koleksiyonudur.
LinkedList() parametresiz boş bir liste oluşturmak için kullanılır. LinkedList(Collection<? extensions E> c), belirtilen koleksiyonun öğelerini, koleksiyonun yineleyicisi tarafından döndürülme sırasına göre içeren bir liste oluşturmak içindir.
Ana LinkedList Yöntemleri:
add(E element) Belirtilen elemanı bu listenin sonuna ekler;
add(int dizini, E öğesi) Öğeyi belirtilen konum dizinine ekler;
get(int index) Bu listede belirtilen konumdaki elemanı döndürür;
remove(Object o) ?o öğesinin ilk geçtiği yer varsa listeden kaldırır.
remove() Listenin ilk öğesini alır ve kaldırır.
addFirst(), addLast() bir listenin başına/sonuna bir öğe ekler
clear() listeden tüm öğeleri kaldırır
include(Object o), liste o öğesini içeriyorsa true değerini döndürür.
indexOf(Object o), o öğesinin ilk geçtiği dizinin dizinini veya listede yoksa -1'i döndürür.
set(int dizini, E öğesi), dizin konumundaki öğeyi öğeyle değiştirir
size() Listedeki öğelerin miktarını döndürür.
toArray(), ilk öğeden son öğeye kadar tüm liste öğelerini içeren bir dizi döndürür.
yığından bir öğe çıkaran pop() (liste tarafından temsil edilir)
push(E e) bir öğeyi yığına iter (bu liste tarafından temsil edilir)
Java Kuyruğu Örneği — LinkedList (öğeleri farklı şekillerde koymak ve kaldırmak)
import java.util.*;
public class LinkedListTest {
public static void main(String args[]){
LinkedList<Integer> myLinkedList= new LinkedList<Integer>();
myLinkedList.add(1);
myLinkedList.add(2);
myLinkedList.add(4);
System.out.println("three added elements: " + myLinkedList);
//put one element into the head, not to the tail:
myLinkedList.push(5);
System.out.println("The new element last in will be the first: " + myLinkedList);
//add new element at the specified position:
myLinkedList.add(4,3);
//put one element into the head, not to the tail (same as push):
myLinkedList.addFirst(6);
System.out.println(myLinkedList);
//now remove element no 2 (it is 1):
myLinkedList.remove(2);
System.out.println(myLinkedList);
//now remove the head of the list
myLinkedList.pop();
System.out.println(myLinkedList);
//remove with the other method
myLinkedList.remove();
System.out.println(myLinkedList);
//and with one more
myLinkedList.poll();
System.out.println(myLinkedList);
}
}
Öncelik Sırası
PriorityQueue, FIFO genel anlamında tam olarak sıra değildir. Öncelik sırasının öğeleri, doğal sıralamalarına göre veya hangi yapıcının kullanıldığına bağlı olarak, sıra oluşturma sırasında sağlanan bir Karşılaştırıcı tarafından sıralanır. Ancak liste (büyükten küçüğe veya tam tersi) gibi lineer bir yapıda olabilecek bir sıralama değildir. Öncelik min yığınına dayalı bir öncelik kuyruğu. Yığın, ikili ağaca dayalı bir veri yapısıdır. Her ebeveynin önceliği, çocuklarının önceliklerinden daha büyüktür. Her ebeveynin ikiden fazla çocuğu yoksa ve seviyelerin doldurulması yukarıdan aşağıya (aynı seviyeden - soldan sağa) gidiyorsa, bir ağaca tam ikili denir. İkili yığın, her yeni öğe eklendiğinde veya çıkarıldığında kendisini yeniden düzenler. Min-yığın durumunda, en küçük öğe, yerleştirme sırasına bakılmaksızın köke gider. Öncelik kuyruğu bu min-yığına dayalıdır, dolayısıyla bir PriorityQueue tamsayılarımız varsa, bunun ilk öğesi bu sayıların en küçüğü olacaktır. Kökü silerseniz, bir sonraki en küçük kök olur.
Ana PriorityQueue Yöntemleri:
boolean add(object), belirtilen öğeyi öncelik sırasına ekler. Başarı durumunda true döndürür. Kuyruk doluysa, yöntem bir istisna atar.
boolean Offer(object) belirtilen öğeyi bu öncelik sırasına ekler. Kuyruk doluysa, yöntem false döndürür.
boolean remove(object), eğer varsa, belirtilen öğenin tek bir örneğini bu sıradan kaldırır.
Object poll() bu kuyruğun başını alır ve kaldırır. Kuyruk boşsa null döndürür.
void clear(), öncelik kuyruğundaki tüm öğeleri kaldırır.
Object element(), bu kuyruğun başını kaldırmadan alır. Kuyruk boşsa NoSuchElementException atar.
Object peek(), kuyruğun başını kaldırmadan alır. Kuyruk boşsa null döndürür.
boolean include(Object o), sıra o öğesini içeriyorsa true değerini döndürür.
int size(), bu kuyruktaki öğelerin sayısını döndürür.
PriorityQueue Örneği
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
Öncelik sıralarının ikili yığınlara dayandığını, dolayısıyla öğeleri doğrusal sıralı düzende tutmadıklarını anlamak önemlidir. Kökten yaprağa kadar her yol sıralıdır ama kökten farklı yollar sıralanmamıştır. Bu, kuyruğun minimum öğesini çok hızlı bir şekilde alabileceğiniz anlamına gelir. Her seferinde kafayı silerseniz sıralanmış bir yapı yazdırırsınız.
Dizi Engelleme Sırası
ArrayBlockingQueue'nun dahili veri yapısıöğeleri depolamak için dairesel bir diziye dayanır. Kuyruğun kuyruğuna yeni öğelerin eklenmesi ve çıkarma işlemlerinin kuyruğun başından bir öğe döndürmesi durumunda bu tipik bir sıradır (FIFO). Oluşturulduktan sonra kuyruk kapasitesi değiştirilemez. Dolu bir kuyruğa öğe ekleme (koyma) girişimleri akışın engellenmesine yol açar; boş bir sıradan bir öğe almaya çalışmak da iş parçacığını engeller. Daha önce de söylediğimiz gibi, bu dizi daireseldir. Bu, dizinin ilk ve son öğelerinin mantıksal olarak bitişik olarak ele alındığı anlamına gelir. Sıra, elemento'yu kuyruğa her koyduğunuzda veya sıradan çıkardığınızda baş ve kuyruk elemanlarının indekslerini ilerletir. Bazı dizinler dizinin son öğesini ilerletirse, 0'dan yeniden başlar. kafanın çıkarılması durumunda (normal dizide olduğu gibi) kuyruğun tüm öğeleri kaydırması gerekmez. Ancak, ortadan bir öğenin kaldırılması durumunda (Iterator.remove kullanılarak), öğeler kaydırılır. ArrayBlockingQueue, üreticilerin (ekleme öğeleri) ve tüketicilerin (çıkarma öğeleri) bekleyen akışlarının işini sıralamak için yapıcıda adil parametresiyle ek bir adillik ilkesini destekler . Varsayılan olarak, sipariş garanti edilmez. Ancak kuyruk "fair == true" ile oluşturulursa, ArrayBlockingQueue sınıfının uygulanması FIFO sırasında iş parçacığı erişimi sağlar. Eşitlik tipik olarak bant genişliğini azaltır ama aynı zamanda oynaklığı da azaltır ve kaynakların tükenmesini önler.
ArrayBlockingQueue Sınıf oluşturucuları
ArrayBlockingQueue (int kapasite), varsayılan erişim ilkesiyle sabit kapasitede bir sıra oluşturur.
ArrayBlockingQueue (int kapasite, boole adil), sabit kapasiteli ve belirli bir erişim ilkesine sahip bir sıra oluşturur.
ArrayBlockingQueue (int kapasite, boolean adil, Koleksiyon <? E'yi genişletir> c), erişim ilkesi tarafından belirtilen sabit kapasiteli bir kuyruk oluşturur ve kuyruğa öğeler içerir.
Burada BlockingQueueExample örneğimiz var. ArrayBlockingQueue'nun bir eleman kapasiteli ve adil bir bayrakla kuyruğunu oluşturuyoruz. İki iş parçacığı başlatılır. Bunlardan ilki olan Üretici iş parçacığı, put yöntemini kullanarak mesajlar dizisinden gelen mesajları kuyruğa alır. İkincisi, Tüketici, iş parçacığı, alma yöntemini kullanarak kuyruktaki öğeleri okur ve bunları konsolda görüntüler. Öğelerin sırası, sıra için doğal olandır.
import java.util.concurrent.*;
public class ArrayBlockingQueueExample {
private BlockingQueue<Integer> blockingQueue;
private final Integer[] myArray = {1,2,3,4,5};
public ArrayBlockingQueueExample ()
{ blockingQueue = new ArrayBlockingQueue<Integer>(1, true);
(new Thread(new Producer())).start();
(new Thread(new Consumer())).start();
}
class Producer implements Runnable
{
public void run() {
try {
int counter = 0;
for (int i=0; i < myArray.length; i++) {
blockingQueue.put(myArray[i]);
if (counter++ < 2)
Thread.sleep(3000);
} blockingQueue.put(-1);
}
catch (InterruptedException e) {
System.err.println(e.getMessage());
}
}
}
class Consumer implements Runnable
{
public void run() {
try {
Integer message = 0;
while (!((message = blockingQueue.take()).equals(-1)))
System.out.println(message);
} catch (InterruptedException e) {
System.err.println(e.getMessage());
}
}
}
public static void main(String[] args) {
new ArrayBlockingQueueExample();
}
}
Çıktı, doğal sıradaki sıradır; ilk iki öğe gecikmeli olarak görünür. Öğrendiklerinizi pekiştirmek için Java Kursumuzdan bir video dersi izlemenizi öneririz.
Sonuçlar
Sıra, sıranın sonuna eleman eklemek ve sıranın başından kaldırmak için kullanılır. FIFO konseptini takip eder.
Java Kuyruğu, Koleksiyon Çerçevesinin bir parçasıdır ve Koleksiyon arayüzünü uygular. Bu nedenle, ekleme, silme vb. gibi Koleksiyon arayüzünün tüm yöntemlerini destekler.
Queue'nin en sık kullanılan uygulamaları LinkedList, ArrayBlockingQueue ve PriorityQueue'dur.
Öncelik sırasının öğeleri, doğal sıralamalarına göre veya hangi yapıcının kullanıldığına bağlı olarak, sıra oluşturma sırasında sağlanan bir Karşılaştırıcı tarafından sıralanır.
BlockingQueues üzerinde herhangi bir boş işlem gerçekleştirilirse, NullPointerException atılır.
Yani bir sıra ile çalışırken en sona yeni elemanlar eklenir ve eğer bir eleman almak istenirse baştan alınır. Klasik kuyruk veri yapısı çalışmasının ana prensibi budur.
LinkedList'in bellek kullanımı açısından pek etkili olmadığını söyleyebilirsiniz. Bu doğrudur, ancak bu veri yapısı, ekleme ve silme işlemlerinin performansı durumunda yararlı olabilir. Ancak, yalnızca onlar için yineleyiciler kullanırsanız gerçekleşir (bu durumda, sabit zamanda gerçekleşir). İndeks bazında erişim işlemleri, sonun başından (hangisi daha yakınsa) istenilen elemana kadar arama yapılarak gerçekleştirilir. Ancak, öğeler arasında referansları depolamak için ek maliyetleri unutmayın. LinkedList, Java'daki en popüler kuyruk uygulamasıdır. List ve Deque'nin de bir uygulamasıdır ve null dahil herhangi bir nesneden oluşan çift yönlü bir sıra oluşturmamıza izin verir. LinkedList bir öğeler koleksiyonudur.
GO TO FULL VERSION