Veri Yapıları ve Programlama

7 - Kuyruk (Queue) Veri Yapısı

Emre Can Yılmaz

[email protected]

Ondokuz Mayıs Üniversitesi

2025

Kuyruk

Kuyruk, elemanların bir ucundan (arka/rear) eklendiği ve diğer ucundan (ön/front) çıkarıldığı, doğrusal ve sıralı bir veri yapısıdır.
Bir sinema salonunun dışındaki bilet kuyruğuna benzer, burada kuyruğa giren ilk kişi bileti alan ilk kişidir.

Kullanım Alanları

İşletim Sistemleri: Görev zamanlama (CPU scheduling), disk zamanlama, yazıcı kuyrukları, I/O işlemleri.
Ağ İletişimi: Paket yönlendirme, veri aktarımı.
Simülasyonlar: Gerçek dünya sistemlerinin davranışlarını modelleme (örneğin, banka gişesi, trafik ışıkları).
Asenkron veri işleme: Arka planda çalışacak görevleri sıraya almak.

FIFO (First-In-First-Out)

Kuyruk, İlk Giren İlk Çıkar (FIFO - First-In-First-Out) kuralını izler yani ilk giren öğe ilk çıkan öğedir.

Yukarıdaki görüntüde 1, 2’den önce kuyrukta bekletildiği için kuyruktan ilk çıkarılacak olan da odur. Burada lk Giren İlk Çıkar (FIFO - First-In-First-Out) kuralı işler.

Kuyruğun Temel İşlemleri ve Kavramları

Bir kuyruğun üzerinde farklı eylemler gerçekleştirmemizi sağlayan bazı temel işlemler vardır.

Enqueue: Kuyruğun sonuna bir öğe ekler.
Dequeue: Bir öğeyi kuyruğun önünden kaldırır.
IsEmpty: Kuyruğun boş olup olmadığını kontrol eder.
IsFull: Kuyruğun dolu olup olmadığını kontrol eder.
Peek: Kuyruğun önündeki değere kaldırmadan erişme.
Front: Kuyruğun başındaki (ilk elemanın bulunduğu) pozisyonu gösterir.
Rear: Kuyruğun sonundaki (son elemanın bulunduğu) pozisyonu gösterir.

Kuyruk Çalışma Prensibi

Kuyruk işlemleri aşağıdaki gibi çalışır:

ÖN(FRONT) ve ARKA(REAR) olmak üzere iki işaretçi vardır.
FRONT kuyruğun ilk öğesini izler.
REAR kuyruğun son elemanını takip eder.
Başlangıçta, FRONT ve REAR değerini -1 olarak ayarlayın.

Enqueue İşlemi (Kuyruğa Eleman Ekleme)

Kuyruğun dolu olup olmadığını kontrol edin
ilk öğe için FRONT değerini 0 olarak ayarlayın
REAR değerini 1 artırın
REAR tarafından işaret edilen konuma yeni eleman ekler.

Dequeue İşlemi (Kuyruktan Eleman Çıkarma)

Kuyruğun boş olup olmadığını kontrol edin
FRONT tarafından işaret edilen değeri döndür.
FRONT değerini 1 artır.
Son öğe için FRONT ve REAR değerlerini -1 olarak sıfırlayın.

Kuyruk Türleri

Kuyruk, programlamada kullanışlı bir veri yapısıdır. Bir sinema salonunun dışındaki bilet kuyruğuna benzer, burada kuyruğa giren ilk kişi bileti alan ilk kişidir. Dört farklı kuyruk türü vardır:

Basit Kuyruk (Simple Queue)
Dairesel Kuyruk (Circular Queue)
Öncelikli Kuyruk (Priority Queue)
Çift Uçlu Kuyruk (Double Ended Queue)

Basit Kuyruk

Basit bir kuyrukta, ekleme arkadan gerçekleşir ve çıkarma önde gerçekleşir. FIFO (İlk giren ilk çıkar) kuralına sıkı sıkıya bağlıdır.

Dairesel Kuyruk

Dairesel bir kuyrukta, son eleman dairesel bir bağlantı oluşturan ilk elemanı işaret eder.

Dairesel bir kuyruğun basit bir kuyruğa göre ana avantajı daha iyi bellek kullanımıdır.
Eğer son pozisyon doluysa ve ilk pozisyon boşsa, ilk pozisyona bir eleman ekleyebiliriz.
Bu işlem basit bir kuyrukta mümkün değildir.

Öncelikli Kuyruk

Öncelik kuyruğu, her elemanın bir öncelik ile ilişkilendirildiği ve önceliğine göre servis edildiği özel bir kuyruk türüdür.
Aynı önceliğe sahip öğeler ortaya çıkarsa, kuyruktaki sıralarına göre servis edilirler.
Örnek olarak hastanelerdeki aciliyet sırasına göre acil hastalara öncelik verilmesi olabilir.

Çift Uçlu Kuyruk

Çift uçlu bir kuyrukta, elemanların eklenmesi ve çıkarılması önden veya arkadan gerçekleştirilebilir.
Bu nedenle FIFO (İlk Giren İlk Çıkar) kuralına uymaz.

C ile Gerçekleme

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

struct test {
    int veri;
    struct test *sonraki;
} Node, *etkin, *head, *tail;

void sonaEkle(int sayi) {
    struct test *etkin;

    etkin=(struct test *)malloc(sizeof(Node));
    etkin->veri=sayi;
    etkin->sonraki=NULL;

    if (head == NULL) {
        head=etkin;
        tail=etkin;
    } else {
        tail->sonraki=etkin;
        tail=etkin;
    }
    return;
}

void kuyrukYaz() {
    etkin = head;
    while (etkin) {
        printf("%d", etkin->veri);
        etkin = etkin->sonraki;
    }
    return;
}

int main() {
    int i;
    for (i=1;i<10;i++) {
        sonaEkle(i*i);
        printf("\n");
        kuyrukYaz();
    }
}

Kodun tam hali: https://gist.github.com/ecylmz/2ee82af420067ba0a590ca25aca4c123

Çalışma sorusu: Kuyruktan çıkarma işlevini (dequeue) yazın.

Alıştırma

struct test {
  int veri;
  struct test *sonraki;
} Node, *etkin, *head, *tail

void foo() {
  etkin = head;
  while (etkin) {
    printf(“%d ”, etkin->veri);
    etkin = etkin->sonraki;
  }
  return;
}

Yukarıdaki foo isimli fonksiyon ne yapmaktadır?

Görselleştirme

https://lumos.emrecan.dev/queue