C Dilinde Kuyruk Oluşturma: Detaylı Bir Rehber (Kod Örnekleriyle)

C Dilinde Kuyruk Oluşturma: Detaylı Bir Rehber (Kod Örnekleriyle)

Kuyruk (Queue), bilgisayar bilimlerinde ve yazılım mühendisliğinde sıkça kullanılan temel bir doğrusal veri yapısıdır. Gerçek dünyadaki kuyruklar gibi, bu veri yapısı da “ilk giren ilk çıkar” (First-In, First-Out – FIFO) prensibiyle çalışır. Yani, bir kuyruğa ilk eklenen eleman, kuyruktan ilk çıkarılan eleman olacaktır. Bu makale, C dilinde kuyrukların nasıl oluşturulacağını, farklı uygulama yöntemlerini (dizi tabanlı ve bağlı liste tabanlı) ve her bir yöntemin avantajları ile dezavantajlarını detaylı kod örnekleriyle açıklamaktadır.

Kuyruk Nedir ve Neden Önemlidir?

Kuyruk, elemanların bir ucundan (arka – rear/tail) eklendiği ve diğer ucundan (ön – front/head) çıkarıldığı bir veri yapısıdır. Bu FIFO prensibi, birçok gerçek dünya senaryosunu modellemek için idealdir:

* İşletim Sistemleri: Görev zamanlayıcılar, yazdırma kuyrukları, disk erişim istekleri.
* Ağ İletişimi: Yönlendiricilerde (router) paket tamponları.
* Simülasyonlar: Müşteri hizmetleri kuyrukları, üretim hattı süreçleri.
* Algoritmalar: Genişlik Öncelikli Arama (BFS) gibi grafik algoritmaları.

Kuyruklar, sistemlerdeki iş yükünü yönetmek, olayları sıralamak ve kaynakları verimli bir şekilde kullanmak için kritik öneme sahiptir.

Temel Kuyruk İşlemleri

Bir kuyruk veri yapısının temel olarak desteklemesi gereken işlemler şunlardır:

* enqueue (Ekleme): Kuyruğun arkasına yeni bir eleman ekler.
* dequeue (Çıkarma): Kuyruğun önündeki elemanı çıkarır ve döndürür. Kuyruk boşsa bir hata durumu bildirmelidir.
* front / peek (Öndeki Elemanı Görme): Kuyruğun önündeki elemanı, onu çıkarmadan döndürür. Kuyruk boşsa bir hata durumu bildirmelidir.
* isEmpty (Boş mu?): Kuyruğun boş olup olmadığını kontrol eder. Boşsa true, değilse false döndürür.
* isFull (Dolu mu?): Kuyruğun dolu olup olmadığını kontrol eder (genellikle dizi tabanlı uygulamalar için geçerlidir). Doluysa true, değilse false döndürür.
* size (Boyut): Kuyruktaki eleman sayısını döndürür.

Kuyruk Uygulama Yöntemleri

C dilinde kuyrukları uygulamak için iki ana yöntem vardır:

1. Dizi (Array) Kullanarak Kuyruk
2. Bağlı Liste (Linked List) Kullanarak Kuyruk

Her iki yöntemin de kendine göre avantajları ve dezavantajları bulunmaktadır.

Dizi (Array) Kullanarak Kuyruk

Dizi tabanlı kuyruk uygulaması, bellekte ardışık bir blok kullanarak kuyruk elemanlarını depolar. Bu yöntem basittir ve bellek erişimi genellikle daha hızlıdır (önbellek performansı açısından). Ancak, dizinin boyutu sabit olduğundan, kuyruğun kapasitesi de sabittir.

Dizi Tabanlı Kuyruğun Dezavantajları:

* Sabit Boyut: Kuyruk, tanımlandığı maksimum boyutu aşamaz.
* Verimsiz Alan Kullanımı (“Kaydırma” Sorunu): dequeue işlemi yapıldığında, kuyruğun önündeki eleman çıkarılır. Geri kalan elemanlar dizinin başına kaydırılmazsa (ki bu pahalı bir işlemdir), dizinin başında boşluklar oluşur. Bu boşluklar, kuyruğun kapasitesi dolu görünse bile gerçekte hala yer varken enqueue işlemine izin vermeyebilir. Bu sorunu çözmek için “dairesel kuyruk” (circular queue) kavramı geliştirilmiştir.

