Kuyruk II: dairesel indeks hesabı, deque, öncelik kuyruğu

Geçen hafta kuyruğun iki temel gerçeklemesini yazdık. Bu hafta üç genişleme var. Önce dairesel dizinin count tutmayan versiyonunu ve indeks formüllerini çalışıyoruz, çünkü sınavda “front = 4, rear = 1, kaç eleman var?” gibi saf formül soruları çıkıyor. Sonra iki uçtan da işlem yapılabilen deque’yi, ardından elemanları öncelik sırasına göre çıkaran öncelik kuyruğunu (priority queue) görüyoruz. Son olarak kuyruğun asıl kullanım alanı olan simülasyonları izliyoruz.

Altın kurallar:

1. Dairesel indekste her şey % cap. Geriye giderken önce + cap.
2. count yoksa bir hücre boş kalır. Boş: front == rear. Dolu: (rear + 1) % cap == front.
3. Deque iki uçlu kuyruktur. Hem yığın hem kuyruk gibi kullanılabilir.
4. Öncelik kuyruğu FIFO değildir. Java’da en küçük önce çıkar.

Dairesel kuyruk: count olmadan

Geçen hafta front == rear durumunun hem boş hem dolu anlamına gelebildiğini gördük ve bir count alanı ekledik. Diğer yaygın çözüm: kuyruğun hiçbir zaman tamamen dolmasına izin vermemek. Bir hücre hep boş kalır, böylece:

rear yine bir sonraki boş yerdir. Kapasite 5 ile:

SlotQueue s = new SlotQueue(5);
for (int i = 1; i <= 4; i++) s.enqueue(i * 10);
System.out.println(s.raw() + " full=" + s.isFull());
s.dequeue(); s.dequeue(); s.enqueue(50); s.enqueue(60);
System.out.println(s.raw() + " full=" + s.isFull());

[10, 20, 30, 40, 0] front=0 rear=4 size=4 full=true
[60, 20, 30, 40, 50] front=2 rear=1 size=4 full=true

İlk satırda dizide hâlâ bir boş hücre var ama kuyruk dolu: (4 + 1) % 5 = 0 = front. İkinci satırda 50 indeks 4’e, 60 indeks 0’a yazıldı; rear 1, front 2. Boyut (1 − 2 + 5) % 5 = 4.

TUZAK · Neden + cap? rear sarıp front’un gerisine düştüğünde rear - front negatif olur. Java’da % negatif sonucu negatif bırakır: (1 − 4) % 6 = −3. Önce cap ekleyince (1 − 4 + 6) % 6 = 3 olur, doğru boyut.

Formül soruları için çözüm kalıbı

cap = 6, front = 4, rear = 1
boyut    = (1 - 4 + 6) % 6 = 3
elemanlar: indeks 4, 5, 0
dolu mu? (1 + 1) % 6 = 2 ≠ 4 → hayır
sonraki enqueue indeks 1'e yazar, rear 2 olur

Deque (double-ended queue)

İki ucundan da ekleme ve çıkarma yapılabilen kuyruk. “Deck” diye okunur.

Sadece addLast + pollFirst kullanırsan kuyruk, sadece addFirst + pollFirst kullanırsan yığın olur. Java’nın ArrayDeque sınıfı tam olarak budur: dairesel dizi üzerinde bir deque.

Deque<Integer> d = new ArrayDeque<>();
d.addFirst(1); d.addLast(2); d.addFirst(3); d.addLast(4);
System.out.println(d);
System.out.println(d.pollLast() + " " + d.pollFirst());
d.offerFirst(9);
System.out.println(d + " peekLast=" + d.peekLast());

[3, 1, 2, 4]
4 3
[9, 1, 2] peekLast=2

Deque’yi dairesel diziyle yazmak

front ve count tutulur. Sona ekleme (front + count) % cap hücresine yazar. Başa ekleme front’u bir geri alır:

void addFirst(int x) {
    front = (front - 1 + data.length) % data.length;
    data[front] = x;
    count++;
}

void addLast(int x) {
    data[(front + count) % data.length] = x;
    count++;
}

int removeLast() {
    int idx = (front + count - 1) % data.length;
    count--;
    return data[idx];
}

Kapasite 6 ile addLast(1), addLast(2), addFirst(3), addFirst(4):

[1, 2, 0, 0, 4, 3] front=4 count=4

front 0’dan geri sarınca 5’e (3 yazıldı), sonra 4’e (4 yazıldı). Mantıksal sıra front’tan: 4 3 1 2.

