Veri Yapıları ve Programlama

7 - Kuyruk (Queue) Veri Yapısı

Emre Can Yılmaz

emrecan@omu.edu.tr

Ondokuz Mayıs Üniversitesi

2026

Kuyruk - Giriş

Bazı problemlerde önemli olan en son gelen değil, önce gelen elemanın önce işlenmesidir.

Kuyruk, elemanların bir uçtan eklendiği ve diğer uçtan çıkarıldığı doğrusal bir veri yapısıdır.

• sona ekleme: rear
• baştan çıkarma: front
• temel kural: ilk gelen eleman ilk çıkar

Gündelik benzetim: banka sırası, yazıcı kuyruğu, müşteri hizmetleri bekleme hattı.

Bu Derste Ne Öğreneceğiz?

Bu dersin sonunda şunları yapabiliyor olmanız beklenir:

• kuyruğun neden FIFO mantığıyla çalıştığını açıklamak,
• front ve rear kavramlarını karıştırmadan kullanmak,
• kuyruğun soyut veri tipi olduğunu, farklı biçimlerde gerçekleştirilebileceğini ayırt etmek,
• bağlı liste ile gerçekleştirilen bir kuyrukta enqueue ve dequeue işlemlerinin mantığını açıklamak,
• boş kuyruk ve tek elemanlı kuyruk gibi kenar durumlarını fark etmek.

Geçen Haftadan Bu Haftaya Köprü

Geçen hafta bağlı listelerde düğümler arasında bağlantı kurmayı ve bağlantıyı bozmadan işlem yapmayı gördük. Bu hafta o bilgiyi yeni bir amaç için kullanıyoruz:

Bağlı listeyi kullanarak FIFO davranışı gösteren bir kuyruk oluşturmak.

• bağlı listedeki ilk düğüm: kuyruktaki front
• bağlı listedeki son düğüm: kuyruktaki rear
• sona ekleme ve baştan çıkarma işlemleri, bağlı listenin doğal yapısına çok uygundur

FIFO (First-In-First-Out)

Kuyruk, İlk Giren İlk Çıkar kuralı ile çalışır.

Yukarıdaki görselde 1 önce geldiği için kuyruktan ilk çıkacak eleman da odur. FIFO mantığında önemli olan değerlerin büyüklüğü değil, geliş sırasıdır.

FIFO’yu Metinle Görmek

front                           rear
    |                               |
    v                               v
+----+    +----+    +----+
| 10 | -> | 20 | -> | 30 |
+----+    +----+    +----+

• enqueue(40) olursa yeni eleman en sağa eklenir
• dequeue() olursa en soldaki eleman çıkar
• yani ekleme ve çıkarma aynı uçtan yapılmaz

Kuyruğu Doğru Düşünmek

Öğrencilerin en sık karıştırdığı nokta şudur:

1. Kuyruk bir soyut veri tipidir.
2. Bu soyut yapı diziyle de gerçekleştirilebilir, bağlı listeyle de gerçekleştirilebilir.

Bu derste ağırlıklı olarak bağlı liste ile gerçekleştirme üzerinde duracağız.

Not

front = -1, rear = -1 gibi başlangıç değerleri genellikle dizi tabanlı kuyruklar için kullanılır. Bağlı listede ise çoğunlukla head = NULL, tail = NULL yaklaşımı kullanılır.

İsimleri Eşleştirelim

• kuyruk düzeyinde: front ve rear
• bağlı liste düzeyinde: head ve tail

Bu derste çoğu zaman şu eşleşmeyi kullanacağız:

• front = head
• rear = tail

Bu eşleşmeyi net tutmak, iki farklı kavramı karıştırmamanızı sağlar.

Kullanım Alanları

• işletim sistemlerinde görev zamanlama ve yazıcı kuyrukları,
• ağ iletişiminde paketlerin sıraya alınması,
• simülasyonlarda müşteri, araç veya olay akışının modellenmesi,
• arka planda çalışacak işlerin sıraya alınması.

Kuyruk, verilerin hangi sırayla işleneceğini kontrol etmek istediğimiz her yerde karşımıza çıkar.

Temel İşlemler ve Kavramlar

