Takıldığınız bir şey mi var?

.NET, front-end development, data structures veya desing patterns gibi konularda sorular açın ve en kısa zamanda cevaplayalım...


4
Şubat

C++ dili ile Queue veri yapısı örneği ve FIFO çalışma mantığı.

Bu yazımızda FIFO çalışma prensibi ve Queue veri yapısı hakkında konuşacağız. FIFO, “First in first out” kelimelerinin baş harflerinden oluşmuş bir kısaltma olup “İlk giren ilk çıkar” prensibi ile çalışan bir veri yapısını ifade eder.


FIFO mantığını daha iyi anlamak ilerleyen satırlarda irdeleyeceğimiz Queue veri yapısı ile aramızda yakınlık oluşturacaktır. Bu yüzden makalemizin kapak görselindeki kuyruğu inceleyelim. Böyle bir sırada olmayı aslında kimse istemez öyle değil mi? Sıra beklemek çoğumuz için stres ifade eden bir durumdur. Lakin kuyrukta sıra beklemenin güzel sayılabilecek bir yönü vardır ki bu da kuyruğa ilk katılan kimsenin kuyruktan ilk önce çıkacak olan kimse olmasıdır. İşte FIFO prensibi aynen bu şekilde işler ve kuyruk veri yapısına ilk giren eleman çıkma konusunda en öncelikli elemandır.


Queue veri yapısı temel olarak enqueue, dequeue ve peek fonksiyonlarını içerir. Queue veri yapısının enqueue ve dequeue fonksiyonları, Stack veri yapısını sırasıyla push ve pop fonksiyonları ile aynı amaca yönelik çalışır. Peek fonksiyonu ise hem Queue hem de Stack veri yapılarında aynı amaca yönelik olarak görev yapar.


Enqueue            ->          Kuyruğa bir eleman ekler.

Dequeue -> Kuyruğun sıradaki elemanını teslim eder, ilgili elemanı kuyruktan çıkarır.

Peek                   ->          Kuyruğun sıradaki elemanını teslim eder.


Queue veri yapısı oluştururken array kullanabileceğimiz gibi bir başka veri yapısı olan linked list’i kullanmak ta bir alternatif olabilir.  RAM uzayında daha özgür bir çalışma alanı elde edebilmek için linked list kullanmayı tercih ederim.


template<class T>
struct queueNode
{
       T data;
       queueNode *next = NULL;
};


Queue için tek yönlü bir bağlı liste düğümü bana yeterli olacaktır. Düğüm yapısının template olarak tanımlanması da ileride yazacağım kuyruk veri yapısının generic bir biçimde kullanılabilmesinin önünü açacaktır.


Düğüm yapısını tanımladığıma göre artık bir linked list sahibi olabilirim. Kuyruğa eleman eklerken ilgili elemanı kuyruğun en sonuna atacağımdan ötürü linked list’in en sonuna bir düğüm ekleme işlemi yapacağım. Yani enqueue fonksiyonu içinde öncelikle kuyruğun en sonundaki elemanı bulamam ve kuyruğun en sonuna yeni eklenecek elemanı koymam gerekiyor.


template<class T>
class queueDataStucture
{

private:

       queueNode<T> *first;

public:

       queueDataStucture() {}
       ~queueDataStucture() {}

       bool queueIsEmpty() {
             return first == NULL;
       }

       void enqueue(T data) {

             queueNode<T> *node = new queueNode<T>();
             node->data = data;

             if (queueIsEmpty())
             {
                    first = node;
             }
             else
             {
                    queueNode<T> *temp = first;
                    while (temp->next != NULL)
                           temp = temp->next;

                    temp->next = node;
             }
       }

       T dequeue() {
             if (queueIsEmpty())
                    throw exception("queue is empty!");

             queueNode<T> *temp = first;
             first = first->next;
             T data = temp->data;
             delete temp;

             return data;
       }

       T peek() {
             if (queueIsEmpty())
                    throw exception("queue is empty!");

             return first->data;
       }
};


Burada adeta bir ışık niteliğinde olan son derece basit bir kontrol ifadesinden ibaret queueIsEmpty fonksiyonuna bakarsak return fist == NULL komutunu göreceğiz. Sınıfın içinde private olarak duran first, queueNode<T> türündeki bir varlığın bellek adresine işaret eden bir pointer olup kuyruğun ilk elemanını tutmak ile görevlidir. Haliyle kuyruğun ilk elemanı NULL ise, kuyruk boş demektir.


Linked List ile çalışmanın belki en kritik noktası ilk elemanı RAM uzayında kaybetmemektir. Veriler birbirine pointer ile bağlı olacağından ötürü ilk elemanın kaybedilmesi kendisinden sonra gelen tüm elemanların da RAM uzayında kaybolması anlamına gelir. Dolayısıyla dequeue fonksiyonu ile kuyruğun en başındaki elemanı geri döndürürken bu elemanı silmeden evvel yedeklemeli, tuttuğu veriyi almalı ve en tepe elemana kendisinden bir sonra gelen elemanı atamalıyım. Böylelikle en tepedeki eleman kuyruktan çıkmış olurken, bir sonraki eleman en tepeye oturmuş olacaktır.


Testimizi yapmak için kuyruk veri yapısını integer türünde örnekleyip sırasıyla 10, 23, 54 ve -20 değerlerini kuyruğa alalım.


queueDataStucture<int> queue = queueDataStucture<int>();
queue.enqueue(10);
queue.enqueue(23);
queue.enqueue(54);
queue.enqueue(-20);


Tüm kuyruk içeriğini alabilmek için while döngüsünden yararlanırken şart ifadesi olarak kuyruğun boş olup olmadığını döndüren queueIsEmpty fonksiyonundan faydalanabilirim. Bir sonraki elemana geçmek için kullanabileceğim iki yoldan birincisi sıradaki elemanı ya doğrudan dequeue fonksiyonu ile almak ya da peek fonksiyonu ile alıp dequeue fonksiyonunu çağırmak olur.


while (!queue.queueIsEmpty())
{
      int next = queue.dequeue();
      cout << next << endl;

      //sırasıyla 10, 23, 54 ve -20 yazılır.
     //tüm queue boşalmış olur.
}

if (queue.queueIsEmpty()) {
       queue.enqueue(100);
       queue.enqueue(200);
}

while (!queue.queueIsEmpty())
{
       int next = queue.peek();
       cout << next << endl;
       queue.dequeue();

       //sırasıyla 100 ve 200 yazılır.
      //queue boşalmış olur.
}


Böylelikle FIFO ve Queue üzerine yazdığım makalenin de sonuna gelmiş olduk. Başka bir makalede buluşana dek kendinize iyi bakın, hatasız kodlamalar dilerim.