Öncelik kuyruğu (priority queue)

Hastane acil servisi gibi: gelme sırasına değil, aciliyete göre çağrılırsın. Her elemanın bir önceliği vardır; remove her zaman en yüksek öncelikli elemanı verir. Java’da “en yüksek öncelik” varsayılan olarak en küçük değer demektir.

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : new int[]{5, 1, 8, 3, 9, 2}) pq.add(x);
System.out.println("toString: " + pq);
System.out.println(pq.poll() + " " + pq.poll() + " " + pq.poll() + " size=" + pq.size());

toString: [1, 3, 2, 5, 9, 8]
1 2 3 size=3

toString çıktısı sıralı değil. PriorityQueue içeride bir heap tutar; garanti sadece en öndekinin en küçük olmasıdır. En büyük önce çıksın istiyorsan bir Comparator ver:

PriorityQueue<Integer> mx = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<String> byLen = new PriorityQueue<>((a, b) -> a.length() - b.length());

Gerçekleme seçenekleri

Bu derste ilk ikisini yazabilmen yeterli. Sıralı liste versiyonu 3. haftadaki insertSorted + removeFirst’ten ibarettir. Heap bir sonraki dersin (SEN2212) konusu.

Kuyrukla simülasyon

Kuyruğun asıl gücü “sırası gelen işlenir, işi bitmeyen sona geçer” senaryolarıdır.

Round-robin zamanlama

İşletim sistemi işlemciyi işlere sırayla, her birine sabit bir süre dilimi (quantum) vererek dağıtır. Süre dilimi 2, işler A (5 birim), B (2), C (4):

while (!names.isEmpty()) {
    String p = names.remove();
    int run = Math.min(2, left.get(p));
    time += run;
    left.put(p, left.get(p) - run);
    if (left.get(p) > 0) names.add(p);   // bitmediyse sona
}

A[0-2] B[2-4] (B done at 4) C[4-6] A[6-8] C[8-10] (C done at 10) A[10-11] (A done at 11)

Hot potato (sıcak patates)

Herkes çember halinde. Patates k kez el değiştirir, elinde kalan oyundan çıkar. Kuyrukla: k kez add(remove()), sonra bir remove(). 3. haftadaki Josephus probleminin kuyruk versiyonu.

out: Deniz Cem Ece Bora | winner: Ali

Kuyruğu bozmadan gezmek

Kuyrukta indeksle erişim yok. İçeriği değiştirmeden toplamı almak için size kez döndür:

static int sumQueue(Queue<Integer> q) {
    int sum = 0, n = q.size();
    for (int i = 0; i < n; i++) { int x = q.remove(); sum += x; q.add(x); }
    return sum;
}

[3, 6, 9, 12] için 30 döner ve kuyruk aynı sırada kalır. Döngü sınırını önceden n değişkenine almak önemli; i < q.size() de bu örnekte çalışır çünkü boyut değişmiyor, ama eleman çıkaran varyasyonlarda yanıltır.

Sık yapılan hatalar

Deque<Integer> d = new ArrayDeque<>();
d.addFirst(1); d.addLast(2); d.addFirst(3); d.addLast(4);
System.out.println(d);
System.out.println(d.pollLast() + " " + d.pollFirst());
d.offerFirst(9);
System.out.println(d + " peekLast=" + d.peekLast());

static boolean isPalindrome(String s) {
    Deque<Character> d = new ArrayDeque<>();
    for (char c : s.toCharArray()) d.addLast(c);
    while (d.size() > 1) {
        if (d.pollFirst() != d.pollLast()) return false;
    }
    return true;
}

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : new int[]{5, 1, 8, 3, 9, 2}) pq.add(x);
System.out.println(pq.poll() + " " + pq.poll() + " " + pq.poll() + " size=" + pq.size());

PriorityQueue<Integer> mx = new PriorityQueue<>(Comparator.reverseOrder());
mx.add(4); mx.add(10); mx.add(7);
System.out.println(mx.peek());
mx.poll(); mx.add(6);
while (!mx.isEmpty()) System.out.print(mx.poll() + " ");

zaman   çalışan   kalan sonrası   kuyruk
0-2     A         A:3             B C A
2-4     B         B:0 bitti (4)   C A
4-6     C         C:2             A C
6-8     A         A:1             C A
8-10    C         C:0 bitti (10)  A
10-11   A         A:0 bitti (11)