Dizi Tabanlı Kuyruk Yapısı (Basit Uygulama)

#include 
#include 
#include  // INT_MIN için

// Kuyruk yapısı tanımı
struct Queue {
    int front, rear, size;
    unsigned capacity;
    int* array;
};

// Yeni bir kuyruk oluşturur. Kapasite ile başlatılır.
struct Queue* createQueue(unsigned capacity) {
    struct Queue queue = (struct Queue) malloc(sizeof(struct Queue));
    if (!queue) {
        perror("Bellek ayırma hatası");
        exit(EXIT_FAILURE);
    }
    queue->capacity = capacity;
    queue->front = 0; // İlk elemanın indeksi
    queue->size = 0;
    queue->rear = capacity - 1; // Son elemanın ekleneceği yer (dairesel kuyruk mantığına yakın başlangıç)
    queue->array = (int) malloc(queue->capacity  sizeof(int));
    if (!queue->array) {
        perror("Dizi için bellek ayırma hatası");
        free(queue);
        exit(EXIT_FAILURE);
    }
    printf("Kuyruk %d kapasite ile oluşturuldu.\n", capacity);
    return queue;
}

// Kuyruğun dolu olup olmadığını kontrol eder
int isFull(struct Queue* queue) {
    return (queue->size == queue->capacity);
}

// Kuyruğun boş olup olmadığını kontrol eder
int isEmpty(struct Queue* queue) {
    return (queue->size == 0);
}

// Kuyruğa eleman ekler (enqueue)
void enqueue(struct Queue* queue, int item) {
    if (isFull(queue)) {
        printf("Kuyruk dolu! %d eklenemedi.\n", item);
        return;
    }
    // Dairesel kuyruk mantığı: rear'ı bir sonraki boş konuma taşır
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->array[queue->rear] = item;
    queue->size++;
    printf("%d kuyruğa eklendi.\n", item);
}

// Kuyruktan eleman çıkarır (dequeue)
int dequeue(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Kuyruk boş! Çıkarılacak eleman yok.\n");
        return INT_MIN; // Hata durumunu belirtmek için
    }
    int item = queue->array[queue->front];
    // Dairesel kuyruk mantığı: front'ı bir sonraki elemana taşır
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size--;
    printf("%d kuyruktan çıkarıldı.\n", item);
    return item;
}

// Kuyruğun önündeki elemanı döndürür (peek/front)
int front(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Kuyruk boş! Öndeki eleman yok.\n");
        return INT_MIN;
    }
    return queue->array[queue->front];
}

// Kuyruğun arkasındaki elemanı döndürür (rear)
int rear(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Kuyruk boş! Arkadaki eleman yok.\n");
        return INT_MIN;
    }
    return queue->array[queue->rear];
}

// Kuyruğu temizler ve belleği serbest bırakır
void destroyQueue(struct Queue* queue) {
    if (queue) {
        free(queue->array);
        free(queue);
        printf("Kuyruk bellekten temizlendi.\n");
    }
}

