Yığınlar

Bu yazı BLM212 Veri Yapıları dersinin yığın konusu için hazırlanmış bir çalışma dosyası. Ders notlarından yola çıkılarak yapay zekâ ile derlendi ve düzenlendi. Erteleme bölümündeki çevirici kendi yazdığın ifadeyi işliyor — o bölümün iddiası bir operatörün neye benzediği değil ne zaman kullanıldığı üzerine, ve kuralı gerçekten kavrayıp kavramadığını sınayan şey kendi ifadeni yazmak.

Yığın nedir?

Yığın, verilerin eklenmesinin ve silinmesinin tepe (top) adı verilen tek bir uçla kısıtlandığı doğrusal listedir. Kısıtlı bir listedir: genel doğrusal listede her noktadan ekleme yapılabilirken burada yalnızca o uçtan yapılabilir.

Sezgisel tanımı şu: yalnızca en üste bir nesne ekleyip en üstten çıkarabildiğiniz her durum bir yığındır. Alttaki bir nesneyi almak istiyorsanız, önce üstündekilerin hepsini kaldırmanız gerekir.

Kısıtlı liste

Ekleme ve silme yalnızca tek uçtan. Genel doğrusal listede ikisi de her noktadan yapılabilir.

LIFO

Last In – First Out. Bir dizi veriyi yığına koyup çıkarırsanız sıra tersine döner.

Overflow

Yeni eleman için yer yok. Push öncesinde kontrol edilmeli.

Underflow

Boş yığında pop denemesi. Pop öncesinde kontrol edilmeli.

Sekiz işlem

Ders kitabının tanımladığı sekiz işlem, herhangi bir temel yığın problemini çözmeye yeter. Uygulama daha fazlasını gerektiriyorsa kolayca eklenebilir.

createStack

Dinamik bellekte baş düğüm ayırır; top = null, count = 0 yapıp adresini döndürür.

pushStack

Tepeye bir eleman ekler. Önce yığın dolu mu diye bakılır.

popStack

Tepedekini alır ve siler. Önce yığın boş mu diye bakılır.

stackTop

Tepedekini kopyalar, silmez. Mantığı pop ile aynı — sadece silme kısmı yok.

emptyStack

Yığın boş mu? Veri gizleme için gerekli: çağıran program baş yapısına erişemeyebilir.

fullStack

Yer kaldı mı? Dinamik bellekte "dolu", ancak bellek tükendiğinde olur.

stackCount

Yığındaki eleman sayısı — baş yapısındaki sayaçtan okunur.

destroyStack

Tüm düğümleri, sonra baş yapısını sisteme geri verir; null döndürür.

pushStack overflow kontrolüyle açılır ve o geçmeden başka hiçbir şey yapmaz:

Algorithm pushStack (stack, data)
1 if (stack full)
   1  success = false
2 else
   1  allocate (newPtr)
   2  newPtr->data = data
   3  newPtr->next = stack->top      // önce yeni düğümün bağı
   4  stack->top   = newPtr          // sonra tepe işaretçisi
   5  stack->count = stack->count + 1
   6  success = true
3 return success

İşaretli iki satır, bağlı listedeki "başa ekleme" ile birebir aynı — yazılma sırası dahil. popStack de "ilk düğümü silme"nin adı değişmiş hâli:

Algorithm popStack (stack, dataOut)
1 if (stack empty)
   1  success = false
2 else
   1  dltPtr       = stack->top
   2  dataOut      = stack->top->data
   3  stack->top   = stack->top->next   // önce zinciri kurtar
   4  stack->count = stack->count - 1
   5  recycle (dltPtr)                  // sonra düğümü geri ver
   6  success = true
3 return success

Yani yığın aslında yeni bir konu değil. Bağlı listede öğrendiğin iki işlem, başka hiçbir noktaya izin verilmemiş hâlde karşına çıkıyor — ve yığını yararlı kılan şey tam olarak o yasak. stackTop ise popStack'in silme kısmı çıkarılmış hâli: boşluk kontrolü ve kopyalama kalır, 1, 3 ve 5. satırlar gider.

