Bölüm 7: Yığınlar

7.1Yığın ADT'si

Bir veri yapısını iki düzeyde anlatmak mümkündür. Birinci düzey, yapının ne yaptığını söyler: hangi işlemler vardır, her işlem neyi değiştirir, ne döndürür. İkinci düzey, bunun nasıl yapıldığını söyler: veriler bellekte hangi biçimde saklanır, her işlem hangi adımlarla yürür. Birinci düzeydeki tarife soyut veri tipi (abstract data type, kısaca ADT) denir. Bu kesimde yığını önce bu soyut düzeyde tanıyoruz; gerçekleme ayrıntıları bir sonraki kesimin konusudur.

7.1.1Yığın nedir?

Mutfakta üst üste dizilmiş temiz tabakları düşünelim. Yıkanan tabak her zaman en üste konur. Sofraya tabak gerektiğinde de en üstteki alınır. En alttaki tabağa ulaşmak için üstündekilerin hepsini tek tek kaldırmak gerekir. Kimse yığının ortasından tabak çekmeye kalkmaz; hem zordur hem de yığın devrilir.

Bilgisayar bilimindeki yığın (stack) tam olarak bu düzeni taklit eder. Öğeler bir sıra hâlinde tutulur, ama sıranın yalnız bir ucu kullanılabilir. Bu uca yığının üstü (top) denir. Ekleme de çıkarma da üstte yapılır. Böylece yığından çıkan öğe, her zaman o anda yığında bulunanlar arasında en son eklenmiş olandır.

LIFO ve FILO aynı davranışın iki ayrı söylenişidir. Bir yığına 1, 2, 3 sırasıyla öğe eklenip ardından üç kez çıkarma yapılırsa 3, 2, 1 sırası elde edilir. Son giren 3 ilk çıkmıştır (LIFO); ilk giren 1 ise en son çıkmıştır (FILO).

Yığın düzeni yazılımda sık karşımıza çıkar. Üç tanıdık örnek, kavramın neden bu kadar yaygın olduğunu gösterir:

• Geri al (undo): Bir metin düzenleyicide yapılan her değişiklik bir yığına eklenir. “Geri al” komutu en son yapılan değişikliği geri çevirir; bir daha basılınca ondan önceki değişikliği çevirir. Değişiklikler yapıldıkları sıranın tersiyle geri alınır.
• Tarayıcıdaki “geri” düğmesi: Ziyaret edilen sayfalar bir yığında tutulur. “Geri”ye basıldığında en son ayrılan sayfaya dönülür. Bu örnek, iki yığınla birlikte 7.3.2'de ayrıntılı işlenir.
• Fonksiyon çağrıları: main bir f fonksiyonunu, f de g'yi çağırırsa önce g biter, sonra f, en son main. En son çağrılan fonksiyon ilk biter. Programlama dilleri bu yüzden çağrıları bir yığında izler (7.3.3).

Üç örneğin ortak noktası şudur: hepsinde “en son başlayan, henüz bitmemiş iş” ile ilgilenilir. Bir işi bitirince, ondan hemen önce başlamış ve bekleyen işe dönülür. Yığın bu “bekleyen işler” listesini en ucuz biçimde tutar.

7.1.2Temel işlemler

Yığın ADT'si beş işlemle tanımlanır. İşlem adları İngilizce kalıplaşmıştır ve Java kütüphanesinde de aynı adlarla geçer; bu yüzden notta da aynen kullanılır. push “üste ekleme”, pop ise “üstten çıkarma” demektir.