// Ana fonksiyon: Dizi tabanlı kuyruk kullanımı
int main_array_queue() {
    struct Queue* queue = createQueue(10);

    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    enqueue(queue, 40);

    printf("Kuyruğun önündeki eleman: %d\n", front(queue));
    printf("Kuyruğun arkasındaki eleman: %d\n", rear(queue));

    dequeue(queue); // 10 çıkarılacak
    dequeue(queue); // 20 çıkarılacak

    printf("Kuyruğun önündeki eleman (dequeue sonrası): %d\n", front(queue));
    printf("Kuyruğun arkasındaki eleman (dequeue sonrası): %d\n", rear(queue));

    enqueue(queue, 50);
    enqueue(queue, 60);

    printf("Kuyruğun önündeki eleman: %d\n", front(queue));
    printf("Kuyruğun arkasındaki eleman: %d\n", rear(queue));

    // Kuyruğu dolduralım
    enqueue(queue, 70);
    enqueue(queue, 80);
    enqueue(queue, 90);
    enqueue(queue, 100);
    enqueue(queue, 110); // Kapasite 10, 8 eleman var
    enqueue(queue, 120); // Kapasite 10, 9 eleman var
    enqueue(queue, 130); // Kapasite 10, 10 eleman var
    enqueue(queue, 140); // Kuyruk dolu, eklenemeyecek

    // Kuyruktaki tüm elemanları çıkaralım
    while (!isEmpty(queue)) {
        dequeue(queue);
    }
    dequeue(queue); // Kuyruk boş, hata mesajı verecek

    destroyQueue(queue);
    return 0;
}

Yukarıdaki kod örneği, aslında dairesel kuyruk mantığını kullanarak dizi tabanlı kuyruğun “kaydırma” sorununu çözmektedir. front ve rear işaretçileri dizinin sonuna ulaştığında başa dönerler (% queue->capacity operatörü sayesinde). Bu, dizinin tamamını verimli bir şekilde kullanmayı sağlar.

Dairesel Kuyruk (Circular Queue)

Dairesel kuyruk, dizi tabanlı kuyrukların verimsiz alan kullanımı sorununu çözen bir optimizasyondur. front ve rear işaretçileri dizinin sonuna ulaştığında, dizinin başına “dairesel” olarak geri dönerler. Bu, dizinin sürekli olarak yeniden kullanılmasını sağlar.

* front: Kuyruğun önündeki elemanın indeksini gösterir.
* rear: Kuyruğa yeni elemanın ekleneceği pozisyonun indeksini gösterir.
* size: Kuyruktaki eleman sayısını tutar.

Dairesel kuyrukta enqueue ve dequeue işlemleri sırasında (index + 1) % capacity formülü kullanılır.

* Dolu Kontrolü: (rear + 1) % capacity == front (eğer size kullanılmıyorsa) veya size == capacity (eğer size kullanılıyorsa).
* Boş Kontrolü: front == -1 ve rear == -1 (başlangıç için) veya size == 0.

Yukarıdaki main_array_queue fonksiyonunda kullanılan enqueue ve dequeue fonksiyonları zaten dairesel kuyruk mantığına uygun olarak yazılmıştır. front ve rear işaretçileri (index + 1) % queue->capacity şeklinde güncellenir. size değişkeni ise dolu ve boş kontrollerini daha net hale getirir.

Bağlı Liste (Linked List) Kullanarak Kuyruk

Bağlı liste tabanlı kuyruk uygulaması, her elemanın bir düğüm (node) olduğu ve bu düğümlerin birbirine işaretçiler (pointer) aracılığıyla bağlandığı bir yapıdır. Bu yöntem, kuyruğun dinamik olarak büyümesini veya küçülmesini sağlar, çünkü bellek ihtiyacı sadece mevcut eleman sayısı kadardır.

Bağlı Liste Tabanlı Kuyruğun Avantajları:

* Dinamik Boyut: Kuyruğun boyutu önceden belirlenmek zorunda değildir. İhtiyaç duyulduğunda yeni düğümler oluşturulur ve belleğe eklenir.
* Verimli Bellek Kullanımı: Sadece mevcut elemanlar için bellek tahsis edilir, dizi tabanlı kuyruklardaki gibi boşluklar oluşmaz.

Bağlı Liste Tabanlı Kuyruğun Dezavantajları:

* Ek Bellek Yükü: Her düğüm için veri elemanının yanı sıra bir sonraki düğümü işaret eden bir işaretçi (pointer) de saklanır. Bu, dizi tabanlı yaklaşıma göre biraz daha fazla bellek kullanılmasına neden olabilir.
* Daha Yavaş Erişim: Dizi tabanlı kuyruklardaki ardışık bellek yerleşimi sayesinde elde edilen önbellek avantajı burada yoktur. Elemanlara erişim, işaretçileri takip etmeyi gerektirdiğinden biraz daha yavaş olabilir.

