2. Stack (Yığın)

STACK VERİ YAPISI

    Bu yazimda sizlere stackten bahsedicem. Bir önceki yazımda linked listlerden detaylıca bahsetmiştim ve bir linked list implementasyonu yapmıştık link node classi ve list classi vardı. Link node’da tek bir nodu tanımlarken. Listte ise bu nodelar bir araya gelerek list’i olusturuyordu. Listin yapisi geregi, List class’inda insertAtFront , insertAtBack, RemoveAtBack, RemoveAtFront  metotları vardı.

    Şimdi stackin yapısından biraz bahsedelim. Stack , ilk giren son çıkar (first in last out) mantığıyla çalışır dolayısıyla son giren de ilk çıkar(last in first out), peki ne demek oluyor bu, bir bellek alanı düşünün son koyduğunuz elemana ilk öncelikle ilk koyduğunuza da son öncelikle ulaşabiliyorsunuz. Bunu günlük hayattan iki somut örnek vererek kafanızda somutlaştırıcam. 

stack ile ilgili görsel sonucu

 

  Yere üst üste dizilen kitapları düşünün. ilk önce birinci kitabi yere koyuyorsunuz daha sonra 2yi onun üzerine 3ü de bir diğerinin üzerine , bu şekilde kitaplari diziyorsunuz.  Kitapları geri almak istediğinizde ilk olarak hangisinden başlarsınız, en üsttekinden. Yani en son koyduğunuz kitabi ilk olarak alırsınız, ilk koyduğunuz kitabi yani en alttaki kitaba en son ulaşırsınız heh işte First in last out yani ilk giren son çıkmış oldu.

  İkinci bir örnek ki benim daha çok sevdiğim.. silah şarjörlerini düşünün, mermileri tek tek şarjöre doldurduğunuzu hayal edin önce birinci kurşun sonra onun üzerine ikinci üçüncü.. böyle gider.. her koyduğunuz kurşun bir diğerini daha aşağı iter ve kendisi en üstte bulunur. Tekrar boşaltmaya başladığınızda en son koyduğunuz mermiyi ilk çıkarırsınız ve  sondan başa doğru sırayla deneyebilirsiniz.(evde bir adet şarjör ve 12 adet kurşunla kendiniz de deneyebilirsiniz). işte buradaki şarjör stack , mermilerin diziliş ve geriye alınış mantığı ise ilk giren son çıkar – son giren ilk çıkardır.

   İşte stack’e de veriler aynen bu şekilde yerleşiyor ve ancak bu şekilde dışarı alınabiliyor. Buradan yola çıkarak stack’in 3 temel operasyonu olduğu sonucunu çıkarabiliriz.  Push, pop , peek. Push stack’e eleman atar. Pop eleman çeker. Peek de en üstteki elemanı gösterir. Pop ile peek’in farkı, pop elemanı çeker alır, peek ise sadece gösterir.

   Peki bu yapının avantajlari nedir ? Yani neden ilk giren son çıkar gibi bir mantıkla çalışan bir yapıyı kullanırız ?

   Asıl özelliği en son eklediğiniz veriyi ilk olarak geri almanıza yarar. Mesela internet tarayıcınızda sayfalarda geziyorsunuz. Bir yerde aa dediniz bir önceki sayfaya dönmem lazım. Ne yapıyoruz? Geri butonuna basıyoruz. Peki arkada girilen sayfaları hangi veri yapısıyla tutabilliriz? En son girilen sayfaya gitmemiz gerekmiyor mu?  Tam olarak stack kullanılacak bir örnek.

   Stack yapı olarak Link list’in kısıtlı bir versiyonudur. Yukarıda da bahsettiğimiz gibi link listte   insertAtFront , insertAtBack, RemoveAtFront,RemoveAtBack metotlari varken stackte pop, push ve peek metotları vardır. Bunları birbirleriyle eşleştirmek istersek.

  • InsertAtFront  listin başına eleman eklediğinden push ile eşdeğer.
  • RemoveFromFront da elemanı sildiğinden pop ile eşdeğerdir.

Buradan yola çıkarak eğer ki bir stack implementasyonu yapmak istersek bir önceki link list yazımızda implemente ettiğimiz list üzerinden aşağıdaki gibi bir kalıtım yapabiliriz.

 class StackInheritance : List
 {
    public StackInheritance() : base("stack")
    {
    }

    public void Push(object dataValue)
    {
      InsertAtFront(dataValue);
    }

    public object Pop()
    {
      return RemoveFromFront();
    }
 
     public bool StackIsEmpty()
    {
     return IsEmpty();
    }

    public void StackPrint()
    {
     Print();
    }
}