Bu işlemlerden yalnız ikisi yığını değiştirir: push öğe sayısını bir artırır, pop bir azaltır. Öteki üçü yalnız bilgi verir. top() ile pop() arasındaki fark önemlidir: ikisi de üstteki öğeyi döndürür, ama top() öğeyi yerinde bırakır. Bir öğeye bakıp karar vermek, sonra gerekiyorsa çıkarmak gereken durumlarda (örneğin 7.3.9'daki sonraki büyük öğe probleminde) önce top(), sonra pop() kullanılır.

İki işlem boş yığında anlamsızdır: boş yığının üstünde öğe yoktur, dolayısıyla pop() da top() da döndürecek bir şey bulamaz. Boş yığından çıkarma denemesine alt taşma (underflow) denir ve hata sayılır. Kapasitesi sınırlı bir yığına, dolu iken ekleme denemesine ise taşma (overflow) denir. Taşma yalnız sınırlı yığınlarda görülür; bu ayrım 7.2.1'de ele alınır.

7.1.3push ve pop adım adım

İşlemlerin birlikte nasıl çalıştığını küçük bir işlem dizisi üzerinde izleyelim. Boş bir yığına sırayla push(10), push(15), push(20), top() ve dört kez pop() uygulanıyor.

Şekil 7.1'deki tablo, yığın sorularını çözerken kullanılabilecek pratik bir düzen önerir: her satıra bir işlem, işlemin döndürdüğü değer ve işlemden sonraki boyut yazılır. Yığının kendisi de her adımda alttan üste bir liste olarak not edilirse yanlış öğeyi çıkarma hatası pek yapılmaz.

7.1.4Java arayüzü: ADT ile gerçeklemeyi ayırmak

Java'da bir ADT'yi kodla ifade etmenin doğal yolu bir arayüz (interface) yazmaktır. Arayüz, bir sınıfın hangi metotları sağlaması gerektiğini söyler, ama metotların gövdesini içermez. Yığın ADT'si için arayüz şöyledir:

public interface Stack<E> {
  int size();
  boolean isEmpty();
  void push(E e);
  E top();    // boşsa null
  E pop();    // boşsa istisna
}

Arayüzün ilk satırındaki <E>, yığının jenerik (generic) olduğunu gösterir. E bir tür parametresidir: yığın tamsayı tutacaksa Stack<Integer>, karakter tutacaksa Stack<Character> yazılır ve E her yerde o türün yerine geçer. Böylece aynı kod her tür öğe için çalışır. Metotlar Tablo 7.1'deki işlemlerin aynısıdır. Yorumlar, boş yığındaki davranışı da sözleşmenin parçası yapar: boş yığında top() null döndürür, pop() ise bir istisna (exception) fırlatır.

Arayüzün yaptığı iş, “ne” sorusunu “nasıl” sorusundan ayırmaktır:

• ADT, “ne?” sorusunu cevaplar. Arayüz yalnız işlemleri ve anlamlarını söyler. Verinin dizide mi, bağlı listede mi saklandığından hiç söz etmez.
• Gerçekleme, “nasıl?” sorusunu cevaplar. DiziYigin<E> implements Stack<E> gibi bir sınıf, arayüzdeki her metodu belirli bir saklama biçimiyle yazar. Bağlı liste kullanan başka bir sınıf da aynı arayüzü gerçekleyebilir.
• Kod arayüze göre yazılırsa gerçekleme değiştirilebilir. Yığını kullanan bir metot parametresini Stack<Integer> türünde alırsa, ona dizi tabanlı ya da bağlı liste tabanlı bir yığın verilebilir. Çağıran kodda tek satır değişmez.

Bu ayrım yalnız düzen için değildir. Bir programın yığına yaptığı istekler değişmeden kalırken, ölçümler sonucunda daha hızlı bir gerçeklemeye geçmek gerekebilir. Arayüz bu değişikliği yerel tutar.

“Boş yığında ne olur?” sorusunun cevabı ise kütüphaneden kütüphaneye değişir. Aynı soyut işlem farklı sınıflarda farklı davranır:

Tablo 7.2'deki farklar, yığın kullanan kodda bir alışkanlığı gerekli kılar: pop() ya da peek() çağrılmadan önce isEmpty() ile yığının boş olmadığı denetlenir. Bu denetim yapılmazsa aynı kod bir kütüphaneyle istisna fırlatır, ötekiyle sessizce null alır ve hata çok daha ileride, anlaşılması zor bir yerde ortaya çıkar.

7.1.5İşlemlerin algoritmaları

Gerçeklemeye geçmeden önce işlemleri, dili bağlamayan bir sözde kodla yazmak yararlıdır. Yığının bir dizide tutulduğunu varsayalım. Dizinin yanında bir tamsayı tutulur: top, üstteki öğenin indisidir. Dizi indisleri 0'dan başladığı için ilk öğe 0. hücreye yazılır. Boş yığında henüz geçerli bir üst yoktur; bu durum top = −1 ile gösterilir.

push(x):

başla
  eğer yığın doluysa   // top = kap−1
    hata ver: taşma (overflow)
  değilse
    top değerini 1 artır
    yığın[top] ← x
son

Ekleme önce yer olup olmadığını sorar. Dizinin kapasitesi kap ise son geçerli indis kap − 1'dir; top bu değere ulaşmışsa dizi doludur ve ekleme taşmaya yol açar. Yer varsa top bir artırılır ve x yeni üst hücreye yazılır. Sıra önemlidir: önce indis artar, sonra yazılır. Ters sırada yapılsaydı x mevcut üstün üzerine yazılır ve o öğe kaybolurdu.

pop():

başla
  eğer yığın boşsa     // top = −1
    hata ver: alt taşma (underflow)
  değilse
    x ← yığın[top]; top 1 azalt
    x değerini döndür
son

Çıkarma önce yığının boş olup olmadığını sorar; top = −1 ise alt taşma vardır. Boş değilse üstteki öğe bir değişkene alınır, top bir azaltılır ve saklanan öğe döndürülür. Burada da sıra önemlidir: önce okunur, sonra indis azaltılır.

top():

başla
  eğer yığın boşsa null döndür
  değilse yığın[top] döndür
son

isEmpty() ve size():

isEmpty: top = −1 ise true, değilse false
size:    top + 1 döndür

size neden top + 1'dir? Öğeler 0, 1, …, top indislerindedir; bu aralıkta top + 1 tane indis vardır. Örneğin üç öğeli yığında öğeler 0, 1 ve 2. hücrelerdedir, top = 2'dir ve size = 3'tür. Boş yığında top = −1 olduğu için size = 0 çıkar; formül boş yığında da doğrudur.

7.1.6Zaman ve alan maliyeti

Yığının en güçlü yanı, temel işlemlerinin hepsinin sabit sürede çalışmasıdır. Bir işlemin süresi yığındaki öğe sayısına bağlı değilse o işleme O(1) zamanlı denir. Tablo 7.3 her işlemin maliyetini ve gerekçesini verir.

7.1.5'teki sözde kodlara bakıldığında bu sonuç açıktır. Her işlem en çok bir karşılaştırma, bir indis değişikliği ve bir dizi erişimi yapar. Dizi erişimi, indis bilindiği sürece dizinin boyutundan bağımsızdır. Hiçbir işlemde döngü yoktur; hiçbir öğe kaydırılmaz ya da taranmaz. Bir milyon öğeli yığında push, üç öğeli yığındakiyle aynı sayıda adım atar.

Arama ise farklıdır. Yığında belirli bir değerin olup olmadığını öğrenmek için ADT'nin sunduğu tek yol, öğeleri üstten başlayarak tek tek çıkarıp bakmaktır. En kötü durumda (aranan değer en altta ya da hiç yoksa) n öğenin hepsi çıkarılır: O(n). Arama sık gerekiyorsa yığın doğru veri yapısı değildir.

Alan maliyeti de basittir. n öğeli bir yığın en az n öğeyi saklamak zorundadır, bu yüzden O(n) bellek kullanır. İşlemlerin kendisi ise ek bellek gerektirmez: her işlem yalnız birkaç yerel değişken kullanır, yani O(1) ek alan harcar.

Tek bir istisna vardır: kapasitesi dolunca büyüyen dinamik dizi (dynamic array) kullanan yığında, büyütme yapan push bütün öğeleri yeni diziye kopyalar ve O(n) sürer. Büyütme seyrek yapıldığı için uzun bir işlem dizisinde push başına ortalama maliyet yine sabittir; buna amortize O(1) denir. Bu sonuç 7.2.6'da hesapla gösterilir.

Yığının hızının kaynağı kısıtlamanın kendisidir. Erişim yalnız üstle sınırlandığı için hiçbir işlem öğeleri kaydırmak ya da aramak zorunda kalmaz. Ortadan ekleme ya da istenen indisteki öğeyi okuma gibi işlemlere izin veren bir liste daha esnektir, ama bu esnekliğin bedeli bazı işlemlerin O(n) sürmesidir.

7.2Gerçekleme

Bir ADT'yi gerçeklemek, onu belirli bir saklama biçimiyle çalışan bir sınıf olarak yazmak demektir. Yığın için iki temel seçenek vardır: öğeleri bir dizide ya da birbirine bağlı düğümlerden oluşan bir listede tutmak. Bu kesim iki seçeneği de kod düzeyinde inceler, ardından ikisini karşılaştırır.

7.2.1Sabit boyutlu ve dinamik boyutlu yığın

Gerçeklemeye geçmeden önce yığının kapasitesi hakkında bir karar vermek gerekir. Yığın en çok kaç öğe tutabilecek? Bu soruya iki farklı cevap, iki tür yığın doğurur.

Sabit boyutlu yığın (fixed size stack) kapasitesini oluşturulurken belirler; sonradan büyüyemez, küçülemez. Arka planda sabit uzunlukta bir dizi kullanır. Dolu yığına ekleme denemesi taşma, boş yığından çıkarma denemesi alt taşma hatasıdır.

Dinamik boyutlu yığın (dynamic size stack) ise çalışma sırasında büyüyüp küçülebilir. Dolduğunda kapasitesini kendiliğinden artırır, örneğin iki katına çıkarır. Öğe sayısı kapasiteye göre çok azalırsa belleği geri vermek için küçülebilir de. Dinamik dizi ya da bağlı liste ile gerçeklenir.

İki tür arasındaki fark yalnız taşma durumunda ortaya çıkar. Alt taşma ise her iki türde de hatadır: dinamik yığın büyüyebilir, ama boş bir yığından öğe çıkarmanın hiçbir anlamı yoktur. Kısacası taşma yalnız sabit boyutlu yığında görülür; alt taşma her yığında görülebilir.

7.2.2İki gerçekleme yolu

Yığın ADT'si bir dizi (array) ya da bir bağlı liste (linked list) ile gerçeklenebilir. Şekil 7.3 aynı üç öğeli yığını (alttan üste 10, 15, 20) iki biçimde gösterir.

Dizi tabanlı yığında push işlemi top indisini artırır ve öğeyi dizi[top] hücresine yazar. pop işlemi dizi[top]'u alır, sonra top'u azaltır. Yığının dibi her zaman dizinin 0. hücresidir ve yığın dizinin sonuna doğru büyür.

Bağlı liste tabanlı yığında ise üst, listenin başıdır (head). push yeni düğümü listenin başına ekler; pop baştaki düğümü çıkarır ve değerini döndürür. Dikkat edilirse iki şekilde okların ve indislerin yönü farklıdır, ama ADT açısından iki yığın aynıdır: ikisinde de üstte 20 vardır, bir pop ikisinde de 20'yi döndürür.

7.2.3Dizi tabanlı yığın

Kapasitesi oluşturulurken belirlenen ve sonra değişmeyen dizi tabanlı yığına sınırlı yığın (bounded stack) da denir. Şekil 7.4 kapasitesi 8 olan bir dizide üç öğenin (5, 8, 3) nasıl durduğunu gösterir.

Dizi tabanlı yığının avantajları şunlardır:

• Basittir. Bir dizi ve bir tamsayı yeterlidir; kod birkaç satırdır.
• Bellek tasarrufu sağlar. Her öğe için yalnız öğenin kendisi saklanır. Bağlı listedeki gibi düğüm başına ek bir referans tutulmaz.
• Bellek kullanımı sıkı biçimde denetlenir. Yığın, kapasitesinden fazla bellek isteyemez. Kötü niyetli bir girdinin yığını sonsuza dek büyütüp belleği doldurmaya çalıştığı saldırılara karşı bu sınır bir güvencedir.
• Önbellek dostudur. Öğeler bellekte ardışık hücrelerdedir. İşlemci belleği bloklar hâlinde okuduğu için ardışık veriye erişim, dağınık düğümlere erişimden hızlıdır. Bu yüzden aynı O(1) işlemler dizi tabanlı yığında pratikte genellikle daha hızlı çalışır.

Dikkat edilmesi gereken noktalar da vardır:

• Eklemeden önce yığının dolu olmadığı denetlenmelidir. Denetim yapılmazsa yazma dizinin dışına düşer ve Java ArrayIndexOutOfBoundsException fırlatır.
• Kapasite seçimi bir uzlaşmadır. Az seçilirse taşma yaşanır, çok seçilirse kullanılmayan hücreler belleği boşa tutar.
• Nesne tutan dizide, çıkarılan öğenin hücresine null atanmalıdır. Atanmazsa dizi o nesneyi göstermeye devam eder ve nesne bellekte gereksiz yere kalır.

7.2.4Kod: DiziYigin

Aşağıdaki sınıf, 7.1.4'teki Stack<E> arayüzünü sabit kapasiteli bir diziyle gerçekler.

public class DiziYigin<E> implements Stack<E> {
    private E[] veri;
    private int top = -1;                    // -1 → boş yığın
    public DiziYigin(int kapasite) { veri = (E[]) new Object[kapasite]; }
    public boolean isEmpty() { return top == -1; }
    public int size()        { return top + 1; }
    public E top()           { return isEmpty() ? null : veri[top]; }
    public void push(E x) {
        if (top == veri.length - 1) throw new IllegalStateException("Taşma");
        veri[++top] = x;
    }
    public E pop() {
        if (isEmpty()) throw new IllegalStateException("Alt taşma");
        E x = veri[top];
        veri[top--] = null;                  // referansı bırak
        return x;
    }
}

Kod satır satır şöyle çalışır:

• veri, öğeleri tutan dizidir; top üstteki öğenin indisidir ve -1 ile başlar, çünkü yeni oluşturulan yığın boştur.
• Yapıcı, istenen kapasitede bir dizi ayırır. Java'da new E[kapasite] yazılamaz: tür parametresi E çalışma zamanında bilinmediği için jenerik dizi doğrudan oluşturulamaz. Bunun yerine bir Object dizisi oluşturulur ve (E[]) ile dönüştürülür. Derleyici bu dönüşüm için “unchecked” (denetlenmemiş) uyarısı verir; dizi sınıfın dışına hiç verilmediği sürece bu dönüşüm güvenlidir.
• isEmpty() yalnız top == -1 sorusunu sorar; size() top + 1 döndürür (7.1.5).
• top() metodu yığın boşsa null, değilse veri[top] döndürür. Burada ? : koşul işlecidir: koşul doğruysa ilk, yanlışsa ikinci değeri verir. Sınıfta hem top alanı hem de top() metodu vardır; Java ikisini parantezlerden ayırt eder.
• push(x) önce doluluğu sorar: top == veri.length - 1 ise son hücre de doludur ve IllegalStateException("Taşma") fırlatılır. Yer varsa veri[++top] = x; çalışır. ++top ön artırmadır: önce top bir artar, sonra artmış değer indis olarak kullanılır. Böylece 7.1.5'teki “önce artır, sonra yaz” sırası tek satıra sığar.
• pop() önce boşluğu sorar; boşsa “Alt taşma” istisnası fırlatılır. Değilse üstteki öğe x'e alınır. veri[top--] = null; satırında top-- son azaltmadır: önce top'un eski değeri indis olarak kullanılır ve o hücreye null yazılır, sonra top bir azalır. Son olarak saklanan x döndürülür.

++top ile top++ arasındaki fark burada belirleyicidir. push'ta veri[top++] = x yazılsaydı öğe eski top indisine, yani mevcut üstün üzerine yazılırdı. pop'ta veri[--top] = null yazılsaydı üstteki değil, onun altındaki hücre silinirdi.

Bütün metotlar döngüsüzdür ve sabit sayıda adım atar; her biri O(1) zamanlıdır. Sınıf, kapasite kadar hücrelik bir dizi kullanır: alan O(kapasite)'dir.

7.2.5Kod izleme: DiziYigin

Sınıfın davranışını, kapasitesi 4 olan bir yığın üzerinde izleyelim. main metodu sırayla şu çağrıları yapıyor: y.push(10), y.push(15), y.push(20), y.top(), y.pop(), y.push(25), y.push(30), y.push(40). İzlemede kullanılan metot gövdeleri şunlardır:

public void push(E x) {
  if (top == veri.length - 1)
    throw new IllegalStateException("Taşma");
  veri[++top] = x;
}
public E pop() {
  if (isEmpty())
    throw new IllegalStateException("Alt taşma");
  E x = veri[top];
  veri[top--] = null;          // referansı bırak
  return x;
}
public E top() { return isEmpty() ? null : veri[top]; }

İzlemenin önemli anları şunlardır. İlk push(10)'da denetim top = −1 ile veri.length − 1 = 3'ü karşılaştırır; eşit olmadıkları için devam edilir. veri[++top] = x önce top'u −1'den 0'a çıkarır, sonra veri[0] = 10 yazar. Bu tek bir atamadır; dizi ne kadar büyük olursa olsun süre değişmez.

top() çağrısı yığın boş olmadığı için veri[2] = 20'yi döndürür; dizi ve top değişmez. Hemen ardından gelen pop() önce isEmpty() ile top = 2 ≠ −1 olduğunu görür. Sonra x = veri[2] = 20 saklanır, veri[top--] = null ile 2. hücre boşaltılır ve top 1'e iner. Metot 20'yi döndürür: son giren ilk çıkmıştır.

push(25), boşalan 2. hücreyi yeniden kullanır. push(30) ile son hücre de dolar ve top = 3 olur. push(40)'ta denetim 3 == 3 sonucunu verir: dizi doludur, IllegalStateException("Taşma") fırlatılır. Dizi ve top değişmeden kalır. Sabit kapasiteli yığında taşma budur; dinamik dizi aynı noktada diziyi büyütürdü.

Şekil 7.5'in (c) ve (d) karelerinde dikkat çekici bir nokta vardır: 2. hücre önce 20'yi tutmuş, pop sonrası null olmuş, sonra 25 ile yeniden dolmuştur. Dizi tabanlı yığın hücreleri yeniden kullanır; bir öğe çıktığında dizinin geri kalanı kaydırılmaz.

7.2.6Dinamik dizi: dolunca iki katına büyütme

Sabit kapasite, kaç öğe geleceği önceden bilinmeyen durumlarda sıkıntı yaratır. Çözüm, dizi dolduğunda daha büyük bir dizi ayırmak ve öğeleri oraya taşımaktır. Java'da bir dizinin uzunluğu sonradan değiştirilemez; bu yüzden “büyütme” aslında yeni bir dizi oluşturup kopyalamak demektir.

public void push(E x) {
  if (top == veri.length - 1)
    buyut(2 * veri.length);
  veri[++top] = x;
}
private void buyut(int yeniKap) {
  E[] yeni = (E[]) new Object[yeniKap];
  for (int i = 0; i <= top; i++)
    yeni[i] = veri[i];
  veri = yeni;
}

Yeni push, taşma istisnası fırlatmak yerine buyut(2 * veri.length) çağırır. buyut metodu istenen kapasitede yeni bir dizi ayırır, döngüyle 0'dan top'a kadar bütün öğeleri aynı indislere kopyalar ve veri referansını yeni diziye yöneltir. Eski diziyi artık hiçbir referans göstermez; çöp toplayıcı onu temizler. Büyütmeden sonra veri[++top] = x her zamanki gibi çalışır.

Büyütme yapan bir push'un maliyeti büyüktür: n öğe kopyalanır, yani o tek push O(n) sürer. Buna karşın büyütmeler seyrektir. Kapasite her seferinde iki katına çıktığı için bir büyütmeden sonra, bir sonraki büyütmeye kadar o ana kadarki öğe sayısı kadar ucuz push yapılabilir. Pahalı işlemlerin maliyeti, aradaki çok sayıda ucuz işleme yayılır.

Örnekteki gözlem genelleşir. Kopya sayıları 4, 8, 16 gibi her biri öncekinin iki katı olan bir dizidir. Böyle bir dizinin toplamı son terimin iki katından küçüktür. Son büyütmede kopyalanan öğe sayısı da n'den küçük olduğu için bütün kopyaların toplamı 2n'yi geçmez.

Teoremin söylemediği şeye de dikkat etmek gerekir: tek bir push yine O(n) sürebilir. Örnek 7.2'deki 17. push 16 kopya yapmıştır. Bir oyun ya da gerçek zamanlı bir sistemde her işlemin kısa sürmesi gerekiyorsa amortize sınır yetmez; en kötü durum sınırı önemlidir.

Kapasiteyi oranla değil de sabit bir miktarla büyütmek çok daha kötü sonuç verir. Kapasite 10'dan başlayıp her dolumda 10 hücre artırılsın (10 → 20 → 30 → …). Büyütmeler 10, 20, 30, … öğede yapılır ve kopya toplamı 10 + 20 + 30 + … olur. n = 100 için bu toplam 10 + 20 + … + 90 = 450'dir; genel olarak yaklaşık n²/20'dir. Toplam maliyet O(n²), push başına ortalama O(n) olur. Karşılaştırma için iki katına büyütmede 1000 push 1023 kopya yaparken, 10'ar büyütmede 49.500 kopya yapar.

7.2.7Bağlı liste tabanlı yığın

İkinci gerçeklemede öğeler birbirine bağlı düğümlerden (node) oluşan bir zincirde tutulur. Her düğüm iki alan taşır: öğenin değeri ve zincirdeki bir sonraki düğüme referans.

class Dugum {
    int veri;
    Dugum sonraki;
    Dugum(int veri) { this.veri = veri; }   // sonraki = null
}

Dugum sınıfında veri değeri, sonraki ise bir alttaki düğümü gösterir. Yapıcı yalnız veri'yi atar; Java'da atanmayan referans alanları varsayılan olarak null'dır, bu yüzden yeni düğümün sonraki alanı başta null'dır.

Bu gerçeklemenin özellikleri şöyle sıralanabilir:

• Esnek boyut. Her push yeni bir düğüm ayırır. Boyut çalışma zamanında ihtiyaca göre değişir; bellek bitmedikçe taşma olmaz.
• Ek bellek. Her düğüm, değerin yanında bir sonraki referansı da tutar. Küçük öğelerde (örneğin bir int) referans, öğenin kendisi kadar ya da ondan fazla yer kaplayabilir.
• Rastgele erişim yok, ama üste erişim hızlı. Bağlı listede k. öğeye ulaşmak için baştan k adım yürümek gerekir. Yığın ise yalnız üstle ilgilenir ve üst, listenin başıdır: top referansı onu doğrudan gösterir.
• Ekleme ve çıkarma O(1). İkisi de listenin başında yapılır ve yalnız birkaç referansı değiştirir.

Neden üst listenin başında, sonunda değil? Tek yönlü bağlı listede (singly linked list) her düğüm yalnız sonrakini bilir. Sondaki düğümü silmek için, sondan bir önceki düğümün sonraki alanını null yapmak gerekir. Ama o düğüme ulaşmanın tek yolu baştan başlayıp listeyi yürümektir: O(n). Baştaki düğümü silmek ise yalnız baş referansını bir ilerletmektir: O(1). Yığının üstünü başa koymak, iki işlemi de sabit süreli yapar.

7.2.8Kod izleme: bağlı listede push

Bağlı liste yığınının alanları ve push metodu şöyledir:

Dugum top;         // yığının üstü
int uzunluk;

public void push(int veri) {
  Dugum gecici = new Dugum(veri);
  gecici.sonraki = top;
  top = gecici;
  uzunluk++;
}

top yığının üstündeki düğümü, uzunluk öğe sayısını tutar. Boş yığında top = null ve uzunluk = 0'dır. push dört adımda çalışır: yeni düğüm oluşturulur ve yerel gecici değişkeni onu gösterir; yeni düğümün sonraki alanı eski üste bağlanır; top yeni düğüme yöneltilir; uzunluk bir artırılır. Boş yığına push(10) ve ardından push(15) yapıldığını izleyelim.

İlk push(10)'da top null olduğu için gecici.sonraki = top satırı sonraki'yi yine null bırakır: yeni düğüm tek başınadır. Metot bittiğinde yerel gecici değişkeni ortadan kalkar, ama düğüm kaybolmaz; artık top üzerinden erişilir.

İkinci push'ta 15 düğümü oluşturulduğu anda henüz listeye bağlı değildir; top hâlâ 10'u gösterir. gecici.sonraki = top ile 15, eski üst olan 10'a bağlanır. Ancak bundan sonra top = gecici ile üst değiştirilir. Hiçbir öğe kaydırılmaz; yalnız iki referans değişir. Bu yüzden push O(1)'dir.

7.2.9Kod izleme: bağlı listede pop

pop metodu ve onu üç kez çağıran döngü şöyledir:

public int pop() {
  if (top == null)
    throw new RuntimeException("boş");
  int sonuc = top.veri;
  top = top.sonraki;
  uzunluk--;
  return sonuc;
}
// main içinde (yığın: 15 → 10):
for (int k = 0; k < 3; k++)
  System.out.println(pop());

pop önce yığının boş olup olmadığını top == null ile denetler; boşsa RuntimeException("boş") fırlatır. Değilse üstteki değeri sonuc'a saklar, top'u bir alttaki düğüme ilerletir, uzunluk'u azaltır ve saklanan değeri döndürür. Değerin, düğüm zincirden koparılmadan önce saklanması gerekir; top ilerledikten sonra eski üst düğüme ulaşmanın yolu kalmaz.

İlk çağrıda top = top.sonraki satırı üstü 10 düğümüne indirir. Eski üst düğüm (15) artık hiçbir referansla gösterilmez; çöp toplayıcı onu daha sonra temizler. Dizi tabanlı yığındaki gibi elle null atamaya gerek yoktur, çünkü düğümü gösteren tek referans zaten top'tu ve o ilerlemiştir. İkinci çağrıda top null'a iner ve yığın boşalır. Üçüncü çağrı boş yığına rastlar ve istisna fırlatılır; program, istisna yakalanmadığı için burada durur.

Boşluk denetimi olmasaydı üçüncü çağrıda top.veri ifadesi null bir referans üzerinden alana erişmeye çalışırdı ve Java NullPointerException fırlatırdı. Her iki durumda da program durur; ama açıklayıcı bir istisna hatanın nedenini hemen söyler, NullPointerException ise yalnızca belirtisini gösterir.

7.2.10Dizi mi, bağlı liste mi?

İki gerçeklemenin de temel işlemleri O(1)'dir. Seçim, bellek kullanımı ve kapasite davranışı gibi ikinci derece ölçütlere göre yapılır.

Tabloda bir takas görülür. Dizi tabanlı yığın öğe başına daha az bellek kullanır, ama kapasitenin boş kalan kısmı israf olabilir. Bağlı liste boş kapasite tutmaz, ama her öğe için ek bir referans taşır. Dinamik dizi en kötü durumda bir push'ta O(n) kopyalama yapar; bağlı liste her push'ta yeni bir nesne ayırır ve bu da sabit ama küçük olmayan bir maliyettir. Pratikte önbellek etkisi yüzünden dizi tabanlı yığın genellikle daha hızlıdır.

Java'da yeni kodda yığın için önerilen yol Deque arayüzü ile ArrayDeque sınıfıdır:

Deque<Integer> y = new ArrayDeque<>();

Bu nesne push, pop ve peek metotlarını sunar. Deque (iki uçlu kuyruk) her iki uçtan ekleme ve çıkarma destekler; yığın olarak kullanıldığında yalnız baş uç kullanılır. Eski java.util.Stack sınıfı Vector'dan türer ve bütün metotları senkronizedir: birden çok iş parçacığının aynı anda erişimine karşı her çağrıda kilit alır. Tek iş parçacıklı programlarda bu kilit gereksiz bir yavaşlıktır. Ayrıca Stack, Vector'dan kalıtım yoluyla istenen indise ekleme gibi yığına yabancı işlemleri de dışarı açar. Notun bundan sonraki örneklerinde bu yüzden ArrayDeque kullanılır.

7.3Yığın uygulamaları

Yığının değeri, uygulamalarında ortaya çıkar. Bu kesimdeki problemler birbirinden çok farklı görünür: tarayıcı geçmişi, fonksiyon çağrıları, parantezler, sayı dizileri. Ama hepsinde aynı soru sorulur: “En son görülen ve henüz sonuçlanmamış öğe hangisi?” Bu soruyu sabit sürede cevaplayan yapı yığındır.

7.3.1Yığının kullanıldığı yerler

Yığın, bilgisayar biliminin hemen her alanında karşımıza çıkar. Başlıca kullanım yerleri şunlardır:

• İfadeler. Ara ek, önek ve sonek gösterimler arasında dönüşüm, sonek ifadelerin değerlendirilmesi ve parantez kontrolü (7.5 ve 7.3.5).
• Geri al / yinele. Metin düzenleyicilerde undo ve redo işlemleri.
• Tarayıcı geçmişi. “Geri” ve “ileri” düğmeleri iki yığınla yönetilir.
• Çağrı yığını. Fonksiyon çağrıları, yerel değişkenler ve dönüş adresleri.
• Geri izleme (backtracking). Labirentte yol bulma, N-Vezir ve Şövalye Turu gibi problemlerde, çıkmaza girilince en son karar noktasına dönmek.
• Algoritmalar. Hanoi kuleleri, ağaç gezinme, stock span ve histogram problemleri.
• Çizge algoritmaları. Derinlik öncelikli arama (depth-first search, DFS), topolojik sıralama, güçlü bağlantılı bileşenler.
• Dize ters çevirme. Karakterler sırayla eklenir, ters sırayla çıkar.
• Sonraki büyük öğe. Bir dizideki her öğe için sağındaki ilk büyük değer.

Listenin ortak yönü şudur: işler iç içe başlar ve başlama sırasının tersiyle biter. Geri izlemede en son verilen karar ilk geri alınır; parantezlerde en son açılan ilk kapanır; çağrılarda en son çağrılan ilk döner. Bu iç içelik, LIFO düzeninin doğal karşılığıdır.

7.3.2Tarayıcıda geri ve ileri: iki yığın

Bir web tarayıcısı “geri” ve “ileri” düğmelerini iki yığınla yönetir. Geri yığını, şu anki sayfadan önce ziyaret edilen sayfaları; ileri yığını, geri gidilerek bırakılan sayfaları tutar. Şu anki sayfa iki yığının da dışında, ayrı bir değişkende durur. Üç işlem şu kurallarla çalışır:

• ziyaret(s): şu anki sayfa geri yığınına push edilir, ileri yığını temizlenir, s şu anki sayfa olur.
• geri(): şu anki sayfa ileri yığınına push edilir, geri yığınından pop edilen sayfa şu anki sayfa olur.
• ileri(): şu anki sayfa geri yığınına push edilir, ileri yığınından pop edilen sayfa şu anki sayfa olur.

Her işlem birkaç push ve pop yapar; ileri yığınını temizlemek dışında hepsi O(1)'dir. Temizleme, yığını yeni ve boş bir nesneyle değiştirerek de O(1) yapılabilir. Metin düzenleyicilerdeki geri al / yinele düzeni de aynıdır: “geri al” yığını yapılan değişiklikleri, “yinele” yığını geri alınanları tutar; yeni bir değişiklik yapılınca yinele yığını temizlenir.

7.3.3Çağrı yığını

Bir program çalışırken her metot çağrısı için bellekte bir kayıt tutulur. Bu kayıtta metodun parametreleri, yerel değişkenleri ve metot bitince programın nereden devam edeceği (dönüş adresi) bulunur. Bu kayda çerçeve (stack frame) denir. Çerçeveler bir yığında tutulur: çağrı yığını (call stack). Bir metot çağrıldığında çerçevesi yığına push edilir; metot dönünce çerçeve pop edilir ve kontrol, artık üstte olan çağıran metoda geçer.

Çağrı yığınını en açık gösteren örnek, kendini çağıran bir metottur. Bir metodun kendini çağırmasına özyineleme (recursion) denir. Aşağıdaki metot n! = n · (n − 1) · … · 1 değerini hesaplar.

int fakt(int n) {
  if (n <= 1)
    return 1;
  return n * fakt(n - 1);
}
// main içinde:
System.out.println(fakt(3));

n <= 1 durumu, metodun kendini çağırmadan doğrudan cevap verdiği taban durumdur (base case). Öteki her durumda n * fakt(n - 1) hesaplanır; ama çarpma, fakt(n - 1) bitmeden yapılamaz.

Yığın 2–4. adımlarda büyür, 5–7. adımlarda küçülür. Taban duruma ulaşıldıktan sonra yığının geriye doğru boşalmasına çözülme (unwinding) denir. Askıda bekleyen her çerçeve, üstündeki çerçeve dönünce kaldığı yerden devam eder: fakt(2), fakt(1)'in döndürdüğü 1 ile çarpmasını tamamlar.

Çağrı yığınının derinliği en çok n çerçevedir; bu yüzden fakt(n) O(n) bellek kullanır. Çağrı yığınının boyutu sınırlıdır. Çok derin özyineleme, ya da taban durumu hiç gelmeyen hatalı bir özyineleme, yığını doldurur ve Java StackOverflowError verir. Bu, çağrı yığınındaki taşmanın kendisidir.

7.3.4Dizeyi tersine çevirme

LIFO düzeninin en doğrudan sonucu şudur: bir dizi öğe sırayla yığına eklenip sonra çıkarılırsa ters sırada çıkar. Bir dizeyi tersine çevirmek için bu yeterlidir.

String tersCevir(String str) {
    Deque<Character> yigin = new ArrayDeque<>();
    char[] karakterler = str.toCharArray();
    for (char c : karakterler)
        yigin.push(c);
    for (int i = 0; i < str.length(); i++)
        karakterler[i] = yigin.pop();
    return new String(karakterler);
}
// main içinde:
System.out.println(tersCevir("ABCD"));

Metot önce boş bir karakter yığını oluşturur. Deque<Character> türü kullanılır, çünkü Java'da jenerik türler ilkel türlerle (char) değil, onların sarmalayıcı sınıflarıyla (Character) çalışır; push(c) sırasında char kendiliğinden Character'a çevrilir. toCharArray() dizenin karakterlerini yeni bir diziye kopyalar; Java'da String değiştirilemez olduğu için sonuç bu dizinin üzerine yazılarak kurulur.

Birinci döngü karakterleri sırayla yığına iter. İkinci döngü i = 0'dan başlayarak her hücreye yığından çıkan karakteri yazar. "ABCD" için birinci döngüden sonra yığın alttan üste A, B, C, D'dir. İkinci döngüde ilk pop D'yi verir ve karakterler[0] = 'D' olur; ardından C, B, A gelir. Metot "DCBA" döndürür.

Her karakter bir kez push, bir kez pop edilir; iki döngü de n adım sürer. Zaman O(n)'dir. Yığın en çok n karakter tutar, karakter dizisi de n hücredir: ek bellek O(n)'dir. Aynı fikir, bir kelimenin palindrom (tersten de aynı okunan kelime, örneğin “kayak”) olup olmadığını denetlemek için de kullanılabilir: ters çevrilmiş dize asıl dizeyle karşılaştırılır.

7.3.5Parantez kontrolü: problem ve algoritma

Bir derleyicinin ilk işlerinden biri, kaynak koddaki parantezlerin doğru eşleşip eşleşmediğini denetlemektir. Problemi sadeleştirelim: S dizisi yalnız ( ) { } [ ] karakterlerinden oluşsun.

İkinci koşul, LIFO kuralının ta kendisidir. Bu yüzden algoritma bir yığın kullanır: henüz kapanmamış, yani eşleşmemiş açık parantezler yığında tutulur. S baştan sona bir kez gezilir:

1. Açık parantez gelirse yığına push edilir. Kapanışını bekleyecektir.
2. Kapalı parantez gelirse: yığın boşsa S geçersizdir (kapatılacak açık parantez yoktur). Boş değilse pop yapılır; çıkan açık parantez gelen kapalıyla aynı tipte değilse S geçersizdir.
3. S bitince yığın boşsa geçerli, değilse geçersizdir (kapanmamış parantez kalmıştır).

Dört küçük örnek, algoritmanın yakaladığı hata türlerini gösterir:

([)] örneği yalnız sayma ile çözülemeyeceğini gösterir. Bu dizide iki açık ve iki kapalı parantez vardır, her tipten de birer açık ve birer kapalı. Sayılar tutar, ama sıra yanlıştır. Yalnız sayaç tutan bir yöntem bu hatayı göremez; yığın görür.

7.3.6Kod: gecerliMi()

boolean gecerliMi(String s) {
  Deque<Character> yigin = new ArrayDeque<>();
  for (char c : s.toCharArray()) {
    if (c == '(' || c == '[' || c == '{') {
      yigin.push(c);
    } else {
      if (yigin.isEmpty()) return false;
      char acik = yigin.pop();
      if (!eslesir(acik, c)) return false;
    }
  }
  return yigin.isEmpty();
}

Yardımcı metot, bir açık ve bir kapalı parantezin aynı tipte olup olmadığını söyler:

boolean eslesir(char a, char k) {
  return (a == '(' && k == ')')
      || (a == '[' && k == ']')
      || (a == '{' && k == '}');
}

gecerliMi dizenin her karakterini sırayla c'ye alır. Açık parantezse yigin.push(c) çalışır. Değilse (yani kapalı parantezse) önce yigin.isEmpty() sorulur; boşsa hemen false döner. Boş değilse en son açılan parantez acik'e çıkarılır ve eslesir(acik, c) ile tip denetlenir; eşleşmezse false döner. Döngü bittiğinde return yigin.isEmpty(); kapanmamış parantez olup olmadığını cevaplar.

eslesir metodu üç olası doğru çifti || (veya) ile bağlar. && (ve) her çiftte açık ve kapalının birlikte doğru olmasını ister. Örneğin eslesir('[', ')') çağrısında üç çiftin hiçbiri tutmaz ve sonuç false'tur.

Her karakter bir kez işlenir ve her işlem O(1)'dir; zaman O(n)'dir. En kötü durumda (örneğin bütün karakterler açık parantezse) yığın n öğe tutar: bellek O(n)'dir.

7.3.7Kod izleme: geçerli bir dize

gecerliMi("{{[]}()}[]") çağrısını izleyelim. Dizenin on karakteri vardır; indisler 0'dan 9'a gider.

Her kapalı parantez geldiğinde yığının üstünde, ona en yakın ve henüz kapanmamış açık parantez durur. 4. indisteki }, 1. indisteki { ile eşleşir; 7. indisteki } ise 0. indisteki ile. Yığın bu eşleşmeyi hiçbir arama yapmadan, yalnız LIFO düzeniyle bulur. 7. indisten sonra yığın bir an boşalır; bu, o ana kadarki önekin kendi başına geçerli olduğunu gösterir. Dize bittiğinde yığın boştur ve metot true döndürür.

