Veri Yapıları · Ünite 3

Yığın (Stack) ve Kuyruk (Queue) Yapısı (C#)

1. Neden yığın ve kuyruk?

Array ve ArrayList veriyi gruplar ama «önce hangisi çıkacak?» sorusuna bir kural koymaz. Yığın ve kuyruk, listeye giriş–çıkış kuralı ekleyen iki basit soyutlamadır. Doğru yapıyı seçmek problemi düşünmeyi kolaylaştırır; iyi programcıyı ortalamadan ayıran becerilerden biri de budur.

2. Yığın (stack)

Yığın, ögelere yalnızca bir uçtan, yani yığının tepesinden erişilebilen listedir. Tabakları hep üstten alır, üste koyarız; bu yüzden yığına LIFO (Last In First Out, son giren ilk çıkar) yapısı denir.

• →Push (itme): tepeye öge ekler.
• →Pop (çekme): tepedeki ögeyi döndürür ve yığından siler.
• →Peek (tepe): tepedeki ögeyi döndürür ama silmez. Başka dillerde Top gibi adlar alır.

Kendi yığın sınıfımız

İşin mantığını görmek için .NET'in hazır Stack sınıfı yerine ArrayList üzerine kendi Yigin sınıfımızı yazalım. ArrayList yeni öge geldikçe kendiliğinden büyüdüğü için uygun. Tepenin indisini tutan bir sayaç var: boş yığında −1, her Push'ta 1 artar, her Pop'ta 1 azalır.

class Yigin
{
    private ArrayList liste = new ArrayList();
    private int tepe = -1;              // boş yığın

    public int Count { get { return liste.Count; } }   // salt okunur

    public void Push(object oge) { liste.Add(oge); tepe++; }

    public object Pop()
    {
        object oge = liste[tepe];
        liste.RemoveAt(tepe);
        tepe--;
        return oge;
    }

    public object Peek() { return liste[tepe]; }
    public void Clear() { liste.Clear(); tepe = -1; }
}

Örnek: palindrom kontrolü

Palindrom, tersten okunuşu da aynı olan kelimedir: kapak, radar, 101. Yığın veriyi ters sırada verdiği için bu iş için biçilmiş kaftan: kelimenin harflerini sırayla Push et, sonra Pop ederek baştan karşılaştır. Bir harf tutmazsa kelime palindrom değildir.

string kelime = "kapak";
var yigin = new Stack<char>();
foreach (char harf in kelime) yigin.Push(harf);

bool palindrom = true;
foreach (char harf in kelime)
    if (yigin.Pop() != harf) { palindrom = false; break; }

Console.WriteLine(palindrom ? "palindrom" : "palindrom değil");

3. C#'ın Stack sınıfı

Hazır Stack sınıfı (System.Collections) bir LIFO koleksiyonudur ve ICollection arayüzünü uygular. Push, Pop ve Peek'in yanında öge sayma, temizleme ve diziye aktarma metotları vardır.

Yığın oluşturmanın yolları

• →Stack dinamiktir: kapasite dolunca iki katına çıkar (10 → 20).
• →Diziden oluşturulan yığında dizinin son elemanı tepe olur. {"Ankara", "İstanbul", "İzmir"} ile kurulan yığında ilk Pop «İzmir»i verir.
• →Kitabın önerisi: yığının kapasitesini eleman sayısından bir fazla ver (20 eleman için 21).

Metotlar

Yığınla hesap yapmak

«5 + 10 + 15 + 20» gibi bir ifadeyi hesaplamak için iki yığın kullanılabilir: biri sayılar, biri operatörler için. İfade karakter karakter okunur; sayı sayılar yığınına, operatör operatörler yığınına itilir. Sayılar yığınında iki sayı birikince ikisi ve bir operatör Pop edilir, sonuç yeniden sayılar yığınına Push edilir. Sonunda yığında kalan tek sayı sonuçtur (50).

• →Peek burada işe yarar: tepedeki değer sayı mı diye bakmak için onu yığından çıkarmak gerekmez.
• →Clear: sıfıra bölme gibi bir hata olursa yığını tek seferde boşaltmak için.
• →Contains: yığında soruna yol açacak bir karakter (ör. boşluk) var mı diye kontrol etmek için.

Örnek: kelimeyi ters çevirmek

Console.Write("Metni girin: ");
string kelime = Console.ReadLine();
var harfler = new Stack<char>();
foreach (char harf in kelime) harfler.Push(harf);
while (harfler.Count > 0) Console.Write(harfler.Pop());   // son giren ilk çıkar → ters

4. Kuyruk (queue)

Kuyruk, yeni verinin arkaya eklendiği, çıkarmanın ise önden yapıldığı doğrusal yapıdır. Banka sırası gibi: işi biten çıkar, yeni gelen sona geçer. Bu yüzden kuyruğa FIFO (First In First Out, ilk giren ilk çıkar) yapısı denir. Ögeleri geliş sırasıyla saklamak, işletim sistemine ya da yazıcı biriktiricisine gönderilen işleri sıraya koymak için kullanılır.

• →Enqueue (sıraya alma): sona öge ekler.
• →Dequeue (sıradan çıkarma): en öndeki ögeyi çıkarır.
• →Peek: en öndeki ögeyi gösterir, çıkarmaz.

Kendi kuyruk sınıfımız

public class Kuyruk
{
    private ArrayList liste = new ArrayList();

    public void Enqueue(object oge) { liste.Add(oge); }   // sona ekle
    public object Dequeue()
    {
        object oge = liste[0];
        liste.RemoveAt(0);                              // önden çıkar
        return oge;
    }
    public object Peek() { return liste[0]; }
    public void Clear() { liste.Clear(); }
    public int Count { get { return liste.Count; } }
}

C#'ın Queue sınıfı ve büyüme faktörü

Kapasiteyi her dolduğunda kaç katına çıkaran sayıya büyüme faktörü denir. Varsayılanı 2'dir; constructor'a verilen ikinci sayı büyüme faktörünü değiştirir.

Örnek: taksi durağı

Bir dosyada taksiler (T) ve yolcular (Y) karışık sırayla yazılı: «Y Yolcu1, Y Yolcu2, T Taksi1…». Program her satırın ilk harfine bakıp kaydı ya taksi kuyruğuna ya yolcu kuyruğuna Enqueue eder. Sonra iki kuyruk da doluyken her turda birer Dequeue yapıp ilk gelen yolcuyu ilk gelen taksiyle eşleştirir. Biri boşalınca durur ve kalanları bildirir: taksi kaldıysa sıradaki taksi Peek ile gösterilir, yolcu kaldıysa bekleyen yolcu sayısı yazılır.

5. Öncelikli kuyruk

Bazen çıkması gereken en eski öge değil, en önemli ögedir. Ögelerin önemini belirten değere öncelik sırası denir. İşletim sistemi örneğin dosya kopyalamayı yazdırmadan önce yapmak isteyebilir. Görevler numaralanır ve küçük sayı yüksek öncelik demektir: öncelik 0, öncelik 20'den önce gelir.

• →Öncelikli kuyruktaki ögeler anahtar–değer çifti gibidir: anahtar öncelik, değer ögenin kendisi. Örnek: struct Islem { int oncelik; string ad; }
• →Sıradan bir Queue işe yaramaz, çünkü Dequeue hep ilk geleni verir.
• →Çözüm: Queue'dan türetilen bir PQueue sınıfı yazıp Dequeue'yu geçersiz kılmak (override).

Örnek: yazdırma (öncelik 1), virüs taraması (öncelik 0) ve yedekleme (öncelik 3) işleri aynı anda kuyruğa girerse ilk Dequeue virüs taramasını verir, çünkü önceliği en yüksek (sayısı en küçük) odur.

Bu not ders kitabının yerine geçmez; konu kendi cümlelerimizle, yapay zekâ desteğiyle özetlendi.