VERİ YAPILARI VE ALGORİTMALAR: STACK VERİ YAPISI

Veri yapısı verileri organize etme, saklama, işleme yöntemlerini tanımlayan çeşitli veri gösterimleridir. Bundan yola çıkarak verilerin etkin bir şekilde yönetilmesi için uygun veri yapılarının seçilmesi ve kullanılması gerektiği söylenebilir.

Bilgisayar bilimlerinde kullanılan en temel veri yapılarından biri, stack (yığın) veri yapısıdır. Stack veri yapısı tıpkı adından anlaşıldığı gibi bir yığın olarak düşünülebilir. Bu veri yapısının en önemli özelliği LIFO (Last In, First Out) yani “son giren ilk çıkar” prensibiyle çalışmasıdır.

Kolay anlaşılabilmesi için üst üste yığılmış bir miktar tabak olduğunu hayal edelim. Bu tabak yığınından ihtiyacımız doğrultusunda bir tabak alabilir ve işimiz bittikten sonra tabağı yerine koyabiliriz. Peki bu yığından, tabağı nereden almayı tercih ettik ve koyduğumuz tabağı bu yığında nereye koyduk? Tabağı, tabak yığının en üstünden alıp yine en üstüne koymak elbette hemen herkesin tercih edeceği bir davranıştır. Örnekte görüldüğü gibi yığın üzerinde gerçekleştirilen işlemler, yığının en üst kısmındaki ögeyle gerçekleştirilir. Bu, stack (yığın) veri yapısının mantığını anlatan temsili bir örnektir ve bu örnek stack veri yapısının, verileri nasıl organize ettiğini, verilerin nasıl saklandığını ve veriler üzerinde nasıl işlemler gerçekleştirilebileceğini açıklar. Örneğe göre; tabakların her biri bir veriyi, üst üste konulmuş tabaklar bütünü de bir diziyi temsil eder ve bunlar bilgisayarın ilgili memory bölgelerinde saklanır.

Stack veri yapısındaki temel işlemler şunlardır:

1. Push: Yığına eleman eklemeyi sağlar. Yeni eleman, yığının en üstüne eklenir. Eğer yığın doluysa ekleme işlemi gerçekleştirilmez ve program hata döndürür.
2. Pop: Yığından eleman çıkarmayı sağlar. Yığından çıkarılmak istenen eleman, yığının en üstündeki elemandır. Eğer yığın boşsa eleman çıkarma işlemi de yapılamaz ve program hata döndürür.
3. Peek/Top: Yığının en üstteki elemanını verir.
4. getCount: Yığının içerdiği eleman sayısını verir.
5. isEmpty: Yığının boş olup olmadığını verir.
6. isFull: Yığının dolu olup olmadığını verir.

Stack veri yapısının temel mantığını anladıysak nerelerde kullanıldığına göz atalım:

• Programlama dillerinde kullandığımız fonksiyon yapıları stack veri yapısından yararlanır. Fonksiyon çağrıldığında, her çağrının yerel değişkenleri ve geri dönüş adresleri stack’te saklanır ve fonksiyon sona erdiğinde stack’ten çıkarılır.
• Birçok uygulamada gördüğümüz, basitçe Ctrl+Z ile gerçekleştirdiğimiz, undo (geri alma) işlemi de stack veri yapısı ile yapılır. Kullanıcının yaptığı her işlem stack’e eklenir ve geri alma işlemiyle, yapılan son işlem yani stack’e eklenen son veri, çıkarılarak geri alma işlemi gerçekleştirilir.
• Derleyicilerin, kaynak kod işlemesinde birçok noktada stack kullanımına rastlarız. Sözdizimsel analiz aşamasında dilin kurallarını kontrol etmek, bir hata meydana geldiğinde programın hangi fonksiyonları çağırdığını göstermek, derleyicinin kaynak kodu parçalara ayırırken (tokenization) her bir token’ı stack’e ekleyip işleme alması, döngü yapılarının kontrolü bunlardan sadece birkaçıdır.
• Oyunlarda, karakterin veya nesnelerin durumlarını yönetmek için stack kullanılabilir. Bir karakterin hareketi veya envanter eylemleri stack üzerinde saklanabilir.
• Zaman zaman stack veri yapısı, diğer veri yapıları veya algoritmalar ile birlikte de kullanılabilir.