7.3.8Geçersiz dizeler

Algoritma üç farklı yerde false döndürebilir. Her biri ayrı bir hata türünü yakalar.

Erken dönüş, algoritmanın bir başka yararıdır: hata bulunduğu anda sonuç bellidir ve dizenin geri kalanını okumaya gerek yoktur. En kötü durum yine O(n)'dir, ama geçersiz girdilerde metot çoğu zaman çok daha erken biter.

Aynı algoritma yalnız parantezlerle sınırlı değildir. Örneğin <b><i>…</i></b> gibi HTML etiketlerinin doğru iç içe olup olmadığı da böyle denetlenir: açılış etiketi yığına push edilir, kapanış etiketi geldiğinde pop yapılır ve etiket adları karşılaştırılır.

7.3.9Sonraki büyük öğe

Bir sayı dizisi verilsin. Her öğe için, sağında kalan ve kendisinden büyük olan ilk öğe isteniyor; böyle bir öğe yoksa cevap −1'dir. Bu probleme sonraki büyük öğe (next greater element) denir.

Tabloyu elle doğrulayalım. 0. öğe 4'ün sağındaki ilk büyük öğe 7'dir. 7'nin sağında 3 ve 4 daha küçüktür, ilk büyük 8'dir. 3'ün hemen sağındaki 4 ondan büyüktür. 8'in sağında yalnız 1 vardır; büyük öğe yoktur, cevap −1'dir. Son öğenin sağında hiç öğe yoktur: −1.