İki gerçekleştirme

Yığının maksimum boyutu program yazılmadan önce hesaplanabiliyorsa, dizi gerçekleştirmesi bağlı listeden hem daha verimli hem de çok daha anlaşılırdır. Hesaplanamıyorsa bağlı liste.

Dizi gerçekleştirmesinde üç şey değişir: top işaretçi değil indeks olur, yanında maksimum eleman sayısı tutulur ve next alanı ortadan kalkar.

Bellek ayırmadan akılda kalması gereken bir ayrıntı: calloc(n, size) de malloc da bellek ayırıp başlangıç adresini döndürür; fark şu ki calloc ayırdığı hücreleri sıfırlar, malloc sıfırlamaz. malloc ile yeni ayrılmış bir hücreyi yazmadan okursanız çöp (garbage) değer alırsınız.

Dört uygulama ve tersine çevirme

Yığın uygulamaları dört geniş aileye ayrılır. Dördünün de altındaki sebep aynı: bir şeyi şimdi kullanamıyoruz ve sonra ters sırada lazım olacak.

Tersine çevirme

Veri sırasını ters çevirmek. Listeyi tersten yazdırma, ondalık sayıyı ikiliye çevirme.

Ayrıştırma

Veriyi sonra işlenmek üzere bağımsız parçalara ayırmak. Derleyicilerin ilk aşaması.

Erteleme

Verinin kullanımını daha sonraki bir noktaya ertelemek. Infix→postfix ve postfix hesaplama.

Geri izsürme

Karar noktalarını saklayıp çıkmaza girince en yakın karara dönmek.

Ondalıktan ikiliye

Bir sayıyı ikiliye çevirmek için sürekli 2'ye böler, kalanları yazarsınız. Sorun şu: kalanlar ters sırada üretilir. Üretildiği gibi basıldığında 19 sayısı 11001 çıkar; doğru cevap 10011'dir.

Programda dikkat edilecek bir nokta daha var: bu tür programlarda yığın yapısına asla doğrudan başvurulmaz. Tüm referanslar yığın ADT'sinin arayüzünden geçer. Kapsülleme ve yeniden kullanılabilirliğin pratikteki karşılığı budur.

Ayrıştırma

Ayrıştırma, veriyi daha sonra işlenmek üzere bağımsız parçalara ayırmaktır. Bir derleyici kaynak programı makine diline çevirmeden önce onu anahtar kelimelere, adlara ve simgelere — token'lara — ayırmak zorundadır.

Klasik ödev problemi, bir cebirsel ifadedeki eşleştirilmemiş parantezlerdir. Algoritma tek cümle — açılanı yığına it, kapanınca çek — ama üç ayrı biçimde sonlanır.

Aynı mantık süslü ve köşeli parantezlere de genişletilir: yığına hangi tür parantezin itildiği de saklanır ve kapanışta iki tür birbirine karşı kontrol edilir.

Erteleme

Bir uygulamanın mantığı çoğu zaman bir değerin kullanımının daha sonraki bir noktaya ertelenmesini gerektirir. Aritmetik ifadeler bunun en temiz örneği ve üç gösterimle yazılırlar:

Prefix

+ a b — operatör operandlardan önce gelir.

Infix

a + b — operatör arada durur. İnsanların yazdığı biçim.

Postfix

a b + — operatör operandlardan sonra gelir.

Infix gösterimin sakıncası şu: değerlendirme sırasını kontrol etmek için parantez gerekir, üstelik iki öncelik sınıfı vardır. Postfix ve prefix'te parantez hiç gerekmez, tek bir değerlendirme kuralı vardır. Derleyicilerin kaynak kodu değerlendirmeden önce postfix'e çevirmesinin sebebi budur — dönüşüm operandları operatörlerden ayırır.