• enqueue: kuyruğun sonuna eleman ekler
• dequeue: kuyruğun başından eleman çıkarır
• peek: baştaki elemana çıkarmadan bakar
• isEmpty: kuyruk boş mu kontrol eder
• front: ilk elemanın bulunduğu konumu gösterir
• rear: son elemanın bulunduğu konumu gösterir

Dikkat

isFull kavramı her gerçekleştirmede aynı anlamı taşımaz. Sabit boyutlu dizi tabanlı kuyruklarda anlamlıdır; bağlı listede ise kuyruk genellikle bellek yettiği sürece büyüyebilir.

Bağlı Liste ile Kuyrukta Tutulan Bilgiler

Bağlı liste ile kuyruk gerçekleştireceksek en az iki göstericiye ihtiyaç duyarız:

• head: kuyruktaki ilk düğüm, yani front
• tail: kuyruktaki son düğüm, yani rear

Başlangıç durumu:

• head == NULL
• tail == NULL

Bu durum kuyruğun boş olduğunu gösterir.

Neden Hem head Hem tail Tutuyoruz?

Eğer sadece head tutarsak, sona eleman eklemek için her seferinde listenin sonuna kadar gitmemiz gerekir.

• head + tail birlikte tutulursa enqueue işlemi çoğu durumda \(O(1)\) olur.
• dequeue işlemi de baştan çıkarma yaptığı için \(O(1)\) olur.

Bu yüzden kuyruk, bağlı liste ile gerçeklenirken çoğu zaman iki uç da tutulur.

Enqueue Mantığı

Bağlı liste ile kuyrukta sona ekleme adımları şöyledir:

1. Yeni düğüm için bellek ayır.
2. Veriyi yerleştir.
3. Yeni düğümün sonraki alanını NULL yap.
4. Kuyruk boşsa head ve tail aynı düğümü göstersin.
5. Kuyruk boş değilse eski tail yeni düğümü göstersin, sonra tail güncellensin.

Kritik fikir: ekleme her zaman sonda yapılır.

Kuyruğun Temel Yapısı

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int veri;
    struct Node *sonraki;
};

struct Node *head = NULL;
struct Node *tail = NULL;

Ders İçi Sadeleştirme

Bu derste mantığı sade göstermek için head ve tail işaretçilerini global tuttuk. Daha sonraki aşamalarda bunları ayrı bir Queue yapısı içinde toplamak da mümkündür.

enqueue Gerçeklemesi

void enqueue(int sayi) {
    struct Node *yeni = malloc(sizeof(struct Node));

    if (yeni == NULL) {
        printf("Bellek ayirma basarisiz.\n");
        return;
    }

    yeni->veri = sayi;
    yeni->sonraki = NULL;

    if (head == NULL) {
        head = yeni;
        tail = yeni;
        return;
    }

    tail->sonraki = yeni;
    tail = yeni;
}

Dequeue Mantığı

Baştan çıkarma sırasında şu sıra izlenir:

1. Kuyruk boş mu kontrol et.
2. head düğümünü geçici bir işaretçide tut.
3. Çıkarılacak veriyi sakla.
4. head işaretçisini bir sonraki düğüme kaydır.
5. Eğer kuyruk boşaldıysa tail değerini de NULL yap.
6. Eski düğümü free ile serbest bırak.

En kritik kenar durum: kuyrukta tek eleman varken dequeue yapılmasıdır.

dequeue Gerçeklemesi

int dequeue() {
    struct Node *eskiHead;
    int veri;

    if (head == NULL) {
        printf("Kuyruk bos.\n");
        return -1;
    }

    eskiHead = head;
    veri = eskiHead->veri;
    head = head->sonraki;

    if (head == NULL) {
        tail = NULL;
    }

    free(eskiHead);
    return veri;
}

Küçük Teknik Not

Bu örnekte boş kuyruk durumunu basit tutmak için -1 döndürüyoruz. Gerçek uygulamalarda hata yönetimi, dönüş değeri ile karışmayacak şekilde farklı tasarlanabilir.

enqueue ve dequeue Akışı

Başlangıç:
front/rear
        |
        v
+----+
| 10 |
+----+

enqueue(20):
front           rear
  |               |
  v               v
+----+  ->  +----+
| 10 |      | 20 |
+----+      +----+

dequeue():
önce:  [10] -> [20]
sonra: [20]