Stack veri yapısının avantajlarından şu şekilde bahsedebiliriz;

• Stack veri yapısı, O(1) zaman karmaşıklığına sahiptir ve özellikle yüksek performans gerektiren durumlar için ideal bir seçenektir.
• Anlaşılması ve uygulanması basit olması sebebiyle geliştiricilerin uygulamaları daha hızlı bir şekilde geliştirmesine olanak tanır.
• Boyut genellikle sadece gerekli olduğu kadar yer kapladığı için hafıza kullanımı açısından verimlidir. Ayrıca bu özelliği, stack veri yapısının hafif ve düşük maliyetli olduğuna da işaret eder.

Buna karşın dezavantajlı yanları da vardır;

• Boyut, dinamik olmadığı için stack dolduğunda (stack overflow) eleman ekleme mümkün olmaz. Özellikle büyük veri setlerinde, istenmeyen sorunlara sebep olabilir.
• Stack, yalnızca en üstteki elemana erişime izin verir. Bu, belirli bir elemana doğrudan erişimi zorlaştırır.
• Büyük veri setleriyle çalışırken stack üzerinde yapılan işlemler yavaşlayabilir. Özellikle çok sayıda fonksiyon çağrısı veya derinlemesine döngü yapıları varsa performans sorunları ortaya çıkabilir.

Stack veri yapısından, özelliklerinden, avantaj/dezavantajlarından ve kullanım alanlarından bahsettik. Son olarak stack veri yapısını Java kullanarak uygulayalım.

Not: Bu örnekte yazılan bütün kodlar, 24 Eylül 2024 itibariyle Java’nın son sürümü olan Java 22 kullanılarak ve NetBeans üzerinden yazılmaktadır.

Eğer ilk kez NetBeans kullanılyorsanız, açıldığında muhtemelen ekrana boş bir sayfa gelecektir. Kodlarımızı yazmak için öncelikle bir java dosyası açmamız gerekir. Bunun için öncelikle ekranın sol üst kenarında bulunan File seçeneğini açtıktan sonra New Project seçeneğini seçelim. Açılan sekmede sırasıyla Java With Ant ve altında bulunan Java Application’ı seçelim ve Next düğmesine tıklayalım. Ardından açılan sonraki sayfada uygulamanın adını “MyStack” olarak dolduralım ve konumunu belirleyelim. Daha sonra Finish butonuna bastığımızda DataStructure klasörü altında “MyStack.java” adında java dosyası oluşturulacaktır.

package DataStructures;

public class MyStack { 
    public static void main(String[] args) {
        System.out.println( "Veri Yapıları: Stack" ); 
    } 
}

Dosya oluşturulduğunda, bazı kodlar hazır bir şablon şeklinde açılacaktır. İlk satırda bulunan “package DataStructure” ifadesi, dosyanın bulunduğu klasörü ifade eder. MyStack class’ı ile kendi Stack yapımızı oluşturacak ve içerisine temel işlemleri ekleyeceğiz. Burada dikkat etmemiz gereken husus, dosyanın ismi ile class’ın adının aynı olmasıdır. Aynı olmaması durumunda uygulama hata verecektir. Eğer dosyanızı “stack” adıyla oluşturduysanız, uygulama kullanım esnasında hata verebilir. Bunun sebebi Java’nın kendi stack sınıfının olması ve sizin yeniden stack adıyla bir dosya oluşturmanızla birlikte karmaşıklıkların oluşabilmesinden kaynaklanabilmektedir. Sınıf parantezlerinin arasında hazır olarak gelen “public static void main(String[] args)” fonksiyonu, uygulamada çalıştırmak istediğimiz kodları yazacağımız kısımdır. Blokları arasına “System.out.println( “Veri Yapıları: Stack” );” yazarak ekrana kendi başlığımızı yazdırmış oluyoruz.

