Bilginin geliş sırasına göre, ilk önce gelen elemana ilk erişilen liste yapısına kuyruk (queue) denir.
Bu erişimde First-In-First-Out (FIFO) prensibi vardır. Yani ilk giren eleman, ilk çıkar. Örneğin sinema bileti almak için sıraya girmiş kişileri düşünebiliriz. İlk önce gelen kişi bileti daha önce alacaktır.
Queue veri yapısında, verilere iki uçtan erişim vardır. Bir uçtan eleman ekleme (enqueue), diğer uçtan eleman çıkarma (dequeue) işlemleri yapılır.
Queue tasarımı dizi veya bağlı liste ile yapılabilir. Bağlı liste kullanarak boyutu sabit olmayan bir queue oluşturabiliriz. Dizi kullanmak için ise sabit bir boyut belirlemeliyiz.
Öncelikli Kuyruk (Priority Queue)
Bazı problemlerin çözümünde doğrudan kuyruk oluşturamayız. Örneğin uçakların inişi sırasında, acil inmesi gereken uçaklar bulunabilir. Veya muayene sırasında bekleyen hastalar için farklı bir öncelik belirlenebilir.
Bu gibi senaryolarda öncelikli kuyruk ile çözüm üretilir. Öncelik sırası belirlenir ve program sırasında uygulanır.
UYGULAMA
Konuyu daha iyi anlatabilmek için, bağlı liste ile gerçekleştirilmiş bir queue uygulaması anlatacağım. İşlemler:
Eleman Ekle (enqueue)
Eleman Çıkar (dequeue)
Sıradaki Elemanı Getir (peek)
Genel anlamda queue (kuyruk) aşağıdaki gibi görünecek.
front (ön): kuyruğun önündeki elemanı gösteren işaretçi.
rear (arka): kuyruğun arkasındaki elemanı gösteren işaretçi
- Eleman Ekle (enqueue)
Eleman ekleme işlemi için enqueue (kuyruğa eklemek) terimi kulanılır. Enqueue işlemininin kodlarını görelim.
Öncelikle kuyruğun boş olduğu durumunu kontrol etmeliyiz. Eğer kuyruk boş ise (rear elemanı NULL ise) boş bir kuyruğa eleman ekleme işlemi yapacağız.
if(rear == NULL)
{
front = rear = new struct node();
rear->data = key;
}
Boş bir kuyruğa eleman eklersek enqueue(36); aşağıdaki gibi gözükecektir.
Eğer kuyruk boş değilse: yeni bir düğüm oluşturmalı ve bu düğümü kuyruğun en arkasına eklemeliyiz.
else
{
struct node* temp = new struct node();
temp->data = key;
rear->next = temp;
rear = temp;
}
Düğüm ekleme konusunu anlamakta zorlanıyorsanız, Bağlı Liste (Linked List) konusunu inceleyebilirsiniz.
Yalnızca 36 elemanını eklemiştik. Şimdi birkaç ekleme yapalım ve nasıl göründüğünü inceleyelim.
enqueue(37);
enqueue(38);
enqueue(39);
enqueue(40);
- Eleman Çıkar (dequeue)
Eleman çıkarma işlemi için dequeue (kuyruktan çıkarmak) terimi kulanılır. Dequeue işlemininin kodlarını görelim.
Öncelikle kuyrukta yalnız bir eleman olduğu durumu kontrol etmeliyiz. Eğer kuyrukta tek eleman varsa (front’un sonraki NULL ise) tek elemanı doğrudan sileceğiz.
if(front->next == NULL)
{
delete front;
front = rear = NULL;
return;
}
Bu işlemden sonra, kuyruk boş bir hâle gelecektir.
Eğer kuyrukta sadece bir eleman yoksa; en öndeki elemanı temp isminde saklamalı, bir sonraki elemanı yeni front elemanı olarak atamalı, son olarak sakladığımız elemanı silmeliyiz.
struct node* temp = front;
front = temp->next;
delete temp;
Örneğin aşağıdaki kuyruktan eleman silelim.
dequeue() işlemini uyguladığımızda, tek eleman olmadığı için if bloğuna girmez.
struct node* temp = front;
front = temp->next;
delete temp;
Kuyruğun sol hâli aşağıdaki gibi olacaktır.
Birkaç işlem daha uygulayalım.
dequeue();
dequeue();
enqueue(41);
enqueue(42);
dequeue();
enqueue(43);
- Sıradaki Elemanı Getir (peek)
Sıradaki eleman, front olarak tuttuğumuz düğüm demektir. Dolayısıyla front düğümünün değerini return ile döndürürsek, silme işlemi uygulamadan sıradaki elemanı elde ederiz. Avantajları: Geliş sırasına göre hizmet verilmesi gereken senaryolarda avantajlıdır. Üretici-tüketici problemlerinde fayda sağlar. Hastanelerde, uçakların inişinde, araç geçişlerinde öncelikli kuyruk kullanılabilir. Dezavantajları: Üzerinde arama yapmak zahmetlidir. En baştan başlanıp ilerlemek gerekir. Kuyruğun aralarına eleman eklemek karmaşıktır. Kullanım Alanları: İşletim sistemlerinde çalışma önceliği kuyruk ile yapılır. Ağ yazıcılarında, belgeler öncelikli kuyruk ile çalışır. Asansör yazılımı kuyruk ile yapılabilir. Sonuç Bu yazımda queue (kuyruk) veri yapısına ve bağlı liste üzerinde uygulamasına değindim. Veri yapısının mantığı anlaşılırsa kolaylıkla dizi ile uygulanabilir.