Bu akışta görmeniz gereken temel şey şudur: enqueue kuyruğu büyütür, dequeue ise head işaretçisini sağa kaydırır.

Adım Adım Örnek

Başlangıçta kuyruk boş olsun.

1. enqueue(10) -> head = 10, tail = 10
2. enqueue(20) -> 10 -> 20
3. enqueue(30) -> 10 -> 20 -> 30
4. dequeue() -> 10 çıkar, kuyruk 20 -> 30 olur
5. dequeue() -> 20 çıkar, kuyruk 30 olur
6. dequeue() -> 30 çıkar, artık head = NULL, tail = NULL

Bu örnek, tail değerinin neden son eleman çıkarıldığında da güncellenmesi gerektiğini gösterir.

Kuyruğu Yazdırma

void kuyrukYaz() {
    struct Node *etkin = head;

    while (etkin != NULL) {
        printf("%d ", etkin->veri);
        etkin = etkin->sonraki;
    }

    printf("\n");
}

Bu fonksiyon kuyruktaki elemanları head’den başlayarak sırayla ekrana yazdırır. Yapıyı değiştirmez; sadece dolaşır.

Zaman Karmaşıklığı

• enqueue: \(O(1)\)
• dequeue: \(O(1)\)
• peek: \(O(1)\)
• tüm elemanları yazdırma / dolaşma: \(O(n)\)

Buradaki hız avantajı, head ve tail işaretçilerinin birlikte tutulmasından gelir.

Tek Elemanlı Durum Neden Özel?

Başlangıç:
head
tail
 |
 v
+----+
| 42 |
+----+

dequeue() sonrası:
head = NULL
tail = NULL

Eğer burada sadece head = NULL yapıp tail değerini eski düğümü göstermeye bırakırsanız, kuyruk boş olduğu halde programınız son düğüm varmış gibi davranabilir.

Kuyruk Türlerine Kısa Bakış

• basit kuyruk: klasik FIFO yapı
• dairesel kuyruk: dizi tabanlı yapılarda boş alanı daha verimli kullanır
• öncelikli kuyruk: çıkış sırası yalnızca geliş zamanına göre değil, önceliğe göre belirlenir
• çift uçlu kuyruk: elemanlar her iki uçtan da eklenip çıkarılabilir

Sık Yapılan Hatalar

• FIFO mantığını “küçük olan önce çıkar” gibi yorumlamak
• dizi tabanlı kuyruk mantığı ile bağlı liste tabanlı kuyruk mantığını karıştırmak
• dequeue sonrasında kuyruk boşaldığında tail değerini güncellememek
• malloc sonucunu kontrol etmemek
• düğümü çıkardıktan sonra free etmeyi unutmak

Alıştırma

void foo() {
    struct Node *etkin = head;

    while (etkin != NULL) {
        printf("%d ", etkin->veri);
        etkin = etkin->sonraki;
    }

    printf("\n");
}

Sorular:

1. Bu fonksiyon ne yapmaktadır?
2. Neden doğrudan head üzerinde ilerlemek yerine etkin adında geçici bir işaretçi kullanıyoruz?
3. Eğer kuyruk boşsa bu fonksiyonun çıktısı ne olur?

Quiz

1. Kuyrukta enqueue işlemi hangi uçta yapılır?
   1. front
   2. rear
   3. ortada
   4. rastgele

2. Bağlı liste ile kuyrukta son eleman çıkarıldıktan sonra hangisi doğru olmalıdır?
   1. sadece head = NULL
   2. sadece tail = NULL
   3. head = NULL ve tail = NULL
   4. head = tail

3. head ve tail birlikte tutulursa hangi işlem genellikle \(O(1)\) olur?
   1. sadece yazdırma
   2. sadece arama
   3. enqueue ve dequeue
   4. tüm işlemler

Sonraki Derse Hazırlık

Bir sonraki derste şunları daha ayrıntılı ele alacağız:

• peek ve isEmpty fonksiyonlarını ekleme,
• kuyruk fonksiyonlarını main içinde test etme,
• dizi tabanlı kuyrukta front ve rear güncellemelerini inceleme,
• sabit boyut ve taşma problemi üzerinden dairesel kuyruk fikrine geçiş.

Teşekkürler