package DataStructures;

public class MyStack { 
    private int indeks;
    private final int[] dizi; 
    public static void main(String[] args) {
        System.out.println( "Veri Yapıları: Stack" ); 
    } 
}

Stack içinde birden fazla veri saklamak istediğimiz için, array türünde bir değişken tanımlayalım. Bu değişken sayesinde stack içerisinde veri saklamamız mümkün olacak. Ayrıca stack içinde yapmak istediğimiz işlemleri kendi tanımladığımız fonksiyonlar üzeirnden yapmak ve sınıfın dışından bir müdahale olmasını istemediğimiz için de dizi değişkenini private olarak tanımlamamız gerekir.

Stack’te işlemlerin her zaman en üstteki eleman üzerinde gerçekleştirildiğinden bahsettik. En üstteki elemana erişebilmek için, indeks adında bir değişken tanımlıyoruz. Indeks değişkenini, yapmak istediğimiz işlemler için bir referans noktası veya bir işaretleyici olarak düşünebiliriz. Esasen bir referans noktası, yapılmak istenen işlemin hangi indeks üzerinde gerçekleştirileceğini söyler. Stack ise 0'dan indeks’e kadar devam eden değerleri içerir.

package DataStructures;

public class MyStack { 
    private int indeks;
    private final int[] dizi;

    public MyStack(int size){
        indeks = -1;
        dizi = new int[size];
    }
    public static void main(String[] args) {
        System.out.println( "Veri Yapıları: Stack" ); 
    } 
}

Tanımladığımız indeks ve dizi değişkenlerine bir başlangıç değeri veya boyut atamadık. Başlangıç değerlerini ve dizi boyutu kurucu metod üzerinden yapacağız. Bu sayede kullanıcı, bizim seçtiğimiz sabit bir boyutta değil, kendi gereksinimlerine göre stack’in kapasitesini belirleyebilir. Kapasiteyi belirlemek için, yapıcı metoda “int size” parametresini göndermemiz gerekir. “main” metodunda, MyStack sınıfından bir nesne türetmek için stack’in kapasitesini belirten size parametresini de kullanmamız gerekir.

Yapıcı metotta dizi değişkenine boyut atamak dışında indeks değişkeninin başlangıç değerini de tanımlamamız gerekir. Indeks değişkenine dair, geçerli olan 2 yaygın görüş bulunmaktadır. Bu görüşler için indeks değişkeni şu şekilde yorumlanır:

• Birinci görüş “indeks = 0” değerini belirtir. Bu görüşe göre indeks, stack’te ilk boş yerin indeks değerini tutar. Eğer stack tamamen boş ise, indeks değişkeni 0 değerini alır ve ekleme/çıkarma işlemleri doğrudan bu indeks değerini alarak gerçekleşir. Sınıfımızı kullanarak türetilecek stack nesnelerinin başlangıçta tamamen boş olduklarını düşünecek olursak kurucu metotta indeks değişkeninin neden 0 değerini aldığını anlayabiliriz.
• İkinci görüşte “indeks = -1” değerini belirtir. Bu görüş, diğerinden farklı olarak stack’te son dolu yerin indeks değerini tutar. Eğer stack tamamen boş ise indeks değişkeni -1 değerini alır ve ekleme/çıkarma işlemleri indeks + 1 değeri ile gerçekleştirilir. MyStack sınıfı kullanılarak türetilecek stack nesneleri başlangıçta tamamen boş olacakları için kurucu metotta indeks değişkeninin -1 değeri alması anlaşılır olacaktır.

Bu yazıda ikinci görüş olarak bahsedilen indeks = -1 değerinin kullanımı tercih edilmektedir. Bu durumla ilgili doğru veya yanlış yaklaşım bulunmamakla beraber herkes istediği kullanımı tercih edebilir.

public int getCount(){
    /*
    * Stack'te kaç eleman olduğunu verir
    */
    int eleman_sayisi = indeks + 1;
    return eleman_sayisi;
}

