Yığın Veri Yapısı (Stack)

Yığın, verilerin bilgisayarda saklanması için kullanılan bir veri yapısıdır. Yığına ilk giren veri en son çıkar. Bilgisayar bilimlerinde bu kullanım FILO (First-In-Last-Out) veya LIFO (Last-In-First-Out) olarak bilinir. Bunu aklınızda, tek şeritli bir park yerine ilk park eden aracın en son çıkmak zorunda olması olarak canlandırabilirsiniz. Yığın veri yapısının bilgisayar bilimlerinde çok geniş bir kullanımı vardır. Örneğin işletim sistemleri, üst üste çağrılan ve kapatılan fonksiyonları doğru bir hizada kullanmak için yığın veri yapısını kullanır.

Örneğin bir f fonksiyonunun içinden bir g fonksiyonu, g fonksiyonunun içinden de bir h fonksiyonu çağrılsın:

f()
{
 ...
 g()
 ...
}

g()
{
 ...
 h()
 ...
}

f fonksiyonun içinden g fonksiyonuna gidilirken, işletim sistemi f fonksiyonuna geri dönebilmek için fonksiyonun hafızadaki konumunu bir yığın yapısı içinde saklar. Aynı durum g fonksiyonundan h fonksiyonuna gidildiğinde de geçerlidir. Bu durumda h fonksiyonuna gelindiğinde yığının alt tabakasında f fonksiyonunun adresi, onun üstünde de g fonksiyonunun adresi bulunur. Yığının yalnızca en üst tabakasındaki veriye ulaşılabilir. Böylece h fonksiyonu tamamlandığında yığının üst tabakasındaki g fonksiyonuna dönülür (yığından alınan veri yığından silinir, bundan dolayı g fonksiyonunun adresi yığından alındığında yığında sadece f fonksiyonunun adresi kalır), aynı şekilde g fonksiyonu tamamlandığında da yığının üstünden alınan f fonksiyonunun adresine dönülür. İşletim sistemi bu şekilde fonksiyon hiyerarşisini sağlar.

STACK (YIĞIN)

Veri Yapısını Oluşturma

Yığın veri yapısı için bir dizi, bu dizinin boyutunu belirten bir değişken ve yığının tepesindeki elemanın indisini tutacak bir değişkene ihtiyacımız var. Bunları bir yapı (struct) içinde tutalım:

Yukarıda, içinde int veri tipinde elemanlar tutan bir yığın yapısı oluşturduk. Ancak siz isterseniz herhangi bir veri tipinde (char, double, kendi oluşturduğunuz bir yapı vs.) yığın yapısı oluşturabilirsiniz. Yukarıda diziyi dinamik olarak oluşturmak için yapının içinde diziyi doğrudan değil de dizinin adresini tuttuk. Siz isterseniz diziyi yapının içinde int st[100]; gibi statik olarak da tanımlayabilirsiniz; bu durumda yığın boyutu hep sabit kalır. (Eğer diziyi statik tanımlarsanız, aşağıdaki isStackFull ve isStackEmpty fonksiyonlarındaki realloc fonksiyonunu içinde barındıran blokları silmelisiniz.)

Yapıyı oluşturduktan sonra, yığını ilklendirecek (initializing) bir fonksiyon yazalım:

Görüldüğü gibi yapıyı, ilklendirme fonksiyonuna adresiyle gönderiyoruz. Genellikle C dilinde bir yapıyı (veya herhangi büyük bir değişkeni) bir fonksiyona kopyasıyla göndermek yerine adresiyle göndermeyi tercih ederiz. Bunun sebebi hem yerden kazanç sağlamak hem de fonksiyona gönderdiğimiz veriyi değiştirdiğimizde etkinin kalıcı olmasını sağlamak.

Yığın veri yapısında kullanılan temel modüller; yığının doluluğunu ve boşluğunu kontrol etmek, yığına veri eklemek ve yığından veri çekmek olarak sayılabilir. Şimdi bu modülleri teker teker inceleyelim:

Yığının Doluluğunu/Boşluğunu Kontrol Etme

Bir yığına veri eklemeden önce yığının dolup dolmadığını kontrol etmemiz gerekir. Aksi durumda yığında taşma olabilir. Aynı şekilde yığından veri çekmeden önce yığının boş olmadığından emin olmamız gerekir, içinde veri olmayan bir yığından veri çekemeyiz.

Yığına Veri Ekleme

Yığına veri eklemek, bilgisayar bilimleri terminolojisinde push olarak bilinir. Bir yığına veri eklerken, yeni veriyi yığının en üstündeki elemanın bir üstüne yerleştirmemiz gerekir. Ayrıca taşma olasılığına karşın, veriyi eklemeden önce yığın dizisinin dolup dolmadığını kontrol etmemiz gerekir.

Yığından Veri Çekme

Yığından veri çekmek, bilgisayar bilimleri terminolojisinde pop olarak bilinir. Yığından veri çektiğimizde, yığının en üstündeki veri yığından silinip bize getirilir. Yığından veri çekmeden önce yığının boş olmadığından emin olmamız gerekir.

Uygulama

Ana fonksiyonun içinde yığını oluşturup ilklendirelim ve kullanıcıya seçenekler sunalım:

Kullanıcı önce sırasıyla 1, 9, 2 ve 3 değerlerini yığına eklesin ve ardından yığın değerleri bastırılsın; daha sonra da iki değer üst üste yığından alınsın ve yığın yeniden bastırılsın:

Bütün kodlara ulaşmak için tıklayın.

Veri Yapısı

Eleman Ekleme: θ(1) (yalnızca dizinin en sonuna eklenebilir)

Eleman Silme: θ(1) (yalnızca dizinin son elemanı silinebilir)

Eleman Arama: Uygun değil.