Bağlı Liste Tabanlı Kuyruk Yapısı

Bağlı liste tabanlı bir kuyruk oluşturmak için iki temel yapıya ihtiyacımız var:

1. struct Node: Kuyruktaki her bir elemanı temsil eden düğüm. Bir veri ve bir sonraki düğümü gösteren bir işaretçi içerir.
2. struct Queue: Kuyruğun kendisini temsil eden yapı. Kuyruğun önünü (front) ve arkasını (rear) gösteren iki işaretçi içerir.

#include 
#include 
#include  // INT_MIN için

// Bağlı liste düğümü yapısı
struct Node {
    int data;
    struct Node* next;
};

// Kuyruk yapısı
struct Queue_LL {
    struct Node front, rear;
    int size; // Kuyruktaki eleman sayısını tutmak için
};

// Yeni bir düğüm oluşturur
struct Node* newNode(int data) {
    struct Node temp = (struct Node) malloc(sizeof(struct Node));
    if (!temp) {
        perror("Düğüm için bellek ayırma hatası");
        exit(EXIT_FAILURE);
    }
    temp->data = data;
    temp->next = NULL;
    return temp;
}

// Boş bir kuyruk oluşturur
struct Queue_LL* createQueue_LL() {
    struct Queue_LL q = (struct Queue_LL) malloc(sizeof(struct Queue_LL));
    if (!q) {
        perror("Kuyruk için bellek ayırma hatası");
        exit(EXIT_FAILURE);
    }
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
    printf("Bağlı liste tabanlı kuyruk oluşturuldu.\n");
    return q;
}

// Kuyruğun boş olup olmadığını kontrol eder
int isEmpty_LL(struct Queue_LL* q) {
    return (q->front == NULL);
}

// Kuyruğa eleman ekler (enqueue)
void enqueue_LL(struct Queue_LL* q, int data) {
    struct Node* temp = newNode(data);

    // Kuyruk boşsa, hem ön hem de arka yeni düğüm olur
    if (q->rear == NULL) {
        q->front = temp;
        q->rear = temp;
    } else {
        // Aksi takdirde, yeni düğümü arkanın sonuna ekler ve arkayı günceller
        q->rear->next = temp;
        q->rear = temp;
    }
    q->size++;
    printf("%d bağlı liste kuyruğuna eklendi.\n", data);
}

// Kuyruktan eleman çıkarır (dequeue)
int dequeue_LL(struct Queue_LL* q) {
    // Kuyruk boşsa, NULL döndür
    if (isEmpty_LL(q)) {
        printf("Kuyruk boş! Çıkarılacak eleman yok.\n");
        return INT_MIN; // Hata durumunu belirtmek için
    }

    // Kuyruğun önündeki düğümü sakla ve önü bir sonraki düğüme taşı
    struct Node* temp = q->front;
    int data = temp->data;

    q->front = q->front->next;

    // Eğer ön NULL olursa, kuyruk boşalmıştır, bu yüzden arkayı da NULL yap
    if (q->front == NULL) {
        q->rear = NULL;
    }

    free(temp); // Çıkarılan düğümün belleğini serbest bırak
    q->size--;
    printf("%d bağlı liste kuyruğundan çıkarıldı.\n", data);
    return data;
}

// Kuyruğun önündeki elemanı döndürür (peek/front)
int front_LL(struct Queue_LL* q) {
    if (isEmpty_LL(q)) {
        printf("Kuyruk boş! Öndeki eleman yok.\n");
        return INT_MIN;
    }
    return q->front->data;
}

// Kuyruğun arkasındaki elemanı döndürür (rear)
int rear_LL(struct Queue_LL* q) {
    if (isEmpty_LL(q)) {
        printf("Kuyruk boş! Arkadaki eleman yok.\n");
        return INT_MIN;
    }
    return q->rear->data;
}

// Kuyruğun boyutunu döndürür
int size_LL(struct Queue_LL* q) {
    return q->size;
}

