2. Stack (Yığın)

1. STACK VERİ YAPISI

 Bir önceki yazımda linked listlerden detaylıca bahsetmiştim ve bir linked list implementasyonu yapmıştık. Şimdi de stack yapısından bahsedeceğim. Stack de aynı linked list gibi verileri belli bir yapıda tutan ve sunan bir veri yapısıdır. Diğer veri yapılarına göre farkı veriyi tutuş ve sunuş şeklidir. Stack Last In First Out (LIFO) mantığıyla çalışır. Yani stack’e koyduğunuz son veri ilk olarak, ilk veri de son olarak stackten alınabilir.

stack ile ilgili görsel sonucu

 

Stackin çalışmasını gündelik hayattan bir kaç örnek ile aklınızda canlandırmaya çalışayım.  Yere üst üste dizilen kitapları düşünün. ilk önce birinci kitabi yere koyarsınız daha sonra ikinciyi onun üzerine üçüncüyü şeklinde kitapları dizersiniz.  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 kitaba yani en alttaki kitaba en son ulaşırsınız . First in last out yani ilk giren son çıkmış oldu.

İkinci bir örnek olarak silah şarjörünü düşünün. Mermileri tek tek şarjöre doldurduğunuzu hayal edin. Önce birinci kurşun sonra onun üzerine ikinci üçüncü.. Bu şekilde gider.. Her koyduğunuz kurşun bir diğerini daha aşağı iter ve kendisi en üstte bulunur. Tekrar şarjörü boşaltmaya başladığınızda en son koyduğunuz mermiyi ilk çıkarırsınız ve bu şekilde devam eder (Evde bir adet şarjör ve 12 adet kurşunla kendiniz de deneyebilirsiniz). İşte buradaki şarjör stack , mermilerin diziliş ve geriye alınış mantığı ise ilk giren son çıkar – son giren ilk çıkar (LIFO)’dır.

2. STACK OPERASYONLARI

İşte stack’e de veriler aynen bu şekilde yerleşiyor ve ancak bu şekilde dışarı alınabiliyor. Buradan yola çıkarak stack’in üç temel operasyonu olduğu sonucunu çıkarabiliriz.  Push, pop ve peek. Push stack’e eleman koyar. Pop stackten en son eklenen 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.

3. STACK IMPLEMENTASYONU

 Stacki de aynı linked list gibi iki şekilde implemente edebiliriz. Biri dinamik bellek kullanarak diğeri de dizi üzerinde implemente etmektir. Dinamik bellek kullanarak yapılan implementasyonu ele alacak olursak aslında stack yapı olarak linked list’in kısıtlı bir versiyonudur. Bir önceki yazımda bahsettiğim gibi linked 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ı baştan çektiği için pop ile eşdeğerdir.

Yani bir linked listin sadece başına elemen ekleyip, başından eleman çekiyorsanız bu sizi Last in First out noktasına götürür ki bu da stack yapısıdır.

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

 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();
    }
}

4. FAYDALI SİTELER

https://www.geeksforgeeks.org/stack-data-structure/