Kuyruk (queue): dairesel dizi ve bağlı liste ile

Kuyruk (queue) markette kasa sırasıdır: sona girersin, öndeki çıkar. İlk gelen ilk hizmeti alır: FIFO (First In, First Out). Yazıcı kuyruğu, işletim sisteminin iş sırası, ağdaki paketler, oyunlardaki eşleşme sırası hep kuyruktur. Yığından tek farkı hangi uçtan çıkardığın, ama gerçeklemesi daha zahmetlidir: iki ucu da takip etmek gerekir. Sınavda dairesel dizinin ham hali (hangi hücrede ne var, front ve rear kaç) neredeyse her yıl sorulur.

Altın kurallar:

1. Arkadan ekle (enqueue), önden çıkar (dequeue).
2. Dizide eleman kaydırma. front ve rear indekslerini ilerlet, sona gelince % ile başa sar.
3. front == rear boş da olabilir dolu da. Ayırt etmek için count tut.
4. Bağlı kuyrukta son eleman çıkınca tail’i de null yap.

Kuyruk ADT

Yığınla karşılaştırma: 1, 2, 3 sırasıyla eklenip hepsi çıkarılırsa

stack: 3 2 1 | queue: 1 2 3

Neden basit dizi yetmez?

İlk akla gelen: önü hep indeks 0’da tut, çıkarınca herkesi bir sola kaydır. Doğru çalışır ama her dequeue n − 1 taşıma yapar. n elemanı sırayla çekmenin toplam maliyeti:

n=1000 shifts=499500
n=2000 shifts=1999000
n=4000 shifts=7998000

n iki katına çıkınca maliyet dört katına çıkıyor: O(n²) toplam, işlem başına O(n). Kaydırmak yerine front indeksini ilerletirsen bu sefer dizinin başı boşa gider ve rear sona dayanınca yer kalmamış gibi görünür. Çözüm: diziyi bir halka gibi düşün.

Dairesel dizi (circular buffer)

İndeks sona gelince 0’a döner: i = (i + 1) % capacity. Kapasite 4 için indeks sırası 0, 1, 2, 3, 0, 1, …

class ArrayQueue {
    private int[] data;
    private int front = 0;   // ilk elemanın indeksi
    private int rear = 0;    // bir sonraki boş yer
    private int count = 0;

    ArrayQueue(int capacity) { data = new int[capacity]; }

    boolean isEmpty() { return count == 0; }
    boolean isFull()  { return count == data.length; }

    void enqueue(int x) {
        if (isFull()) throw new RuntimeException("Queue overflow");
        data[rear] = x;
        rear = (rear + 1) % data.length;
        count++;
    }

    int dequeue() {
        if (isEmpty()) throw new RuntimeException("Queue underflow");
        int x = data[front];
        front = (front + 1) % data.length;
        count--;
        return x;
    }

    int peek() {
        if (isEmpty()) throw new RuntimeException("Queue underflow");
        return data[front];
    }
}

TUZAK · rear’ın anlamı. Bazı kitaplarda rear son elemanın indeksidir, bazılarında bir sonraki boş yerin. Bu sayfada bir sonraki boş yer. Sınavda sorudaki tanımı oku; formüller ona göre bir kayar.

Çözümlü iz (kapasite 4)

ArrayQueue q = new ArrayQueue(4);
q.enqueue(10); q.enqueue(20); q.enqueue(30);
System.out.println(q.dequeue());
System.out.println(q.raw());
q.enqueue(40); q.enqueue(50);
System.out.println(q.raw());
System.out.println(q.dequeue() + " " + q.dequeue());
System.out.println(q.raw());

10
[10, 20, 30, 0] front=1 rear=3 count=2
[50, 20, 30, 40] front=1 rear=1 count=4
20 30
[50, 20, 30, 40] front=3 rear=1 count=2