// Kuyruğu temizler ve tüm düğümlerin belleğini serbest bırakır
void destroyQueue_LL(struct Queue_LL* q) {
    if (q) {
        struct Node* current = q->front;
        struct Node* next;
        while (current != NULL) {
            next = current->next;
            free(current);
            current = next;
        }
        free(q);
        printf("Bağlı liste tabanlı kuyruk bellekten temizlendi.\n");
    }
}

// Ana fonksiyon: Bağlı liste tabanlı kuyruk kullanımı
int main_linked_list_queue() {
    struct Queue_LL* q = createQueue_LL();

    enqueue_LL(q, 10);
    enqueue_LL(q, 20);
    dequeue_LL(q);
    dequeue_LL(q);
    enqueue_LL(q, 30);
    enqueue_LL(q, 40);
    enqueue_LL(q, 50);

    printf("Kuyruğun önündeki eleman: %d\n", front_LL(q));
    printf("Kuyruğun arkasındaki eleman: %d\n", rear_LL(q));
    printf("Kuyruktaki eleman sayısı: %d\n", size_LL(q));

    dequeue_LL(q);
    dequeue_LL(q);
    dequeue_LL(q);
    dequeue_LL(q); // Kuyruk boş, hata mesajı verecek

    destroyQueue_LL(q);
    return 0;
}

Bağlı liste tabanlı kuyruk uygulamasında, enqueue işlemi her zaman rear işaretçisinin gösterdiği düğümün next alanına yeni bir düğüm ekleyerek ve rear‘ı yeni düğüme taşıyarak O(1) zaman karmaşıklığında gerçekleştirilir. dequeue işlemi ise front işaretçisinin gösterdiği düğümü çıkararak ve front‘u bir sonraki düğüme taşıyarak yine O(1) zaman karmaşıklığında gerçekleştirilir. Bellek yönetimi (malloc ve free) burada kritik öneme sahiptir.

Kuyrukların Karmaşıklık Analizi

Hem dizi tabanlı (dairesel kuyruk dahil) hem de bağlı liste tabanlı kuyruk uygulamaları için temel işlemlerin zaman karmaşıklığı genellikle çok verimlidir.

* Zaman Karmaşıklığı:
* enqueue (ekleme): O(1) – Her iki yöntemde de eleman eklemek sabit zaman alır.
* dequeue (çıkarma): O(1) – Her iki yöntemde de eleman çıkarmak sabit zaman alır.
* front / peek (öndeki elemanı görme): O(1) – Öndeki elemana erişim sabit zaman alır.
* isEmpty / isFull (boş/dolu kontrolü): O(1) – Bu kontroller sabit zaman alır.
* size (boyut): O(1) – Eğer kuyruk yapısı içinde eleman sayısı tutuluyorsa sabit zaman alır.

* Yer Karmaşıklığı:
* Dizi Tabanlı: O(N), burada N kuyruğun maksimum kapasitesidir. Dizi önceden tahsis edildiği için, kuyruk boş olsa bile bu kadar yer kaplar.
* Bağlı Liste Tabanlı: O(M), burada M kuyruktaki mevcut eleman sayısıdır. Her eleman için bir düğüm (veri + işaretçi) tahsis edilir. Dinamik yapısı sayesinde yalnızca gerekli bellek kullanılır.

Hangi Uygulama Yöntemi Ne Zaman Tercih Edilmeli?

Kuyruk uygulaması için doğru yöntemi seçmek, uygulamanın özel gereksinimlerine bağlıdır:

* Dizi Tabanlı Kuyruk (Dairesel):
* Tercih Edilmeli: Kuyruğun maksimum boyutu önceden biliniyorsa ve bu boyut genellikle sabit kalacaksa. Bellek yerleşimi (cache locality) önemliyse ve performansta küçük avantajlar aranıyorsa. Bellek üzerinde daha sıkı kontrol isteniyorsa.
* Kaçınılmalı: Kuyruğun boyutu sık sık ve öngörülemeyen bir şekilde değişiyorsa, çünkü dizi yeniden boyutlandırma gerektirebilir (ki bu pahalıdır) veya kapasite dolduğunda yeni eleman eklenemez.

