Kuyruk (Queue) | Veri Yapıları

Kuyruk, doğrusal bir yapıda sırasıyla işlemlerin gerçekleştirildiği yapıdır. FIFO(First In First Out) mantığına göre çalışmaktadır, yani ilk giren ilk çıkar. Kuyruk yapısının çalışması gerçek hayatta insanlar tarafından oluşturulan kuyrukların çalışması ile aynıdır. Bankamatik kuyruğunda, ilk sırada yer alan insan işini ilk bitirdiği için kuyruktan ilk çıkan kişidir. Kuyruğun sonunda yer alan kişi ise kuyruktan en son çıkacaktır.
C++ Queue - Kuyruk Veri Yapısı
Kuyruk yapısının uygulandığı alanlara örnek olarak, CPU görev zamanlaması, gerçek hayatta çağrı merkezleri vs. verilebilir. 

Kuyruk yapısının uygulanabileceği en kolay yöntem Array(dizi) kullanımıdır. Kuyrukta eleman ekleme işlemine enqueue ve eleman çıkarma ise dequeue olarak adlandırılmaktadır. En başta front(ön) ve rear(arka) dizinin 0. indisini gösterir. Çoğu kaynak head kelimesini front temsili ve tail kelimesini rear temsili olarak kullanıyor. tail, her zaman kuyruğa yeni eklenecek elemanın kuyruktaki yerini işaret eder. head ise kuyruğun başındaki elemanı temsil etmektedir. 
C++ Queue - Kuyruk Veri Yapısı
Yukarıdaki animasyonda kuyruk yapısının dizi üzerindeki hareketleri gösterilmektedir. Sol ve sağ tarafta yer alan dizideki kuyruk yapısında elemanlar 0.indisten itibaren ekleniyor. Her eklemede head konumu sabit kalırken, tail konumu son eklenen eleman konumunun bir fazlasını gösteriyor. Ancak durum eleman çıkarma sırasında değişiyor. Sol tarafta yer alan dizide her eleman kuyruktan çıktığında diğer tüm elemanların bulunduğu indis konumu 1 azaltılıyor. Yani tüm elemanlar bir önceki elemanın yerini alıyor. Bu kullanımının dezavantajı fazladan performans yükü oluşturmasıdır. Sağ dizideki eleman çıkarma işleminde yapılan iş sadece çıkarılan elemandan sonraki elemanı head ile işaret etmek. Bu kullanımın dezavantajı ise kullanılabilir dizi boyutunun her çıkarma işlemi sırasında küçülmesidir.

Kuyruk yapısına eleman ekleme(enqueue) algoritması aşağıdaki gibidir:
  1. Kuyruk yapısı dolu mu, kontrol edilir.
  2. Eğer doluysa eleman eklemesi yapılmaz ve dolu olduğu belirtilir.
  3. Eğer dolu değilse tail bir arttırılır ve eleman eklenir.
Kuyruk yapısından eleman çıkarma(dequeue) algoritması aşağıdaki gibidir:

  1. Kuyruk yapısı boş mu, kontrol edilir.
  2. Eğer boşsa eleman çıkartılamaz ve boş olduğu belirtilir.
  3. Eğer boş değilse eleman çıkartılır ve head bir indis arttırılır.
Kuyruk veri yapısını algoritmalara göre C++ ile gerçekleştirelim:
#include <iostream>

class Kuyruk{
    int kapasite;
    int uzunluk;
    int head;
    int tail;
    int *dizi;
    
    public:
        Kuyruk(int k){
            kapasite = k;
            head = 0;
            tail = 0;
            uzunluk = 0;
            dizi = new int[k];
        }

        bool doluMu(){
            if(head+1 == kapasite){
                return true;
            }
            return false;
        }

        bool bosMu(){
            if(uzunluk == 0)
                return true;
            return false;
        }

        void ekle(int deger){
            if(doluMu()){
                std::cout << "Kuyruk kapasitesi dolu!\n";
            }else{
                dizi[tail] = deger;
                tail++;
                uzunluk++;
                std::cout << deger << " kuyruga eklendi.\n";
            }
        }

        void cikar(){
            if(bosMu()){
                std::cout << "Kuyruk bos!\n";
            }else{
                std::cout << dizi[head] << " kuyruktan cikarildi.\n";
                dizi[head] = -1;
                head++;
            }
        }
};

int main(){
    Kuyruk *m = new Kuyruk(10);
    m->ekle(12);
    m->ekle(32);
    m->ekle(22);
    m->ekle(44);
    m->cikar();
    m->cikar();
    m->ekle(99);
    m->cikar();
    m->cikar();
    m->cikar();
    return 0;
}

Hiç yorum yok:

Yorum Gönderme