Enqueue | Engin Polat\'ın Windows 8 , Windows Phone 8 ve C# içerikli programcılık sitesi

Arşiv

Etiketlenen yazılar enqueue

Generic Priority Queue Yazalım

06 April 2013 Yorum yapılmamış

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 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>
{
}

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