Generic Priority Queue Yazalım

Queue yapıları, ilk gelen ilk çıkar (first in-first out, FIFO) mantığı ile çalışan listelerdir. C# dilinde yeralan Queue<T> sınıfı bu mantık ile çalışan bir yapıdadır.

Queue sınıfına Enqueue methodu ile yeni eleman ekleyebilir, Dequeue methodu ile de eklenmiş elemanları sırası ile okuyabiliriz.

Projelerimizde sıklıkla Queue sınıfına ihtiyaç duyarız. Örneğin, üye kaydı oluşturan kullanıcılara mail ile erişim bilgileri iletileceği durumda, her yeni oluşturulan üye kaydını bir queue‘ya ekleriz, arka planda çalışan bir servis, queue‘da eleman oldukça alır, veritabanında gerekli kayıtları oluşturduktan, yetkileri tanımladıktan, vs. sonra email gönderme işlemini yapar.

Bazı durumlarda bu senaryo yetersiz kalabilir. Özellikle queue‘ya eklenen elemanlar arasında önceliklendirme yapamadığımız için, yeni kullanıcıya gönderilecek mail ile şifresini unutan kullanıcıya gönderilecek şifre hatırlatma maili aynı önceliğe sahip oluyor.

Queue sınıfına öncelikler eklemeye karar verdik, peki nasıl yapacağız? Başlangıç olarak PriorityQueue sınıfı oluşturalım;

public class PriorityQueue<TPriority, TItem> { }</pre>

PriorityQueue sınıfına her öncelik tipi için Queue barındıracak aşağıdaki değişken tanımlamasını ekleyelim;

public class PriorityQueue<TPriority, TItem>
{
    private SortedDictionary<TPriority, Queue<TItem>> _subqueues;
}

PriorityQueue sınıfının constructor‘ında _subqueues değişkenine değer ataması yapalım;

public PriorityQueue()
{
    _subqueues = new SortedDictionary<TPriority, Queue<TItem>>();
}

Sırada bekleyen eleman var mı, varsa kaç eleman var sorularını cevaplayacak iki property ekleyelim;

public bool HasItems
{
    get { return _subqueues.Any(); }
}
public int Count
{
    get { return _subqueues.Sum(q => q.Value.Count); }
}

İlgili öncelik tipine eleman ekleme işini yapacak Enqueue method’unu yazalım;

public void Enqueue(TPriority priority, TItem item)
{
    if (!_subqueues.ContainsKey(priority))
    {
        _subqueues.Add(priority, new Queue<TItem>());
    }
 
    _subqueues[priority].Enqueue(item);
}

Eğer ilgili öncelik tipi öncelikler listesinde yoksa, ilk olarak öncelik tipine ait yeni queue oluşturuluyor, sonra eleman öncelik tipinin listesine ekleniyor.

Öncelik tipinin listesinden eleman okumak için gerekli Dequeue method’unu da yazalım;

public TItem Dequeue()
{
    if (_subqueues.Any())
    {
        KeyValuePair<TPriority, Queue<TItem>> first = _subqueues.First();

        TItem nextItem = first.Value.Dequeue();

        if (!first.Value.Any())
        {
            _subqueues.Remove(first.Key);
        }

        return nextItem;
    }
    else
    {
        throw new InvalidOperationException("Queue'da hiç eleman yok!");
    }
}

Örnek kullanım;

var queue = new PriorityQueue<int, string>();
 
queue.Enqueue(1, "A-1");
queue.Enqueue(2, "A-2");
queue.Enqueue(3, "A-3");
queue.Enqueue(1, "B-1");
queue.Enqueue(2, "B-2");
queue.Enqueue(3, "B-3");
queue.Enqueue(1, "C-1");
queue.Enqueue(2, "C-2");
queue.Enqueue(3, "C-3");

while (queue.HasItems)
{
    Console.WriteLine(queue.Dequeue());
}

// ÇIKTI
// A-1
// B-1
// C-1
// A-2
// B-2
// C-2
// A-3
// B-3
// C-3


*Kaynak : http://www.blackwasp.co.uk/PriorityQueue.aspx*

İlgili diğer makaleler

blog comments powered by Disqus

Engin Polat hakkında

Senior Software Engineer, @Microsoft

Ada ve Ege'nin babası ;)

Kategoriler

İstatistik

Makale Adedi: 484

Creative Commons Lisansı