08
Oca
2021

C++ ile kuyruk (queue) veri yapısı

Tanım

Aynı tip veriler kümesinin düzenli bir şekilde tutulması için dizi, bağlı liste gibi doğrusal veri yapıları kullanılır. Bu veri yapılarında dizinin veya bağlı listenin sırasına yeni veri ekleme, istenen bir veriyi çıkarma işlemini yapmak mümkündür.

Kuyruk veri yapısında, yeni eleman ekleme ve çıkarma işlemi FIFO (First In First Out/İlk giren ilk çıkar) kuralı ile gerçekleşir. Yani kuyruğa her zaman ilk eklenen eleman ilk önce çıkartılır. Bu işlem, banka kuyruğunda bekleyen insanlara benzer. Kuyrukta bekleyenler arasında kuyruğa ilk giren kişi her zaman ilk önce kuyruktan çıkar.

Kuyruğa eleman ekleme işlemi enqueue() fonksiyonu ile, eleman çıkarma işlemi ise dequeue() fonksiyonu ile gerçekleştirilir.

Bir kuyruk veri yapısı; dizi veya bağlı liste veri yapıları kullanılarak oluşturulabilir.

KriterDiziBağlı Liste
BoyutÖn tanımlıdır. Çalışma zamanında değiştirilemez.Boyutu her zaman eleman sayısına eşittir, yani çalışma zamanında sürekli değişebilir.
Bellek alanıFiziksel olarak ardışık bellek alanı gerekir.Bellekte dağınık bir şekilde yerleşebilir.
Elemanların sırasıDizinin indeks numarası ile tüm elemanlara erişilebilir.Bir sonraki elemanın bellek adresi bilgisi bir önceki eleman tarafından tutulur.

Kaynak kod

Burada yalnızca bir tamsayı değer verisi taşıyan bir kuyruk veri yapısı bağlı liste kullanılarak oluşturulmuştur. Bunun için bu tipte veri yapısının tanımlanması gerekir.

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

Burada, eleman adında yeni bir veri yapısı tanımlanmıştır. Bu yapı bir adet tamsayı veri ve bir adet de işaretçi depolamaktadır. İşaretçi, yine eleman tipinde bir başka veri yapısının bellekteki başlangıç adresini göstermektedir.

eleman *son = new eleman;
int kuyrukboyutu = 0;

Yukarıda; son adında global bir işaretçi ve kuyruğun eleman sayısını tutacak kuyrukboyutu tamsayı değişkeni tanımlanmıştır. son işaretçisi her zaman kuyruğa son giren elemanı gösterecektir.

enqueue(int data)
{
  eleman* yeni = new eleman;
  yeni->veri = data;
  if(kuyrukboyutu==0)
  {
    yeni->sonraki = NULL;
  }
  else
  {
    yeni->sonraki = son;
  }
  son = yeni;
  kuyrukboyutu++;
  cout<<data<<" eklendi. Kuyruk boyutu: "<<kuyrukboyutu<<endl;
}

Yukarıdaki enqueue() fonksiyonu ile adım adım;

  1. Kuyruğa eklenmek üzere yeni bir bellek alanı rezerve eder.
  2. Yeni elemanın veri alanına saklanacak tamsayı değeri yazılır.
  3. Eğer kuyruk boşsa, yeni elemanın sonraki adresine NULL yazarak, bundan sonra kuyrukta başka eleman olmadığı gösterilir.
  4. Eğer kuyrukta başka eleman varsa, yeni elemanın kendinden sonraki elemanı gösteren işaretçisine kuyruğun son elemanının bellek adresi yazılır.
  5. Son elemanı gösteren işaretçi yeni gelen elemanın bellek adresini gösterir.
  6. Kuyruk boyutunu tutan değişkenin değeri 1 arttırılır.
dequeue()
{
  if(kuyrukboyutu>0)
  {
    eleman *ptr = son;
    for(int i=1;i<kuyrukboyutu;i++)
    {
      ptr = ptr->sonraki;
    }
    cout<<ptr->veri<<" kuyruktan cikti."<<endl;
    ptr->sonraki = NULL;
    kuyrukboyutu--;
  }
  else
  {
    cout<<"Kuyruk zaten bos!"<<endl;
  }
}

Yukarıdaki dequeue() fonksiyonu ile adım adım:

  1. Önce kuyruğun boş olup olmadığı kontrol edilir. Eğer kuyruk boş değilse aşağıdaki işlemler yapılır.
  2. Kuyrukta gezinmek için bir ptr işaretçisi tanımlanır ve kuyruğun baştan bir önceki elemanını gösterecek şekilde kaydırılır.
  3. ptr‘nin gösterdiği elemanın verisi ekrana yazdırılır.
  4. Baştaki elemanı kuyruktan çıkarmak için ptr‘nin işaretçisi NULL’a eşitlenir, yani ilk elemanı gösteren işaretçi silinmiş olur.
  5. Kuyruk boyutunu tutan değişkenin değeri 1 azaltılır.

Kuyruğun ekrana yazdırılmasını, enqueue() ve dequeue() fonksiyonlarının örnek kullanımını da içeren kaynak kod aşağıdaki şekildedir.

#include<iostream>
using namespace std;

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

eleman *son = new eleman;
int kuyrukboyutu = 0;

enqueue(int data)
{
  eleman* yeni = new eleman;
  yeni->veri = data;
  if(kuyrukboyutu==0)
  {
    // ilk eleman© ekle
    yeni->sonraki = NULL;
  }
  else
  {
    yeni->sonraki = son;
  }
  son = yeni;
  kuyrukboyutu++;
  cout<<data<<" eklendi. Kuyruk boyutu: "<<kuyrukboyutu<<endl;
}

dequeue()
{
  if(kuyrukboyutu>0)
  {
    eleman *ptr = son;
    for(int i=1;i<kuyrukboyutu;i++)
    {
      ptr = ptr->sonraki;
    }
    cout<<ptr->veri<<" kuyruktan cikti."<<endl;
    ptr->sonraki = NULL;
    kuyrukboyutu--;
  }
  else
  {
    cout<<"kuyruk zaten bos!"<<endl;
  }
}

yazdir()
{
  eleman *ptr = son;
  cout<<"Kuyruk son durumu:"<<endl;
  for(int i=1;i<=kuyrukboyutu;i++)
  {
    cout<<i<<". eleman: "<<ptr->veri<<endl;
    ptr = ptr->sonraki;
  }
}
main()
{
  enqueue(15);     // Kuyruğa 15 ekler
  enqueue(21);     // Kuyruğa 21 ekler
  enqueue(12);     // Kuyruğa 12 ekler
  dequeue();       // Kuyruktan 15 çıkar
  enqueue(33);     // Kuyruğa 33 ekler
  dequeue();       // Kuyruktan 21 çıkar
  yazdir();        // Kuyruğu ekrana yazdır
}