Veri Yapıları ve Programlama

7 - Kuyruk (Queue) Veri Yapısı

Emre Can Yılmaz

[email protected]

Ondokuz Mayıs Üniversitesi

2026

Kuyruk

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

• Temel kural: ilk gelen eleman ilk çıkar

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

Geçen Haftadan Bu Haftaya Köprü

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

Bağlı listeyi kullanarak bir kuyruk oluşturmak.

Bu bağlantıyı şöyle düşünebiliriz:

• Bağlı listedeki ilk düğüm: kuyruktaki front
• Bağlı listedeki son düğüm: kuyruktaki rear

Yani bu derste bağlı liste mantığını, kuyruk davranışı üretmek için kullanacağız.

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

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

• Yeni eleman sağ uçtan eklenir
• Çıkarma işlemi sol uçtan yapılır
• Yani ekleme ve çıkarma aynı uçta değildir

Temel İşlemler ve Kavramlar

Kuyruk üzerinde en sık kullanılan işlemler şunlardır:

• 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

Ayrıca iki temel konum vardır:

• front: İlk elemanın bulunduğu uç
• rear: Son elemanın bulunduğu uç

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.

Bağlı Liste ile Kuyrukta Göstericiler

Kuyruk düzeyinde kullandığımız uçlar ile bağlı listedeki göstericiler şu şekilde eşleşir:

• front = head
• rear = tail

Yani:

• head, kuyruktaki ilk düğümü gösterir
• tail, kuyruktaki son düğümü gösterir

Başlangıçta kuyruk boşsa:

• head == NULL
• tail == NULL

Bu durum, kuyrukta henüz hiç düğüm olmadığını 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 ve tail birlikte tutulursa sona ekleme işlemi doğrudan yapılabilir
• baştan çıkarma işlemi de doğrudan ilk düğüm üzerinden yapılır

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

Enqueue Mantığı

enqueue, kuyruğun sonuna eleman ekleme işlemidir.

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.

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ığı

dequeue, kuyruğun başından eleman çıkarma işlemidir.

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.

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]

Adım Adım Örnek

Başlangıçta kuyruk boş olsun.

1. enqueue(10)

head
tail
 |
 v
+----+
| 10 |
+----+

2. enqueue(20)

head           tail
 |               |
 v               v
+----+  ->  +----+
| 10 |      | 20 |
+----+      +----+

3. enqueue(30)

head                      tail
 |                          |
 v                          v
+----+  ->  +----+  ->  +----+
| 10 |      | 20 |      | 30 |
+----+      +----+      +----+

Tek Elemanlı Kuyrukta dequeue

Aşağıdaki durumda kuyrukta yalnızca bir eleman olsun:

head
tail
 |
 v
+----+
| 10 |
+----+

Bu elemana dequeue() uygularsak:

• head bir sonraki düğüme gider → NULL
• kuyruk boşaldığı için tail de NULL yapılır

Yani işlem sonunda:

head = NULL;
tail = NULL;

Bu güncelleme yapılmazsa yapı bozulur.

Zaman Karmaşıklığı

Bağlı liste ile ve hem head hem tail tutulan bu yapıda:

• enqueue → \(O(1)\)
• dequeue → \(O(1)\)
• peek → \(O(1)\)
• arama / dolaşma → \(O(n)\)

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

Kullanım Alanları

Kuyruk yapısı şu tür durumlarda doğal olarak karşımıza çıkar:

• İş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ı

Buradaki ortak fikir şudur: işler, geliş sırasına göre ele alınır.

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

Not

Bu derste ayrıntılı olarak yalnızca temel kuyruk yapısını ele alıyoruz. Diğer türler, sonraki konular için kısa bir ön bilgidir.

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

Teşekkürler