Queue (Kuyruk) Veri Yapısı

📋 Genel Tanım ve Kavram

Queue (Kuyruk), bilgisayar bilimlerinde kullanılan temel veri yapılarından biridir ve FIFO (First-In-First-Out) prensibine göre çalışır.

💡 Gerçek Hayat Analojisi: Market kasasındaki kuyruk gibi düşünün. İlk sıraya giren müşteri, ilk hizmet alan müşteridir. Yeni müşteriler her zaman kuyruğun sonuna eklenir.

Temel Prensip

• İlk eklenen eleman, ilk çıkarılan elemandır
• Elemanlar sadece bir uçtan eklenir (back/rear)
• Elemanlar sadece diğer uçtan çıkarılır (front)

┌───────────────────────────────────────────┐
│                  QUEUE                     │
│                                            │
│  front/head              back/rear/tail   │
│      ↓                        ↓            │
│    [a] → [b] → [c] → [d] → [e]            │
│     ↑                        ↑             │
│   ÇIKIŞ                   GİRİŞ           │
│  (dequeue)              (enqueue)          │
└───────────────────────────────────────────┘

🔧 Temel Operasyonlar

💻 Bağlı Liste ile İmplementasyon

Neden Bağlı Liste?

✅ Dinamik boyut - önceden boyut belirlemeye gerek yok
✅ Tüm operasyonlar O(1) zamanda çalışır
✅ Overflow problemi yok

Java Kodu

class Node<E> {
    E data;
    Node<E> next;
    
    public Node(E data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedListQueue<E> {
    private Node<E> front;
    private Node<E> back;
    private int size;
    
    public LinkedListQueue() {
        front = null;
        back = null;
        size = 0;
    }
    
    // Kuyruğun sonuna eleman ekle
    public void enqueue(E element) {
        Node<E> newNode = new Node<>(element);
        
        if (isEmpty()) {
            // İlk eleman
            front = newNode;
            back = newNode;
        } else {
            // Mevcut back'in next'ini yeni node yap
            back.next = newNode;
            back = newNode;
        }
        size++;
    }
    
    // Kuyruğun başından eleman çıkar
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        
        E data = front.data;
        front = front.next;
        size--;
        
        // Eğer kuyruk boşaldıysa back'i de null yap
        if (isEmpty()) {
            back = null;
        }
        
        return data;
    }
    
    // Başındaki elemana bak (çıkarma)
    public E first() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return front.data;
    }
    
    public int size() {
        return size;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
}

Adım Adım Çalışma Örneği

Başlangıç: front → null, back → null, size = 0

enqueue(5):
front → [5] → null
back  → [5]
size = 1

enqueue(2):
front → [5] → [2] → null
back  → [2]
size = 2

enqueue(8):
front → [5] → [2] → [8] → null
back  → [8]
size = 3

dequeue() → 5:
front → [2] → [8] → null
back  → [8]
size = 2

first() → 2 (kuyruk değişmez)

🔄 Döngüsel Array ile İmplementasyon

Neden Döngüsel Array?

✅ Tüm operasyonlar O(1)
✅ Bellek verimliliği (boşluklar tekrar kullanılır)
✅ Cache-friendly (bellek lokalitesi iyi)

Döngüsel Mantık

Normal Array Problemi:
[x][x][c][d][e][ ][ ][ ]  → dequeue sonrası boşluklar kullanılamaz
    ↑       ↑
  front   back

Döngüsel Çözüm:
[ ][g][c][d][e][f][ ][ ]  → Array sonu başa döner
     ↑           ↑
   back        front

Java Kodu

public class CircularArrayQueue<E> {
    private E[] data;
    private int front;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;
    
    @SuppressWarnings("unchecked")
    public CircularArrayQueue() {
        data = (E[]) new Object[DEFAULT_CAPACITY];
        front = 0;
        size = 0;
    }
    
    // Kuyruğun sonuna eleman ekle
    public void enqueue(E element) {
        if (size == data.length) {
            resize(2 * data.length);
        }
        
        // back pozisyonunu hesapla: (front + size) % capacity
        int back = (front + size) % data.length;
        data[back] = element;
        size++;
    }
    
    // Kuyruğun başından eleman çıkar
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        
        E element = data[front];
        data[front] = null;  // Garbage collection için
        front = (front + 1) % data.length;  // Döngüsel artış
        size--;
        
        // Bellek optimizasyonu: %25 doluysa boyutu yarıya indir
        if (size > 0 && size == data.length / 4) {
            resize(data.length / 2);
        }
        
        return element;
    }
    
    // Başındaki elemana bak
    public E first() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return data[front];
    }
    
    public int size() {
        return size;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    // Array'i yeniden boyutlandır
    @SuppressWarnings("unchecked")
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        
        // Elemanları yeni array'e kopyala
        for (int i = 0; i < size; i++) {
            newData[i] = data[(front + i) % data.length];
        }
        
        data = newData;
        front = 0;
    }
}

Adım Adım Çalışma Örneği

Başlangıç: [ ][ ][ ][ ][ ]  front=0, size=0

enqueue(5):
[5][ ][ ][ ][ ]  front=0, size=1
 ↑
front

enqueue(2):
[5][2][ ][ ][ ]  front=0, size=2
 ↑  ↑
front back

enqueue(8):
[5][2][8][ ][ ]  front=0, size=3

dequeue() → 5:
[ ][2][8][ ][ ]  front=1, size=2
    ↑
  front

enqueue(9):
[ ][2][8][9][ ]  front=1, size=3
    ↑     ↑
  front  back

enqueue(4):
[ ][2][8][9][4]  front=1, size=4

enqueue(7):  (Döngüsel olarak başa döner)
[7][2][8][9][4]  front=1, size=5
 ↑  ↑
back front

📊 İmplementasyon Karşılaştırması

*Amortized: Bazı durumlarda O(n) (resize), ama ortalama O(1)

🌍 Kullanım Alanları

İşletim Sistemleri

• Process scheduling (CPU görev sırası)
• Print queue (yazıcı kuyruğu)

Ağ ve İletişim

• Router’larda paket yönetimi
• Message queues (RabbitMQ, Kafka)

Algoritmalarda

• BFS (Breadth-First Search): Graf gezinme
• Buffer management

Günlük Uygulamalar

• Müşteri hizmetleri çağrı merkezi
• Online bilet satış sistemleri
• Restoran sipariş yönetimi

💡 Önemli Notlar

⚠️ Edge Cases

🎯 Ne Zaman Kullanmalı?

Queue Kullan:

• FIFO davranışı gerekiyorsa
• İşlem sırasını korumak önemliyorsa
• BFS algoritması yapılacaksa

Queue Kullanma:

• LIFO gerekiyorsa → Stack kullan
• Öncelik bazlı işlem → Priority Queue kullan
• Rastgele erişim → Array/List kullan

📚 Özet

Queue, FIFO prensibine göre çalışan temel bir veri yapısıdır. İki ana implementasyonu vardır:

1. Bağlı Liste: Dinamik, overflow yok, her operasyon gerçek O(1)
2. Döngüsel Array: Cache-friendly, bellek verimli, amortized O(1)

Her ikisi de avantajlı, seçim kullanım senaryosuna bağlıdır.