En doğrudan çözüm kaba kuvvettir: her öğe için sağındaki öğeler tek tek taranır ve ilk büyük olanda durulur. En kötü durumda (örneğin azalan bir dizide) her öğe için sağın tamamı taranır; toplam (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 karşılaştırma, yani O(n²) zaman gerekir.

Yığın ile O(n)'de çözülebilir. Fikir şudur: dizi sağdan sola gezilir ve yığında yalnız “aday” değerler tutulur. Aday, solda kalan öğeler için sonraki büyük öğe olabilecek bir değerdir. Yeni bir öğe x geldiğinde yığının üstündeki x'ten küçük ya da ona eşit değerler atılır. Neden? Bu değerler x'in sağındadır ve x'ten büyük değildir. x'in solundaki herhangi bir öğe için önce x görülür; x yeterince büyük değilse onlar da değildir. Yani bu değerler bir daha asla cevap olamaz. Atılmayan ilk değer (varsa) x'in cevabıdır. Sonra x yeni aday olarak yığına eklenir.

int[] sonrakiBuyuk(int[] dizi) {
    int[] sonuc = new int[dizi.length];
    Deque<Integer> yigin = new ArrayDeque<>();
    for (int i = dizi.length-1; i >= 0; i--) {
        while (!yigin.isEmpty() &&
               yigin.peek() <= dizi[i])
            yigin.pop();
        sonuc[i] = yigin.isEmpty()
                 ? -1 : yigin.peek();
        yigin.push(dizi[i]);
    }
    return sonuc;
}

Bu kuralın bir sonucu olarak yığın her an alttan üste azalan sırada kalır: yeni eklenen öğe, kendisinden küçük ya da eşit olanları attıktan sonra eklendiği için altındaki her değerden küçüktür. İçeriği hep sıralı kalan böyle bir yığına monoton yığın denir.

İspattaki düşünce biçimi, amortize analizin bir başka örneğidir: tek bir dış döngü turunda iç döngü birçok kez dönebilir, ama bütün turların toplamı sınırlıdır. İç içe döngü gördüğümüzde sürenin otomatik olarak karesel olduğunu varsaymak yanlıştır; iç döngünün toplamda kaç kez döndüğü sayılmalıdır.

7.3.10Kod izleme: sonrakiBuyuk()

Başlangıçta sonuc dizisinin bütün hücreleri 0'dır (Java yeni int dizisini sıfırla doldurur) ve yığın boştur. i = 5'te yığın boş olduğu için cevap −1'dir; 1, soldaki öğeler için yeni aday olarak eklenir. i = 4'te üstteki 1, 8'den küçüktür ve atılır: 1, 8'in solundaki hiçbir öğenin cevabı olamaz, çünkü arada ondan büyük 8 vardır. Yığın boşalır, 8'in cevabı −1'dir.

i = 1 satırı yöntemin işleyişini en iyi gösteren adımdır. Yığında alttan üste 8, 4, 3 vardır. Gelen 7, önce 3'ü sonra 4'ü atar; 8'de durur, çünkü 8 <= 7 yanlıştır. Cevap 8'dir. Atılan 3 ve 4, 7'nin solundakiler için gereksizdir. Son olarak i = 0'da üstteki 7, 4'ten büyüktür ve hemen cevap olur. Metot [7, 8, 4, 8, −1, −1] döndürür. Toplam altı push ve üç pop yapılmıştır; Teorem 7.2'deki sınırla uyumludur.

7.3.11En küçüğü O(1)'de veren yığın

Yığın ADT'sine bir işlem ekleyelim: getMin(), yığındaki en küçük değeri döndürsün. Bunu yığını tarayarak yapmak O(n) sürer. Amaç getMin()'i de öteki işlemler gibi O(1) yapmaktır.

Çözüm, ikinci bir yığın kullanmaktır. y bütün öğeleri tutar. min yığınının üstü ise her an y'deki en küçük değerdir. Fikir şöyledir: yeni gelen değer o ana kadarki en küçükten büyük değilse min'e de eklenir. Bir değer y'den çıktığında, min'in üstüne eşitse oradan da çıkar; böylece bir önceki en küçük yeniden üste gelir.

Deque<Integer> y = new ArrayDeque<>();
Deque<Integer> min = new ArrayDeque<>();
void push(int x) {
  y.push(x);
  if (min.isEmpty() || x <= min.peek())
    min.push(x);
}
int pop() {
  int x = y.pop();
  if (x == min.peek()) min.pop();
  return x;
}
int getMin() { return min.peek(); }

Her işlem en çok iki push, iki pop ya da bir peek yapar; hepsi O(1)'dir. getMin() yalnız min.peek()'tir, arama yapmaz. Bedel ek bellektir: en kötü durumda (örneğin azalan sırada eklemelerde) min de n öğe tutar, ek alan O(n)'dir.

pop'taki x == min.peek() karşılaştırması da bir incelik taşır. x bir int, min.peek() ise bir Integer döndürür. Java burada Integer'ı int'e açar ve değerleri karşılaştırır; bu doğrudur. İki taraf da Integer olsaydı == nesne kimliğini karşılaştırırdı ve 127'den büyük değerlerde yanlış sonuç verebilirdi. Böyle durumlarda equals kullanılır.

7.4Hanoi kuleleri ve stock span

Bu kesimdeki iki problem, yığının iki farklı kullanım biçimini gösterir. Hanoi kulelerinde yığın, özyinelemenin gizli çağrı yığınını açık bir veri yapısına dönüştürür. Stock span probleminde ise yığın, sonraki büyük öğedekine benzer bir “aday” listesi tutar ve karesel bir çözümü doğrusal hâle getirir.

7.4.1Hanoi kuleleri: yığınla özyinelemesiz çözüm

Hanoi kuleleri bulmacasında üç çubuk (A, B, C) ve farklı büyüklükte n disk vardır. Başta bütün diskler A çubuğunda, büyükten küçüğe dizilidir. Amaç, diskleri aynı düzende C çubuğuna taşımaktır. İki kural vardır: her hamlede bir çubuğun en üstündeki tek disk taşınır ve büyük disk hiçbir zaman küçük diskin üstüne konamaz. Her çubuk kendi başına bir yığındır: yalnız en üstteki diske erişilir.

Bulmacanın klasik çözümü özyinelemelidir. n diski A'dan C'ye, B'yi yardımcı kullanarak taşımak için:

1. üstteki n − 1 disk A'dan B'ye taşınır (C yardımcı);
2. en büyük disk A'dan C'ye taşınır;
3. n − 1 disk B'den C'ye taşınır (A yardımcı).

Tek disk kaldığında (taban durum) disk doğrudan taşınır. Özyinelemeli çözümde bekleyen alt görevleri çağrı yığını tutar: 1. adım yapılırken 2. ve 3. adım askıdadır. Aynı işi açık bir yığınla yapmak mümkündür. Her bekleyen iş bir görev olarak saklanır.

// Gorev: n diski k(aynak)'tan h(edef)'e, y(ardımcı) ile taşı
record Gorev(int n, char k, char y, char h) {}

void hanoi(int n) {
  Deque<Gorev> yigin = new ArrayDeque<>();
  yigin.push(new Gorev(n, 'A', 'B', 'C'));
  while (!yigin.isEmpty()) {
    Gorev g = yigin.pop();
    if (g.n() == 1)
      System.out.println(g.k() + " → " + g.h());
    else {                         // ters sırayla
      yigin.push(new Gorev(g.n()-1, g.y(), g.k(), g.h()));
      yigin.push(new Gorev(1, g.k(), g.y(), g.h()));
      yigin.push(new Gorev(g.n()-1, g.k(), g.h(), g.y()));
    }
  }
}

record, Java 16 ile gelen kısa bir sınıf tanımıdır: Gorev dört alanlı değişmez bir nesnedir ve alanlarına g.n(), g.k() gibi metotlarla erişilir. Alan adları yorumda açıklanmıştır: n taşınacak disk sayısı, k kaynak, y yardımcı, h hedef çubuktur. Görev (3, A, B, C), “3 diski A'dan C'ye, B yardımcıyla taşı” demektir.

Metot başlangıç görevini yığına koyar ve yığın boşalana kadar döner. Her turda üstteki görev çıkarılır. Görev tek diskliyse doğrudan yapılır: hamle yazdırılır. Değilse görev, yukarıdaki üç alt göreve bölünür ve bu alt görevler yığına ters sırayla eklenir: önce 3. adım (n−1, y, k, h), sonra 2. adım (1, k, y, h), en son 1. adım (n−1, k, h, y). Böylece ilk yapılması gereken 1. adım en üste gelir ve bir sonraki turda ilk o çıkar.

Ters sıra, LIFO'nun doğrudan sonucudur. Alt görevler doğal sırayla eklenseydi en üstte 3. adım kalır ve ilk o yapılırdı: henüz A'dan alınmamış diskleri B'den C'ye taşımaya kalkışılırdı.

7.4.2Kod izleme: hanoi(3)

Tablo 7.15, hanoi(3)'ün bütün döngü turlarını gösterir. Yığın sütununda görevler üstten alta yazılmıştır: ilk yazılan, bir sonraki turda çıkacak görevdir. Görevler (n,k,y,h) biçimindedir.

1. turda (3,A,B,C) bölünür: g.n()-1 = 2, g.y() = B, g.k() = A, g.h() = C olduğu için önce (2,B,A,C), sonra (1,A,B,C), en son (2,A,C,B) eklenir. Üstte “2 diski A'dan B'ye taşı” görevi kalır. 2. turda bu görev de bölünür ve üç tek diskli görev üste gelir. 3–5. turlar en küçük iki diski B'ye taşır (A → C, A → B, C → B). 6. turda en büyük disk A'dan C'ye geçer; bu, ilk bölmedeki 2. adımdır. 7. tur, kalan “2 diski B'den C'ye taşı” görevini böler ve 8–10. turlar onu tamamlar.

Hamle sayısı 7 = 2³ − 1'dir. Genel olarak n disk için 2ⁿ − 1 hamle gerekir, çünkü T(n) = 2T(n − 1) + 1 ve T(1) = 1'dir. Yığından çıkan görev sayısı hamle sayısından biraz fazladır: her hamle bir tek diskli görevdir, bunlara bölünen görevler eklenir. n = 3'te 7 tek diskli ve 3 bölünen görev, toplam 10 tur vardır. Zaman O(2ⁿ)'dir; bu, problemin kendi alt sınırıdır, çünkü her hamlenin yazılması gerekir.

Bellek açısından durum çok daha iyidir. Yığın, izlemede en çok 5 görev tutmuştur. Her bölme en üstteki görevi üç görevle değiştirir, yani yığını iki büyütür; bölmeler en çok n − 1 kez üst üste yapılabilir (görevdeki disk sayısı her seferinde bir azalır). Yığın en çok 1 + 2(n − 1) = 2n − 1 görev tutar: O(n) bellek. n = 3'te 5, n = 4'te 7 görev.

Açık yığının özyinelemeye karşı bir üstünlüğü vardır: bekleyen işlerin listesi programın kendi denetimindedir. Çağrı yığınının boyutunu dil ortamı sınırlar ve çok derin özyineleme StackOverflowError verir; açık yığın ise yığın belleğinde (heap) büyür. Aynı dönüşüm, derinlik öncelikli arama gibi başka özyinelemeli algoritmalara da uygulanabilir.

7.4.3Stock span problemi

Bir hisse senedinin günlük kapanış fiyatları bir dizide verilsin. Finansal analizde sık sorulan bir soru, bugünkü fiyatın “kaç gündür aşılmadığıdır”. Bu soruya stock span (hisse senedi sıçrama) problemi denir.

Tanımdaki üç ayrıntı önemlidir: sayım bugünü de içerdiği için her span en az 1'dir; eşit fiyatlar sayıma dahildir; ve sayım ardışık günler üzerinden yapılır, yani daha yüksek bir fiyata rastlanınca, onun gerisinde daha düşük fiyatlar olsa bile sayım biter.

Kaba kuvvet çözümü her gün için geriye doğru yürür ve daha yüksek fiyat bulunca durur. Fiyatlar sürekli artıyorsa her gün başa kadar yürünür ve toplam 1 + 2 + … + n adım, yani O(n²) zaman gerekir. Yığın bu tekrarlı yürüyüşü ortadan kaldırır.

7.4.4Kod: span()

int[] span(int[] fiyatlar) {
    int[] sicrama = new int[fiyatlar.length];
    Deque<Integer> yigin = new ArrayDeque<>();
    yigin.push(0); sicrama[0] = 1;
    for (int i = 1; i < fiyatlar.length; i++) {
        while (!yigin.isEmpty() &&
            fiyatlar[i] >= fiyatlar[yigin.peek()])
            yigin.pop();
        sicrama[i] = yigin.isEmpty() ? i + 1
                              : i - yigin.peek();
        yigin.push(i);
    }
    return sicrama;
}

Yöntemin fikri, sonraki büyük öğedekiyle aynıdır, ama bu kez dizi soldan sağa gezilir ve yığında değerler yerine indisler tutulur. Yığında, henüz aşılmamış günlerin indisleri vardır; bu günlerin fiyatları alttan üste azalır. Gün i geldiğinde, fiyatı bugünkünden küçük ya da ona eşit olan günler yığından atılır. Bu günler artık hiçbir gelecek gün için sınır olamaz: bugün onları aşmıştır ve bugünün kendisi onlardan daha yakın ve daha yüksek (ya da eşit) bir engeldir.

Atma bittikten sonra yığının üstünde, bugünden önceki ve bugünden daha yüksek fiyatlı ilk gün kalır. Span, bu günle bugün arasındaki gün sayısıdır: i - yigin.peek(). Yığın boşalmışsa bugünkü fiyat bütün önceki fiyatları aşmıştır ve span i + 1'dir (0'dan i'ye bütün günler). Son olarak bugün yığına eklenir; gelecek günler için olası bir sınırdır.

Kodda ilk gün döngüden önce ele alınır: yigin.push(0); sicrama[0] = 1;. İlk günün öncesinde gün olmadığı için span'i 1'dir ve 0 indisi yığının ilk elemanı olur. Döngü bu yüzden i = 1'den başlar. İç while döngüsünün koşulundaki fiyatlar[i] >= fiyatlar[yigin.peek()], yığında indis tutulduğu için fiyata indis üzerinden erişir.

Maliyet, sonraki büyük öğedeki gerekçeyle aynıdır: her indis tam bir kez eklenir ve en çok bir kez çıkarılır. Toplam pop sayısı en çok n'dir; zaman O(n), bellek O(n)'dir.

7.4.5Kod izleme: span()

i = 3'te 70, üstteki 2. günün fiyatını (60) aşar ve 2 atılır. 2. gün artık kimsenin sınırı olamaz: 3. günden sonraki her gün için 3. gün (70) ondan daha yakın ve daha yüksektir. Üstte 1. gün (80) kalır ve span 3 − 1 = 2'dir. i = 5'te 75, önce 4. günü (60) sonra 3. günü (70) atar, 1. günde (80) durur: span 5 − 1 = 4. i = 6'da 85, 5. günü (75) ve 1. günü (80) atar, 0. günde (100) durur: span 6. Metot [1, 1, 1, 2, 1, 4, 6] döndürür; Örnek 7.5'teki elle bulunan sonuçla aynıdır. Toplam 7 push ve 5 pop yapılmıştır.

7.5İfade gösterimleri

Okulda öğrenilen 3 + 4 * 2 gibi aritmetik ifadeler bir insan için kolay okunur, ama bir bilgisayar için iki zorluk taşır. Birincisi, işlemlerin sırası yazılış sırasıyla aynı değildir: çarpma, solda yazılmış toplamadan önce yapılır. İkincisi, parantezler bu sırayı değiştirir ve iç içe geçebilir. Bu kesim, aynı ifadeyi işlem sırasını açıkça taşıyan iki başka biçimde yazmayı ve bu biçimler arasında yığınla dönüşüm yapmayı anlatır.

7.5.1Ara ek, önek ve sonek gösterim

Bir ifadede işlenenler (A, B, 5 gibi değerler) ve operatörler (+, −, *, /) bulunur. Üç gösterim, operatörün işlenenlere göre nereye yazıldığıyla ayrılır.

Günlük yazdığımız biçim ara ek gösterimdir: B + C'de operatör iki işlenenin arasındadır. Önek gösterimde operatör işlenenlerinden önce gelir: + B C. Bu gösterimi Polonyalı mantıkçı Jan Łukasiewicz 1920'lerde önerdiği için Polonya gösterimi de denir. Sonek gösterimde operatör işlenenlerinden sonra gelir: B C +. Bunun adı ters Polonya gösterimidir ve İngilizce kısaltmasıyla RPN (Reverse Polish Notation) olarak da bilinir. Kod ve simülatör adlarında İngilizce kısa adlar kullanıldığı için not boyunca yer yer infix, prefix ve postfix adları da geçer.

Sonek ifadeyi okumak başta yadırgatıcıdır. A B C + * D / şöyle çözülür: soldan okunurken bir operatöre gelince, ondan hemen önceki iki değer o operatörün işlenenleridir ve yerlerini sonuç alır. B C + → (B + C); sonra A (B + C) * → A * (B + C); sonra … D / → (A * (B + C)) / D.

Önek ve sonek gösterimin büyük üstünlüğü şudur: parantez ve öncelik kuralı gerekmez. İşlem sırası, simgelerin dizilişinden kesin olarak okunur. Sonek ifade soldan sağa, önek ifade sağdan sola tek geçişte ve bir yığınla değerlendirilir. Bu yüzden derleyiciler ve yorumlayıcılar ifadeleri çoğunlukla sonek biçime çevirir. Java derleyicisinin ürettiği bayt kodu da yığın tabanlıdır: a + b ifadesi “a'yı yığına koy, b'yi yığına koy, topla” komutlarına dönüşür. Bazı hesap makineleri (örneğin eski HP modelleri) doğrudan RPN ile çalışır. Sembolik cebir programları ve ifade ağaçları üzerinde çalışan algoritmalar da bu gösterimleri kullanır.

7.5.2Öncelik, birleşme ve elle dönüşüm

Ara ek ifadeyi doğru okumak için iki kural gerekir. Öncelik, farklı operatörlerden hangisinin önce yapılacağını söyler. Birleşme, aynı öncelikteki operatörler yan yana geldiğinde hangi yönde yapılacağını söyler.

Soldan birleşmenin anlamı şudur: A − B + C, (A − B) + C demektir, A − (B + C) değil. Sayılarla: 10 − 4 + 3 önce 10 − 4 = 6, sonra 6 + 3 = 9 verir; sağdan yapılsaydı 10 − 7 = 3 çıkardı. Bu ifadenin soneki A B − C +'dır. Üs ise sağdan birleşir: 2 ^ 3 ^ 2, 2 ^ (3 ^ 2) = 29 = 512 demektir, (2 ^ 3) ^ 2 = 64 değil.

Bir ara ek ifadeyi elle önek ya da sonek biçime çevirmenin güvenilir bir yolu tam parantezlemedir:

1. Öncelik ve birleşme kurallarına göre her işlem kendi parantezine alınır.
2. Sonek için her operatör, kendi parantezinin sağ ucuna taşınır ve parantezler silinir.
3. Önek için her operatör, kendi parantezinin sol ucuna taşınır ve parantezler silinir.

Dönüşümü denetlemenin hızlı bir yolu vardır: işlenenlerin sırası üç gösterimde de aynı kalır. Yukarıdaki iki örnekte de A, B, C, D (ve E) her gösterimde bu sırayla geçer; yalnız operatörlerin yeri değişir. Bir dönüşüm sonucunda işlenenlerin sırası bozulmuşsa sonuç kesinlikle yanlıştır. Ters yön her zaman doğru değildir: işlenen sırası doğru olduğu hâlde operatörler yanlış yerde olabilir (7.5.1'deki * A / + B C D örneği gibi).

7.5.3Ara ekten soneke: algoritma

Tam parantezleme elle kolaydır, ama bir programın uygulaması için önce bütün ifadeyi çözümlemek gerekir. Edsger Dijkstra'nın 1961'de tanımladığı ve demiryolu makas alanına benzetilerek shunting-yard (manevra sahası) algoritması adını alan yöntem, aynı işi ifadeyi soldan sağa tek geçişte okuyarak yapar. Operatörler ve açık parantezler bir yığında bekletilir; işlenenler doğrudan çıktıya gider.

Kuralların arkasındaki düşünce şudur. Bir operatör okunduğunda henüz sağ işleneni gelmemiştir, bu yüzden hemen çıktıya yazılamaz; yığında bekler. Yeni bir operatör op geldiğinde, yığındaki operatörlerden önceliği op'unkinden büyük ya da eşit olanların işlenenleri tamamlanmıştır ve op'tan önce yapılmaları gerekir. Bu yüzden çıktıya alınırlar. Önceliği daha düşük olanlar ise op'tan sonra yapılacaktır ve beklemeye devam eder.

Eşitlikte de çıkarmanın (≥) nedeni soldan birleşmedir. A − B + C'de + geldiğinde yığında − vardır; ikisinin önceliği eşittir. Soldaki − önce yapılmalıdır, bu yüzden − çıktıya alınır ve sonuç A B − C + olur. Sağdan birleşen ^ için kural farklıdır: yalnız önceliği daha büyük (>) olanlar çıkarılır, eşit olan ^ yığında kalır. Böylece A ^ B ^ C'de ikinci ^ birincinin üstüne konur ve önce o yapılır.

Parantez, öncelik kurallarına bir “duvar” örer. ( yığına konduktan sonra gelen operatörler onun altındakilere hiç bakmaz; ) gelince yalnız ('a kadar olan operatörler çıkarılır. Parantezler hiçbir zaman çıktıya yazılmaz: sonek gösterimde gerek yoktur.

Her simge bir kez okunur. Her operatör yığına bir kez girer ve bir kez çıkar. Toplam iş, ifadenin uzunluğu n ile orantılıdır: zaman O(n), yığın için bellek en kötü durumda O(n)'dir.

7.5.4Kod: infixToPostfix()

String infixToPostfix(String ifade) {
  StringBuilder cikti = new StringBuilder();
  Deque<Character> yigin = new ArrayDeque<>();
  for (char c : ifade.toCharArray()) {
    if (Character.isLetterOrDigit(c)) cikti.append(c);
    else if (c == '(') yigin.push(c);
    else if (c == ')') {
      while (yigin.peek() != '(')
        cikti.append(yigin.pop());
      yigin.pop();                  // '(' atılır
    } else {                        // operatör
      while (!yigin.isEmpty() &&
          oncelik(yigin.peek()) >= oncelik(c))
        cikti.append(yigin.pop());
      yigin.push(c);
    }
  }
  while (!yigin.isEmpty()) cikti.append(yigin.pop());
  return cikti.toString();
}

Öncelikleri veren yardımcı metot:

int oncelik(char op) {
  switch (op) {
    case '+': case '-': return 1;
    case '*': case '/': return 2;
    default: return 0;   // '('
  }
}

Kod, Tablo 7.19'daki beş kuralı sırasıyla uygular. Character.isLetterOrDigit(c) bir harf ya da rakam için doğrudur; bunlar işlenendir ve cikti'ya eklenir. StringBuilder, Java'da bir dizeyi parça parça kurmanın verimli yoludur: her append sona ekler. ( yığına konur. ) geldiğinde while (yigin.peek() != '(') döngüsü ('a kadar bütün operatörleri çıktıya taşır, ardından tek bir yigin.pop() ('ı atar. Öteki her karakter operatördür: while döngüsü, üstteki operatörün önceliği gelen operatörünkinden küçük olmadığı sürece çıkarma yapar; sonra gelen operatör yığına konur. Girdi bitince kalan operatörler sırayla çıktıya eklenir.

Kodda “üstte ( yoksa” koşulu açıkça yazılmamıştır. Bu koşulu oncelik metodu sağlar: ( için default dalı çalışır ve 0 döner. Her gerçek operatörün önceliği en az 1 olduğu için oncelik('(') >= oncelik(c) hiçbir zaman doğru olmaz. Yani operatör geldiğinde ( hiçbir zaman çıkarılmaz; onu yalnız ) atar.

Kodun bazı varsayımları vardır: işlenenler tek karakterlidir (A, B, 5 gibi), yalnız + − * / operatörleri kullanılır (^ yoktur), ifadede boşluk yoktur ve ifade geçerlidir. Geçersiz bir ifadede, örneğin eşi olan ( bulunmayan bir ) varsa, yigin.peek() boş yığında null döndürür ve null != '(' karşılaştırması Character'ı char'a açmaya çalışırken NullPointerException fırlatır.

7.5.5Kod izleme: A*(B+C)/D

Belirleyici an / okunduğunda gelir. Yığında * vardır ve iki operatörün önceliği eşittir. ≥ kuralı *'ı çıktıya alır: ara ekte * soldadır ve önce yapılır. * yığında bırakılsaydı sonuç A B C + D / * olurdu; bu da A * ((B + C) / D) demektir. Sonuç A B C + * D /, Örnek 7.6'daki elle bulunan sonekle aynıdır.

7.5.6Kod izleme: A+B*C-D/E

Parantezsiz bu ifadede bütün iş öncelik kurallarına kalır.

* okunduğunda üstteki +'nın önceliği daha düşüktür; + beklemeye devam eder ve * onun üstüne konur. Bu, “çarpma önce yapılır” kuralının yığındaki karşılığıdır. - okunduğunda iki operatör birden çıkar: önce daha yüksek öncelikli *, sonra eşit öncelikli +. Girdi bittiğinde yığın üstten alta boşaltılır: önce /, sonra −. Sonuç A B C * + D E / −, yani (A + B·C) − D/E'dir.

7.5.7Sonek ifadeyi değerlendirme

Sonek gösterimin ödülü, değerlendirmenin son derece basit olmasıdır. İfade soldan sağa okunur:

1. Sayı gelirse yığına push edilir.
2. Operatör gelirse yığından iki öğe pop edilir: önce sağ, sonra sol işlenen. İşlem yapılır ve sonuç yığına push edilir.
3. İfade bitince yığında tek öğe kalır: sonuç.

Parantez de öncelik de gerekmez; her simge bir kez işlenir ve süre O(n)'dir.

Yardımcı metot, iki işlenen ve bir operatörle hesabı yapar:

int hesapla(int sol, char op, int sag) {
  switch (op) {
    case '+': return sol + sag;
    case '-': return sol - sag;
    case '*': return sol * sag;
    default:  return sol / sag;
  }
}

Değerlendirme metodu:

int postfixDegerlendir(String ifade) {
  Deque<Integer> yigin = new ArrayDeque<>();
  for (char c : ifade.toCharArray()) {
    if (Character.isDigit(c)) {
      yigin.push(c - '0');
    } else {
      int sag = yigin.pop();
      int sol = yigin.pop();
      yigin.push(hesapla(sol, c, sag));
    }
  }
  return yigin.pop();
}

Character.isDigit(c) rakamları tanır. c - '0', bir rakam karakterini sayı değerine çevirir: Java'da karakterler sayı kodlarıyla saklanır ve '0''dan '9''a kadar kodlar ardışıktır; '7' - '0' bu yüzden 7'dir. Operatör geldiğinde ilk pop sag'a, ikinci pop sol'a atanır ve hesapla(sol, c, sag) çağrılır. Döngü bitince son pop sonucu döndürür. Kodun varsayımları şunlardır: sayılar tek basamaklıdır, boşluk yoktur ve ifade geçerlidir. / tamsayı bölmesidir; 7 / 2 3 verir.

Neden önce sağ işlenen çıkar? Sol işlenen ifadede daha önce okunmuş, dolayısıyla yığına daha önce konmuştur ve altta durur. Sağ işlenen en son konmuştur ve üsttedir. Toplama ve çarpmada sıra fark etmez, ama çıkarma ve bölmede eder: 5 2 − ifadesinde 5 önce, 2 sonra push edilir. İlk pop 2'yi (sag), ikincisi 5'i (sol) verir ve sonuç 5 − 2 = 3'tür, 2 − 5 = −3 değil.

7.5.8Kod izleme: postfixDegerlendir()

Örnek 7.6'daki A B C + * D / ifadesinde A = 4, B = 1, C = 2, D = 3 konursa sonek dize "412+*3/" olur. Ara ek karşılığı 4 · (1 + 2) / 3 = 4'tür.

Yığın, değerlendirme boyunca “henüz bir operatöre işlenen olmamış ara sonuçları” tutar. + geldiğinde 1 ve 2 bu rolü bitirir, yerlerini 3 alır. Yığındaki öğe sayısının seyri (1, 2, 3, 2, 1, 2, 1) ifadenin geçerliliği hakkında da bilgi verir: her sayı yığını bir büyütür, her ikili operatör bir küçültür. Geçerli bir sonek ifadede bu sayı hiçbir operatörde 2'nin altına inmeden işlem yapılabilir ve sonda tam 1'e iner.

7.5.9Ara ekten öneke

Ara ek ifadeyi önek biçime çevirmek için yeni bir algoritma yazmak gerekmez. Soneke dönüşüm algoritması, küçük bir değişiklikle ve iki ters çevirme adımıyla birlikte kullanılır:

1. Ara ek ifade ters çevrilir.
2. Parantezler değiştirilir: ( ↔ ).
3. Soneke dönüşüm algoritması uygulanır; ama eşit öncelikte çıkarma yapılmaz, yalnız önceliği daha büyük (>) olanlar çıkarılır.
4. Çıktı ters çevrilir.

Yöntemin mantığı şudur: önek gösterim, ifadenin “aynadaki” sonekidir. İfade ters çevrilince operatörlerin işlenenlerine göre konumu da ters döner; sağdaki işlenen sola geçer. Ters çevrilmiş ifadenin soneki bulunup yeniden ters çevrilince operatör işlenenlerinin önüne geçer. Ters çevirme parantezlerin yönünü de bozduğu için 2. adımda düzeltilir.

3. adımdaki “eşitte çıkarma yok” kuralı birleşme yönünü korumak içindir. Ters çevirmek soldan birleşmeyi sağdan birleşmeye dönüştürür. Ters ifadede * geldiğinde üstte eşit öncelikli / vardır; / çıkarılmaz ve * onun üstüne konur. Böylece * önce çıkar ve önce yapılır. Ters çevirince ilk işlem önce A * (B + C), sonra / D olarak korunur. Eşitte çıkarma yapılsaydı 3. adımın çıktısı D C B + / A *, önek de * A / + B C D olurdu; bu, 7.5.1'de gösterilen yanlış öneğin ta kendisidir.

İkinci örnek A + B * C − D / E için aynı yöntem − + A * B C / D E verir; bu da Örnek 7.6'daki elle bulunan sonuçtur.

7.5.10Kod izleme: infixToPrefix()

String ters(String s) {
  return new StringBuilder(s).reverse().toString();
}
String infixToPrefix(String ifade) {
  String t = ters(ifade);          // 1. ters çevir
  t = parantezCevir(t);            // 2. ( ↔ )
  String p = prefixIcinPostfix(t); // 3. eşitte pop yok
  return ters(p);                  // 4. ters çevir
}
// main içinde:
System.out.println(infixToPrefix("A*(B+C)/D"));

Metot dört adımı dört satırda yapar. ters, StringBuilder'ın hazır reverse() metoduyla dizeyi ters çevirir. parantezCevir, her ('ı )'ya ve her )'yı ('a çevirir; sunumda gövdesi verilmeyen bu yardımcı şöyle yazılabilir:

String parantezCevir(String s) {
  StringBuilder sb = new StringBuilder();
  for (char c : s.toCharArray()) {
    if (c == '(') sb.append(')');
    else if (c == ')') sb.append('(');
    else sb.append(c);
  }
  return sb.toString();
}

prefixIcinPostfix, infixToPostfix'in kopyasıdır; tek fark operatör dalındaki karşılaştırmadır. Döngüsü şöyledir:

for (char c : ifade.toCharArray()) {
  if (Character.isLetterOrDigit(c)) cikti.append(c);
  else if (c == '(') yigin.push(c);
  else if (c == ')') {
    while (yigin.peek() != '(')
      cikti.append(yigin.pop());
    yigin.pop();                  // '(' atılır
  } else {                        // operatör
    while (!yigin.isEmpty() &&
        oncelik(yigin.peek()) > oncelik(c))
      cikti.append(yigin.pop());
    yigin.push(c);
  }
}
while (!yigin.isEmpty()) cikti.append(yigin.pop());

Burada >= yerine > yazılmıştır: eşit öncelikli operatör yığında kalır. Ters çevrilmiş ve parantezleri değiştirilmiş "D/(C+B)*A" girdisinin izlemesi şöyledir:

p = "DCB+A*/" ters çevrilince "/*A+BCD" elde edilir ve main bunu yazdırır. Sonucu denetlemek için işlenenlere bakılabilir: A, B, C, D sırası korunmuştur.

Dört adımın her biri O(n)'dir: iki ters çevirme, bir parantez değişimi ve bir dönüşüm. Toplam süre de O(n)'dir.

7.5.11Önek ifadeyi değerlendirme

Önek ifade de bir yığınla değerlendirilir. Kurallar sonekteki gibidir, iki farkla: ifade sağdan sola okunur ve bir operatör geldiğinde ilk çıkan sol işlenendir. Sağdan sola okunduğunda sağ işlenen önce görülür ve yığına önce konur; sol işlenen sonra konur ve üstte durur.

Sonek ve önek değerlendirme, aynı yığın fikrinin iki yönlü uygulamasıdır. İkisinde de yığın, bir operatörü bekleyen işlenenleri tutar; fark yalnız okuma yönünde ve dolayısıyla işlenenlerin yığından çıkış sırasındadır.

7.6Sık yapılan hatalar ve ortak desen

Yığınla ilgili hataların çoğu birkaç tipe ayrılır. Not boyunca her konunun yanında verilen hatalar burada bir arada toplanmıştır; bir yığın kodunu gözden geçirirken kontrol listesi olarak kullanılabilir.

Yineleme sırası hatası, kütüphane sınıflarının iç yapısından gelir. java.util.Stack, Vector'dan türediği için öğeleri eklenme sırasıyla bir dizide tutar; toString() ve for-each döngüsü onları alttan üste verir. ArrayDeque ise push'ta öğeyi başa ekler; gezinme baştan, yani üstten başlar. 1, 2, 3 sırasıyla push edilen iki yığından Stack [1, 2, 3], ArrayDeque [3, 2, 1] yazdırır. İçerik aynıdır, ama çıktılar ters görünür.

Bölümdeki bütün problemlere geri dönüp bakıldığında tek bir desen görülür. Yığın, şu soru sorulduğunda doğru araçtır: “En son görülen ve henüz sonuçlanmamış öğe hangisi?” Parantez kontrolünde bu öğe en son açılmış ama henüz kapanmamış parantezdir. Çağrı yığınında en son çağrılmış ama henüz dönmemiş metottur. Sonek değerlendirmede henüz bir operatöre işlenen olmamış en son ara sonuçtur. Sonraki büyük öğe ve stock span'de, henüz “aşılmamış” en yakın adaydır. Hanoi'de, henüz yapılmamış en son alt görevdir. Bir problemde bu soru beliriyorsa, çözümün bir yığın kullanması büyük olasılıktır.

7.7Özet

• Yığın, ekleme ve çıkarmanın yalnız üstten yapıldığı bir ADT'dir ve LIFO (son giren ilk çıkar) düzeniyle çalışır. Temel işlemleri push, pop, top/peek, isEmpty ve size'dır; hepsi O(1)'dir. Bir öğeyi aramak O(n)'dir; n öğeli yığın O(n) bellek kullanır.
• Boş yığından çıkarma alt taşma, dolu sınırlı yığına ekleme taşmadır. Boş yığındaki davranış kütüphaneden kütüphaneye değişir; pop ve peek'ten önce isEmpty() denetlenir.
• Dizi tabanlı yığında top son öğenin indisidir, boş yığında −1'dir ve size = top + 1'dir. Nesne dizisinde çıkarılan hücreye null atanır. Dinamik dizi dolunca iki katına büyütülür; büyütme yapan push O(n), ama n push'un toplamı 3n'den az olduğu için push amortize O(1)'dir. Sabit miktarla büyütme O(n²) toplam maliyet verir.
• Bağlı liste tabanlı yığında üst, listenin başıdır; push başa ekler, pop baştan çıkarır, ikisi de O(1)'dir. Taşma yalnız bellek bitince olur; her düğüm ek bir referans taşır. Java'da yeni kodda Deque<E> y = new ArrayDeque<>() önerilir.
• Tarayıcıda geri/ileri iki yığınla, metot çağrıları çağrı yığınıyla yönetilir. Özyinelemenin derinliği kadar bellek gerekir; taban durumu olmayan özyineleme StackOverflowError verir.
• Parantez kontrolü, eşleşmemiş açık parantezleri yığında tutar ve O(n) zamanda üç hata türünü (yanlış sıra, kapanmamış, fazla kapanış) yakalar.
• Sonraki büyük öğe ve stock span, alttan üste azalan bir monoton yığınla O(n)'de çözülür, çünkü her öğe bir kez eklenir ve en çok bir kez çıkarılır. getMin()'i O(1) yapan yığın, ikinci bir yığında en küçükleri (<= ile) tutar.
• Hanoi kuleleri, alt görevleri ters sırayla push eden açık bir görev yığınıyla özyinelemesiz çözülür: 2ⁿ − 1 hamle, O(n) yığın.
• Ara ek ifade, operatör yığınıyla O(n)'de soneke çevrilir: üstteki operatörün önceliği ≥ gelenin önceliği olduğu sürece çıkarılır. Öneke dönüşüm: ters çevir, parantezleri değiştir, eşitte çıkarmadan soneke çevir, yeniden ters çevir. İşlenenlerin sırası üç gösterimde de aynıdır.
• Sonek değerlendirmede ifade soldan sağa okunur; operatörde ilk pop sağ, ikinci pop sol işlenendir. Önek ifade sağdan sola okunur ve ilk çıkan sol işlenendir.

7.8Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• yığın stack
• üst top
• push (üste ekleme) push
• pop (üstten çıkarma) pop
• LIFO last-in, first-out
• soyut veri tipi abstract data type (ADT)
• arayüz interface
• jenerik generic
• taşma overflow
• alt taşma underflow
• kapasite capacity
• dinamik dizi dynamic array
• amortize analiz amortized analysis
• bağlı liste linked list
• tek yönlü bağlı liste singly linked list
• düğüm node
• referans reference
• geri al undo
• çağrı yığını call stack
• çerçeve stack frame
• özyineleme recursion
• taban durum base case
• geri izleme backtracking
• parantez kontrolü balanced parentheses
• sonraki büyük öğe next greater element
• stock span stock span
• ara ek infix
• önek prefix
• sonek postfix
• derinlik öncelikli arama depth-first search (DFS)
• zaman karmaşıklığı time complexity
• alan karmaşıklığı space complexity

7.9Kendini Dene

1. Boş bir yığına sırayla push(7), push(2), pop(), push(9), top(), push(4), pop(), pop() uygulanıyor. Değer döndüren çağrılar ne döndürür ve sonda yığında ne kalır?

   Cevap

   İlk pop() 2'yi döndürür; yığın: 7. push(9)'dan sonra yığın 7 9'dur ve top() 9'u çıkarmadan döndürür. push(4)'ten sonra 7 9 4; ardından pop() 4'ü, sonraki pop() 9'u döndürür. Dönen değerler sırasıyla 2, 9, 4, 9'dur; sonda yığında yalnız 7 kalır.

2. gecerliMi("([]{})") ve gecerliMi("([]{)}") ne döndürür? Geçersiz olanda hata hangi karakterde fark edilir?

   Cevap

   İlki true döndürür: (, [ push; ] ['i çıkarır; { push; } {'yi çıkarır; ) ('ı çıkarır; sonda yığın boştur. İkincisi false döndürür: 4. indisteki ) geldiğinde yığın ( { durumundadır ve pop {'yi verir; eslesir('{', ')') yanlıştır. Son karakter } hiç okunmaz.

3. (A + B) * C − D / (E + F) ifadesinin sonek ve önek karşılıkları nedir?

   Cevap

   Tam parantezleme: (((A + B) * C) − (D / (E + F))). Sonek: A B + C * D E F + / −. Önek: − * + A B C / D + E F. Denetim: işlenenler iki gösterimde de A, B, C, D, E, F sırasındadır. infixToPostfix izlenirse - geldiğinde yığındaki * çıkarılır, / geldiğinde ise üstteki - daha düşük öncelikli olduğu için kalır.

4. 7 2 − 3 * 8 4 / + sonek ifadesinin değeri nedir? Her operatörden sonra yığında ne vardır?

   Cevap

   −: sağ 2, sol 7 → 5; yığın 5. *: sağ 3, sol 5 → 15; yığın 15. /: sağ 4, sol 8 → 2; yığın 15 2. +: sağ 2, sol 15 → 17. Değer 17'dir; ara ek karşılığı (7 − 2) · 3 + 8 / 4'tür.

5. Fiyatlar [50, 40, 45, 60, 55, 70] için span dizisi nedir? span metodu çalışırken toplam kaç pop yapılır?

   Cevap

   Span: [1, 1, 2, 4, 1, 6]. i = 2'de 45, 1. günü (40) atar ve 0. günde (50) durur: 2 − 0 = 2. i = 3'te 60, 2. ve 0. günleri atar, yığın boşalır: 3 + 1 = 4. i = 5'te 70, 4. ve 3. günleri atar, yığın boşalır: 6. Toplam 5 pop yapılır (1, 2, 0, 4, 3 indisleri); bu, eklenen 6 indisten azdır.

6. {3, 8, 2, 5, 1, 9} dizisi için sonraki büyük öğe dizisi nedir? i = 1 adımında yığından hangi değerler atılır?

   Cevap

   Sonuç [8, 9, 5, 9, 9, −1]'dir. Sağdan sola: 9 → −1; 1 → 9; 5, 1'i atar → 9; 2 → 5; i = 1'de 8 gelir, yığın alttan üste 9 5 2'dir ve 8, önce 2'yi sonra 5'i atar; üstte kalan 9 cevaptır. Son olarak 3 → 8.

7. Kapasitesi 2 olan ve dolunca iki katına büyüyen boş bir yığına 12 kez push yapılıyor. Kaç büyütme ve kaç kopyalama yapılır? Toplam maliyet 3n sınırının altında mıdır?

   Cevap

   Büyütmeler 3. push'ta (2 → 4, 2 kopya), 5. push'ta (4 → 8, 4 kopya) ve 9. push'ta (8 → 16, 8 kopya) yapılır: 3 büyütme, 14 kopya. Yazma sayısı 12'dir; toplam 26'dır ve 3 · 12 = 36'nın altındadır. Son kapasite 16'dır.

8. Yığınla yazılmış hanoi(2) hangi hamleleri yazdırır? İlk turdan sonra yığında (üstten alta) hangi görevler vardır?

   Cevap

   İlk turda (2,A,B,C) bölünür ve yığın üstten alta (1,A,C,B), (1,A,B,C), (1,B,A,C) olur. Sonraki üç turda bu görevler sırayla yapılır: A → B, A → C, B → C. Toplam 2² − 1 = 3 hamle.

9. Min yığında push'taki koşul x <= min.peek() yerine x < min.peek() yazılmış olsun. Boş yığına push(2), push(2), pop(), getMin() uygulanırsa ne olur?

   Cevap

   İlk 2 min'e eklenir; ikinci 2 için 2 < 2 yanlıştır ve eklenmez. pop() 2'yi çıkarır ve 2 == min.peek() doğru olduğu için min'deki tek 2 de silinir. y'de hâlâ 2 vardır, ama min boştur. getMin()'de min.peek() null döndürür; bu değer int'e açılırken NullPointerException fırlatılır.

10. / * 4 + 1 2 3 önek ifadesinin değeri nedir?

    Cevap

    Sağdan sola: 3, 2, 1 push edilir (yığın 3 2 1). +: sol 1 (ilk pop), sağ 2 → 3; yığın 3 3. 4 push; yığın 3 3 4. *: sol 4, sağ 3 → 12; yığın 3 12. /: sol 12, sağ 3 → 4. Değer 4'tür; ara ek karşılığı 4 · (1 + 2) / 3'tür.

7.10İleri okuma

• M. T. Goodrich, R. Tamassia ve M. H. Goldwasser, Data Structures and Algorithms in Java (6. baskı, 2014), Kesim 6.1: yığın ADT'sini, dizi ve bağlı liste gerçeklemelerini ve parantez eşleme ile HTML etiketi denetimini bu nottakine yakın bir Java koduyla anlatır.
• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Kesim 1.3: yığınları dinamik dizi ve bağlı listeyle gerçekler; Dijkstra'nın iki yığınla ifade değerlendirme algoritmasını kısa ve açık bir örnekle verir.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (3. baskı, 2009), Kesim 10.1 ve 17.4: yığının dizi gerçeklemesini ve dinamik tabloların amortize analizini daha biçimsel bir dille işler.

7.11Kaynaklar

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3. baskı, MIT Press, 2009.
2. E. W. Dijkstra, “Algol 60 translation: An Algol 60 translator for the X1 and Making a translator for Algol 60”, Rapor MR 35/61, Mathematisch Centrum, Amsterdam, 1961.
3. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6. baskı, Wiley, 2014.
4. R. Lafore, Data Structures and Algorithms in Java, 2. baskı, Sams, 2002.
5. Oracle, Java SE 17 API Specification: java.util.Deque ve java.util.ArrayDeque belgeleri.
6. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011.

İlgili sayfalar: Bölüm 7 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.