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.
Kriter | Dizi | Bağ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;
- Kuyruğa eklenmek üzere yeni bir bellek alanı rezerve eder.
- Yeni elemanın veri alanına saklanacak tamsayı değeri yazılır.
- Eğer kuyruk boşsa, yeni elemanın sonraki adresine NULL yazarak, bundan sonra kuyrukta başka eleman olmadığı gösterilir.
- 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.
- Son elemanı gösteren işaretçi yeni gelen elemanın bellek adresini gösterir.
- 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:
- Önce kuyruğun boş olup olmadığı kontrol edilir. Eğer kuyruk boş değilse aşağıdaki işlemler yapılır.
- 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.
- ptr‘nin gösterdiği elemanın verisi ekrana yazdırılır.
- 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.
- 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 }