getCount metodu, stack içindeki mevcut eleman sayısını döndürür. Indeks değişkeni, son dolu değerin indeks değerini tutuyordu. Öyleyse içinde 1 eleman bulunduran bir stack’te indeks değişkeni 0'dır. Eğer stack’te 2 eleman varsa indeks 1, 3 eleman varsa indeks 2 değerini alır. Öyleyse stack’teki eleman sayısı = indeks + 1'dir. return komutu ile eleman sayısını döndürebiliriz.

public bool isEmpty(){
    /**
     * Stack'in boş olup olmadığını kontrol eder.
     * Boş ise True, değil ise False değerini döndürür.
     */
    if (getCount() <= 0){
        // Dizi boş
        return True;
    }
    else{
        // Dizi boş değil
        return False;
    }
}

isEmpty metodu getCount metodunu kullanarak stack’teki eleman sayısının 0'a eşit veya 0’dan küçük olup olmadığını kontrol eder ve stack boşsa True değilse False değerini döndürür. Ayrıca bu metodu, eleman çıkarma işleminde çıkarılacak eleman kalıp kalmadığını yani stack’in boş olup olmadığını kontrol etmekte kullanacağız.

public bool isFull(){
    /**
     * Stack'in dolu olup olmadığını kontrol eder.
     * Dolu ise True, değil ise False değerini döndürür.
     */
    if (getCount() >= dizi.length){
        // Dizi dolu
        return True;
    }
    else{
        // Dizi dolu değil
        return False;
    }
}

isFull metodu stack’teki eleman sayısının dizinin kapasitesine eşit veya büyük olup olmadığını kontrol eder ve stack doluysa True değilse False değerini döndürür. getCount metodu stack’in kaç eleman içerdiğini, dizi.length ise stack’in kapasitesini ifade eder. İsFull metodunu, stack’e eleman ekleme işleminde kapasiteyi kontrol etmede yani stack’te eklenecek boş yerin olup olmadığını kontrol etmekte kullanacağız.

public void push(int value) throws Exception{
    /**
     * Stack'e eleman ekler
     */
    if (isFull() == True ){
        throw new Exception("Dizi dolu, daha fazla ekleme işlemi yapılamaz");
    }
    else{
        indeks = indeks + 1;
        dizi[indeks] = value;
    }
}

Push metodu, stack’te eleman ekleme işlemlerinde kullanılan metottur. Value parametresi, stack’e eklenecek değeri alır ve stack’te saklanmak istenilen veri türüne göre int, double, bool vb değerler içerebilir. Eleman ekleme işleminde öncelikle stack’in dolu olup olmadığı kontrol edilir. Bunun için yazılan isFull metodundan kullanılabilir. Eğer stack doluysa exception fırlatılır. Biz örnek olması ve konu hata yapıları olmadığı için bir süper sınıf olan Exception sınıfını direkt olarak kullanacağız ancak bu kullanımın tercih edilmeyen bir yol olduğunu da unutmamamız gerekir. Yerine “StackOverflowException” gibi hata yapılarının kullanımı daha uygun olur.

Indeks değişkeninin, stack’in en üstündeki değerinin indeksini sakladığını biliyoruz. Eklenecek yeni değerin, mevcut son değerin üzerinde yazılmaması için indeks değişkenini 1 arttırmamız gerekir. Böylece yeni değeri doğru indekse ekleyebiliriz.

public void pop()throws Exception{
    /*
    * Stack'ten eleman çıkarır/siler
    */
    if (isNull() == True){
        throw new Exception("Dizi boş, daha fazla çıkarma işlemi yapılamaz");
    }
    else{
        indeks = indeks - 1;
    }
}

Pop metodu stack’ten eleman silmeye yarar. Push metodunda yapılanın aksine bu metotta stack’in boş olup olmadığının kontrolü yapılır. Böylece eğer stack boş ise daha fazla silme işlemi yapılamayacağına dair bir hata döndürülebilir. Meraklısına, pop metodunda Exception yerine “StackUnderflowException” hata yapısı kullanılabileceğini söyleyelim.