Öncelik isteğe bağlı değil. A*B+C için iki aday postfix var, ABC*+ ve AB*C+; doğru olanı ikinci yapan şey aritmetik önceliktir, yani çarpmanın toplamadan önce gelmesi. Öncelik kuralı olmadan dönüşüm tek anlamlı değildir.

Elle dönüşüm

1. Aritmetik öncelikleri kullanarak ifadeyi tamamen parantezli hâle getir.
2. En içteki ifadeden başlayarak her parantezin içini postfix'e çevir; operatörü o parantezin kapanışının önüne taşı.
3. Bütün parantezleri at.

A + B * C  →  ( A + ( B * C ) )  →  ( A ( B C * ) + )  →  A B C * +

Elle yapmak için iyi, bilgisayara yaptırmak için fazla dolambaçlı. Algoritmik yöntem bunun yerine yığın kullanır.

Yığınla dönüşüm

• Operand doğrudan çıktı ifadesine kopyalanır.
• Operatör yığına itilir.
• Sonraki operand yine çıktıya kopyalanır.
• Sonraki operatörün önceliği yığının tepesindekinden yüksekse itilir; değilse yığındaki çekilip çıktıya yazılır, sonra yenisi itilir.
• Son operand çıktıya kopyalanana kadar tekrarlanır.
• Yığında kalan operatörler çekilip çıktıya yazılır.

Bir incelik daha var. Düşük ya da eşit öncelikli bir operatör tepeyi çıkmaya zorladıysa yeni tepeye de bakılır — o da yüksek ya da eşit öncelikliyse o da çekilir. Yani yeni operatör itilmeden önce birkaç operatör çıktıya gidebilir.

Öncelik 2

* /

Öncelik 1

+ −

Öncelik 0

( — yığından hiçbir şey çıkarmaz; kendisi ancak ) görülünce atılır.

İkinci sekme aynı yığını ters yönde çalıştırır. Postfix'te operandlar operatörlerden önce geldiği için bu sefer kullanımı ertelenmesi gereken şey operatörler değil operandlardır: her operand yığına itilir, bir operatör görüldüğünde tepeden iki operand çekilir, işlem yapılır ve sonuç geri itilir.

Geri izsürme

Geri izsürme, bir başlangıç noktasından belirli bir hedefe giden uygun bir yolu bulma yöntemidir. Karar analizinde, uzman sistemlerde ve bilgisayar oyunlarında yaygındır.

"En yakın karar noktasına dön" cümlesi bir LIFO ifadesidir: en son kaydedilen karar noktası, ilk geri dönülecek olandır. Veri yapısının yığın olmasının sebebi budur.

Yığına neyin itileceği sonunda ne istediğine bağlı. Yalnızca hedefi bulmak yeterliyse sadece dallanma noktaları itilir. Hedefe giden yolun yazdırılması da gerekiyorsa geçerli yoldaki düğümler de itilmelidir — ve artık yığında iki farklı türde şey bulunduğu için her birine hangisi olduğunu söyleyen bir bayrak gerekir: yol düğümü (path token) mü, geri dönüş noktası (backtracking token) mu.

Yığın ve alt yordamlar

Yığın yalnızca senin yazdığın bir veri yapısı değil. Bilgisayarın alt program çağrılarını yürütme biçiminin ta kendisi: tüm parametreler çağıran programdan alt yordama ve tersine bir yığın üzerinden aktarılır.

İşlemcinin genel amaçlı register'ları hem çağıran program hem de alt yordam tarafından ayrı ayrı kullanılır, bu yüzden içeriklerinin çağrı boyunca korunması gerekir — frame'in ② numaralı parçası bu iş içindir.

Özyinelemenin bedeli de burada duruyor. Her özyinelemeli çağrı yeni bir stack frame demektir ve hepsi aynı anda bellektedir: factorial(3) üç frame üretir. Özyineleme dersinde "hem zaman hem bellek maliyeti getirir" denirken bellek kısmıyla kastedilen buydu.

Kendini sına