Yığıtlar ve yığıt uygulamaları
Bitişik listelerdeki eleman ekleme ve çıkarma işlemlerine kısıtlamalar getirerek, listelerde boşluklar oluşmasına yada elemanların kitle halinde yerlerinin değişmesine izin vermeyecek yapıları düşünelim. Bu yapılar bellekteki herhangi bir yere değil, sadece izin verilen yerlere ekleme ve çıkarma yapmaya olanak tanırlar. Böylece, hem bitişik listelerin sağladığı kolaylıklardan yararlanılır, hem de sorun yaratmadan ekleme ve çıkarma olanağı kazanırız.
Bitişik listeler kullanarak kısıtlı eleman ekleme ve çıkarma işlemlerinin yapılabildiği veri yapılarından birisi yığıtlardır. Yığıtlar (stacks) , ekleme ve çıkarma işlemlerinin bitişik listenin sadece bir ucunda gerçekleşebildiği listelerdir. Elemanların eklendiği ve çıkarıldığı bu uca yığıt tepesi diğer ucada yığıt bazı denir.
Gündelik hayatta fark etmeden birçok yığıt örneği ile karşılaşırız. Bir kamyona un çuvalları yüklenirken, izlenen sıra, bu çuvalları boşaltırken izlenen sıranın tam tersidir. Bu özelliğinden dolayı yığıtlara ilk giren son çıkar (İGSÇ) (FİLO) saklama sistemi adı verilir. Çuvalları kamyona yerleştirirken son taşınan çuval, hep bir öncekinin önüne konur. Boşaltma sırasında, yüklediğimiz en son çuvalı ilk önce çıkarırız. Süper marketlerde üst üste yığılı duran konserve kutularının en son konanı en üsttedir. Müşteri, kolay olduğu için en üstteki kutuyu alır. Kazara üstteki kutuyu beğenmeyip aradan bir kutu çekmek isterse, bütün kutuların tepesine devrilmesi gibi bir faciayla karşılaşır.
Yığıt Uygulamaları
Yığıtların fiziksel olarak bilgisayar belleğinde nasıl gerçeklenebileceğini görmeden önce bu yapıların programcılıkta nasıl yararlı olabileceklerini görelim.
Yığıtlar, programın içinde çağrılan yordamları veri geldikçe gerçeklemek üzere, yaygın bir şekilde kullanırlar. Bir yordamın gerçeklenmesi istendiği zaman, bilgisayar bu işi yapmak üzere işlem gücünü bu yordama yoğunlaştırır. Daha sonra, yordam tamamlanınca, yordamı çağıran komuta geri dönülür. O halde, yordam tamamlandıktan sonra sistemin nereye geri döneceğini bilmesi gerekir. Bu durum, özellikle yordam diğer bir yordamı çağırdığı zaman daha karışık bir hale gelir. Bu yordam da başka bir yordamı çağırabilir. Böylece birbirinin içine geçmiş olan yordamların her biri tamamlandığında, bir önceki yordamda kalınan yere geri dönülmesi gerekir. Karışık ve uzun programlarda geri dönülmesi gereken komutlar üst üste birikir. Biriken bu program noktaları her yordam tamamlandığında teker teker azalır. Geri dönüş noktalarını saklamak ve yeri geldikçe bu noktaları elden çıkarmak için bir sistem gereklidir.
İşte yığıtlar bu gibi durumlarda ideal bir veri yapısı oluştururlar. Her yordam çağırıldıkça, geri dönüş noktasını saklayan bir imleç yığının üstüne eklenir. Her yordam tamamlanınca da, yığıtın en üstündeki imleçteki adrese geri dönülür ve bu imleç yığıttan silinir. Gerçektende bu uygulamada geri dönüş noktalarının sırası yordamı çağıran komutların sırasının tam tersi olur. Genel olarak diyebiliriz ki, yığıtlar, geri dönüşü aynı olan bir yoldaki mihenk taşlarının tabi ki iz sürme işlemi gerçekleştirir.
Yığıtların Bellekte Gerçeklenmesi
Şimdi de yığıtların bilgisayar belleğinde nasıl bir organizasyonla gerçeklenebileceğine kısaca bakarsak. İlk işimiz bellekte yeteri kadar büyük bitişik bir liste için yer ayırmaktır. Bellekte ayrılacak olan bloğun boyutunun belirlemek oldukça önemli bir tasarım problemidir. Eğer gereğinden küçük bir alan ayrılırsa, yığıt eklemelerle dolar ve listeye yeni elemanları eklemek için yer kalmaz. Eğer çok büyük bir alan ayrılırsa bellekte gereksiz yer harcanır.
Bellek bloğunu ayırdıktan sonra ikinci iş, bloğun bir ucunu yığıtın bazı olarak belirlemektir. Burası yığıta koyulacak ilk elemanın yeri olacaktır. Yeni gelen her bir eleman bir önceki elemanın bulunduğu hücrenin yanına yerleştirildikçe yığıt diğer uca doğru büyümeye devam eder.
Bu yapı içinde yığıt başının adresinin izlenmesi için ek bir yönteme ihtiyaç vardır. Zira yığıta yeni elemanlar eklendikçe ve çıkarıldıkça, yığıt başı sürekli olarak yığıt için ayrılmış olan bellekteki bloğunda ileri geri hareket eder. O halde, bütün bu ekleme ve çıkarma işlemleri süresince yığıt başının blok içindeki yerini belirleyen bir kayıt tutmamız gerekir. Bunun için belleğin bir başka hücresinde yığıt başının adresi tutulur. Bu hücreye yığıt imleci adı verilir. Yığıta bir eleman eklendiği zaman yığıt imleci, önce bloğun boş olan ilk hücresine kaydırılır. Eklenecek elemanda bu boşluğa yerleştirilir. Listeden bir eleman silmek için ise, yığıt imlecinin gösterdiği eleman silinir, imleç bir alttaki elemanın adresi ile güncellenir.
Yığıtların kavramsal tasarımları ve bellek üzerindeki gerçek yapıları arasında pek bir fark yoktur.
Eğer, yığıt için bellekte hangi büyüklükte bir blok ayrılması gerektiği belli değilse, yığıtı bitişik liste olarak değilse, bağlı listelerde oluşturmakta yarar vardır. Bu yapı, yığıtın büyüklüğünü herhangi bir şekilde sınırlamaz. Zira bağlı listelerde, listedeki elemanlar belleğin içinde yan yana ve bitişik tek bir blokta değil, tüm belleğin içinde boş bulunan hücrelere dağıtılarak saklanırlar. Bu durum kavramsal yığıt yapısı verinin bellek içindeki gerçek yapısından çok farklı olur.
Yığıtların gerçeklenmesi için üç adet yordama ihtiyaç vardır.
1) Ekleme işlemi
2) Çıkarma işlemi
3) Yığıtın boş olup olmadığının kontrol edilmesi.
Bu yordamlar geliştirildikten sonra, programcı, artık belleğin içinde olup biten karışık işlemlerden kendini soyutlayarak programını amaçladığı doğrultuda tasarlayabilir.
Örnek:
Eskiden İstanbul‘ da Boğaz vapurları gidiş yönünde yandaki listedeki iskelelere uğrarlardı.
- Eminönü
- Üsküdar
- Kuzguncuk
Dönüşte aynı iskelelere uğrayan vapurun uğradığı iskelelere dönüş sırası ile yazdırtmak için bir yordam hazırlayalım. Yani, listedeki iskeleleri ters yönde yazdıralım.
Elimizdeki gidiş yönü iskelelerinin bağlı bir listede tutulduğunu varsayalım. Bu listenin ilk elemanını en son yazdırmak için önce baştan itibaren sıra sıra bütün elemanlara erişir ve bu elemanları kaydederiz. Listenin en sonuna varınca, yazdırma işlemine son elemandan başlayarak geri geri gideriz. Bu işlemi yapabilmek için listeyi başından itibaren tarar, erişilen adresleri tek yığıtta tutar, listenin gösterdiği adresten başlayarak yığıttaki verileri tüketinceye kadar yazdırma işlemine devam ederiz. Bu yazdırma işlemi için gösterilen yordam aşağıdaki şekildeki gibidir.
Procedure Dönüşüyaz(liste)
Assign şimdiki değer value listenin baş imleci
While (şimdiki imleç boş imleç değilken) do
Şimdiki imleç tarafından gösterilen iskelenin adresini yığıta ekle
Şimdiki imleç tarafından gösterilen iskelenin adresini gözle ve şimdiki imleci o iskelenin adresi olarak yeniden düzenle
While (yığıt boş değilken) do
Yığıttan bir iskele çıkar ve bu iskeleyi bastır
Örnek:
Yığıtın bitişik hücre bloklarından oluştuğunu varsayarak, bu yığıtın tamamen boş olma olasılığını bulunuz.
Konuyla ilgili slayt sunumu aşağıdadır. Ön izlemenin altından bilgisayarınıza indirebilirsiniz.