Silme işleminde gerçek manada silmekten bahsedilmez. Burada mesele, ihtiyacımız olan ve istediğimiz ölçüde elemana erişebilmektir. Elemanlara erişmek için indeks değişkenini bir referans olarak kullanmak da bu amaca hizmet eder. Yani stack 0 ile indeks arasındaki verileri saklar. Diğer elemanların boş veya bir değer taşımaları anlam ifade etmez çünkü yapılacak bir işlem mevcut değerin üzerine işlenir ve eski değer saklanmamış olur. Bu yüzden silme işlemi için indeks değişkenini 1 azaltmak yeterlidir. Akla, silinen ögelere 0 değeri atamak gelebilir ancak 0 da stack’te saklanan bütün diğer veriler gibi bir değerdir.

public int peek(){
    /*
    * Stack'in en üstteki elemanının değerini verir
    */
    en_ust = dizi[indeks];
    return en_ust;
}

Peek metodu, stack’in en üstteki elemanının değerini döndürür. Bu aynı zamanda indeks değişkeninin karşılık geldiği değeri ifade eder. Indeks stack’te en üstteki elemanın indeks değerinine karşılık geliyorsa peek metodu da bu değeri geri döndürür.

public static void main(String[] args) throws Exception {
    System.out.println( "Veri Yapıları: Stack" );
    MyStack asal= new MyStack(10);
    try {
    asal.push(2);
    asal.push(3);
    asal.push(5);
    asal.push(7);
    asal.push(9);
    asal.pop();
    asal.push(11);
    asal.push(13);
    } catch(Exception ex) {
    }
    System.out.println(asal.peek());
    System.out.println(asal.getCount());
}

Main fonksiyonunda, yazdığımız MyStack sınıfını kullanarak asal sayıları depolamak için 10 eleman saklayabilen bir stack nesnesi ürettik. Stack’e sırasıyla asal sayılar, push metoduyla ekleniyor. 9 sayısı stack’e eklendiğinde asal olmadığı için çıkarılmak istenmiş ve pop metodunu kullanarak silme işlemi gerçekleştirilmiştir. Ayrıca ekleme ve silme işlemlerinde, hata kontrolü yapmak istediğimiz için bu işlemleri try bloğunun arasın gerçekleştirdik. try ve catch bloklarının ardından stack’e eklenen son elemanı ve stack’te kaç eleman olduğunu görmek için peek ve getCount metotları yazdırılmıştır.

Stack veri yapısını daha iyi yazmak için aşağıdaki örneği de inceleyebiliriz.

package DataStructures;

public class MyStack {

    private int top;  // indeks değişkenine karşılık gelir ve Stack'in son dolu elemanını tutar
    private final int[] arr;  // dizi değişkenini ifade eder

    public MyStack(int capacity) throws Exception{
        if (capacity <= 0){
        throw new Exception("Kapasite 0'dan büyük olmalı");
        }
        arr = new int[capacity];
        top = -1;
    }

    public void push(int value) throws Exception{
        /**
         * Diziye eleman ekleme işlemi yapar
         */
        if (isFull()){
            throw new Exception("Dizi dolu, daha fazla ekleme işlemi yapılamaz");
        }
        arr[++top] = value;
    }

    public void pop()throws Exception{
        /*
        * Diziden eleman çıkarma işlemi yapar
        */
        if (isNull()){
            throw new Exception("Dizi boş, daha fazla çıkarma işlemi yapılamaz");
        }
        return arr[top--];
    }

    public int getCount(){
        /*
        * Dizide kaç eleman olduğunu verir
        */
        return top + 1;
    }

    public boolean isEmpty(){
        /**
         * Stack'in boş olup olmadığını kontrol eder.
         */
        return top == -1;
    }
    public boolean isFull(){
        /**
         * Stack'in boş olup olmadığını kontrol eder.
         */
        return top == capacity - 1;
    }
    public int peek(){
        /*
        * Dizinin son elemanının değerini verir
        */
        return arr[top+1];
    }

    public static void main(String[] args) throws Exception {
        try {
            MyStack s = new MyStack(10);
            s.push(3);
            } catch(Exception ex) {
            }
            System.out.println(s.peek());
        }
}