* Bağlı Liste Tabanlı Kuyruk:
* Tercih Edilmeli: Kuyruğun boyutu dinamik olarak değişecekse ve maksimum boyut önceden bilinemiyorsa. Bellek esnekliği ve kolay genişleyebilirlik önemliyse.
* Kaçınılmalı: Her düğüm için ek işaretçi belleği nedeniyle küçük bir bellek overhead’i kabul edilemezse. Belirli bir durumda önbellek performansı kritik öneme sahipse (nadiren büyük bir sorun teşkil eder).

Çoğu genel amaçlı uygulama için bağlı liste tabanlı kuyruklar daha esnek ve kullanışlıdır. Ancak, kaynak kısıtlı sistemlerde veya belirli performans gereksinimleri olan durumlarda dairesel dizi tabanlı kuyruklar tercih edilebilir.

Gerçek Dünya Uygulamaları

Kuyruklar, bilgisayar bilimlerinin birçok alanında temel bir yapı taşıdır:

* İşletim Sistemleri:
* Görev Zamanlama: CPU’ya gönderilmeyi bekleyen süreçler bir kuyrukta tutulur.
* G/Ç (Input/Output) Tamponları: Disk veya ağ kartı gibi yavaş cihazlardan gelen veya giden veriler, işlenene kadar kuyruklarda bekletilir.
* Yazdırma Kuyrukları: Bir ağ yazıcısına gönderilen belgeler, sırayla yazdırılmak üzere bir kuyrukta bekler.
* Ağ İletişimi:
* Paket Yönlendirme: Yönlendiriciler (router) gelen ağ paketlerini işleme sırasına göre bir kuyrukta tutar.
* Trafik Yönetimi: Ağ tıkanıklığını önlemek için paketler belirli bir sıraya göre gönderilir.
* Web Sunucuları: Gelen HTTP istekleri, sunucunun işleme kapasitesine göre bir kuyrukta bekletilebilir.
* Veri Yapısı ve Algoritmalar:
* Genişlik Öncelikli Arama (BFS): Bir grafikte veya ağaçta düğümleri seviye seviye ziyaret etmek için kuyruk kullanılır.
* Kritik Yol Analizi: Proje yönetiminde görev bağımlılıklarını ve kritik yolu belirlemek için kullanılabilir.
* Simülasyonlar: Gerçek dünyadaki kuyruk sistemlerini (banka kuyrukları, süpermarket kasaları) modellemek için kullanılır.

Sonuç

Kuyruklar, bilgisayar bilimlerindeki en temel ve yaygın kullanılan veri yapılarından biridir. “İlk giren ilk çıkar” (FIFO) prensibi, birçok senaryoda doğal bir sıralama ve işleme mekanizması sağlar. C dilinde kuyrukları uygulamak için dizi tabanlı (özellikle dairesel kuyruk) ve bağlı liste tabanlı olmak üzere iki ana yöntem bulunmaktadır.

Dizi tabanlı kuyruklar, sabit boyutlu ve bellekte ardışık yerleşimin avantajlarına sahipken, bağlı liste tabanlı kuyruklar dinamik boyut ve esnek bellek yönetimi sunar. Her iki uygulamanın da temel işlemler için O(1) zaman karmaşıklığına sahip olması, kuyrukları çoğu durumda oldukça verimli kılar.

Doğru kuyruk uygulamasını seçmek, uygulamanızın gereksinimlerine (bellek kısıtlamaları, performans hedefleri, dinamik boyut ihtiyacı) bağlıdır. Bu makalede sunulan kod örnekleri ve açıklamalar, C dilinde kendi kuyruk yapılarınızı oluşturmanız ve farklı senaryolarda kullanmanız için sağlam bir temel sağlamaktadır. Kuyrukların gücünü ve esnekliğini anlayarak, daha sağlam ve verimli yazılımlar geliştirebilirsiniz.