enqueue 10,20,30   [10,20,30, _]  front=0 rear=3 count=3
dequeue → 10       [10,20,30, _]  front=1 rear=3 count=2   (10 dizide kaldı)
enqueue 40         [10,20,30,40]  front=1 rear=0 count=3   (rear 3 → (3+1)%4 = 0)
enqueue 50         [50,20,30,40]  front=1 rear=1 count=4   (10'un üstüne yazıldı, dolu)
dequeue → 20       front=2
dequeue → 30       front=3, count=2; kuyruk mantıken: 40, 50

Son durumda kuyruk 40 ve 50’den oluşur. Önden okumak için front’tan başla ve count kadar (i + 1) % cap ile ilerle: indeks 3 (40), indeks 0 (50).

İPUCU · Ham dizi soruları. Sınavda “dizinin içeriği ne?” diye sorulduğunda çıkarılan elemanlar da dizide yazılı kalır. Sadece yeni bir enqueue onların üstüne yazar. Her adımda dört şeyi yaz: dizi, front, rear, count.

Bağlı liste ile kuyruk (linked queue)

Tek yönlü listede başa ekleme/baştan silme O(1), sona ekleme tail varsa O(1), sondan silme ise O(n). Bu yüzden: ekleme tail’de, çıkarma head’de.

class LinkedQueue {
    private static class Node { int data; Node next; Node(int d) { data = d; } }
    private Node head, tail;   // head = ön, tail = arka

    boolean isEmpty() { return head == null; }

    void enqueue(int x) {
        Node n = new Node(x);
        if (tail == null) head = tail = n;   // boş kuyruk
        else { tail.next = n; tail = n; }
    }

    int dequeue() {
        if (head == null) throw new RuntimeException("Queue underflow");
        int x = head.data;
        head = head.next;
        if (head == null) tail = null;       // kuyruk boşaldı
        return x;
    }
}

if (head == null) tail = null; satırı unutulursa: kuyruk boşaldıktan sonra tail eski düğümü göstermeye devam eder, sonraki enqueue o ölü düğümün arkasına bağlanır ve head null kalır. Kuyruk sonsuza kadar boş görünür.

Kuyruk kalıpları

Döndürme (rotate). q.enqueue(q.dequeue()) öndeki elemanı arkaya alır. k kez yaparsan kuyruk k adım döner: 10 20 30 40 50 iki kez → 30 40 50 10 20.

Ters çevirme. Kuyruğu bir yığına boşalt, sonra yığından geri kuyruğa doldur: 1 2 3 4 → 4 3 2 1.

Sırayla işleme. Öndeki iki elemanı çekip sonucu arkaya eklemek bir “turnuva” ya da birleştirme işlemi kurar. Eleman sayısı her turda bir azalır; tek eleman kalınca dur.

Sık yapılan hatalar

q.enqueue(5); q.enqueue(3);
System.out.print(q.dequeue() + " ");
q.enqueue(8); q.enqueue(1);
System.out.print(q.dequeue() + " ");
System.out.print(q.dequeue() + " ");
q.enqueue(6);
System.out.println(q.peek());

enqueue(1); enqueue(2); enqueue(3); enqueue(4);
dequeue(); dequeue(); dequeue();
enqueue(5); enqueue(6); enqueue(7);

for (int i = 1; i <= 4; i++) enqueue(i);
dequeue(); dequeue();
enqueue(5); enqueue(6);

void enqueue(int x) {
    if (count == data.length)
        throw new RuntimeException("Queue overflow");
    data[rear] = x;
    rear = (rear + 1) % data.length;   // sona gelince 0'a sar
    count++;
}

int dequeue() {
    if (count == 0)
        throw new RuntimeException("Queue underflow");
    int x = data[front];
    front = (front + 1) % data.length;
    count--;
    return x;
}

int dequeue() {
    if (head == null)
        throw new RuntimeException("Queue underflow");
    int x = head.data;
    head = head.next;
    if (head == null)   // son eleman çıktı
        tail = null;
    return x;
}

void enqueue(int x) {
    Node n = new Node(x);
    if (tail == null) head = tail = n;
    else { tail.next = n; tail = n; }
}
int dequeue() { int x = head.data; head = head.next; return x; }

enqueue(1); dequeue(); enqueue(2); enqueue(3);

for (int k = 0; k < 2; k++)
    q.enqueue(q.dequeue());

Deque<Integer> st = new ArrayDeque<>();
while (!q.isEmpty()) st.push(q.dequeue());
while (!st.isEmpty()) q.enqueue(st.pop());

try {
    for (int i = 1; i <= 4; i++) {
        q.enqueue(i * 10);
        System.out.print(i * 10 + " ");
    }
} catch (RuntimeException e) {
    System.out.println("-> " + e.getMessage());
}

int total = 0;
while (q.size() > 1) {
    int x = q.dequeue();
    int y = q.dequeue();
    q.enqueue(x + y);
    total += x + y;
}
System.out.println(q.peek() + " " + total);