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

6.1Yığın: son giren ilk çıkar

Dizi ve bağlı liste, öğelere her yerden erişmeye izin verir. Dizide herhangi bir indise yazılabilir; listede herhangi bir düğümün arkasına düğüm eklenebilir. Yığın bu özgürlüğü bilerek kısıtlar. Öğeler yalnız bir uçtan girer ve yalnız aynı uçtan çıkar. Bu kesim yığını tanımlar ve bir işlem dizisi boyunca nasıl büyüyüp küçüldüğünü gösterir.

6.1.1Tanım

Gündelik hayatta yığına benzeyen pek çok düzen vardır. Mutfakta üst üste konmuş tabaklardan önce en üsttekini alırız. Masadaki kâğıt destesine yeni gelen evrak en üste konur ve ilk okunan da odur. Şekil 6.1 daha öğretici bir örnek verir: tek araç genişliğinde, bir ucu duvarla kapalı bir çıkmaz sokak. Araçlar sokağa A, B, C, D sırasıyla girmiştir. Sokaktan ilk çıkabilecek araç, girişe en yakın olan D'dir. A'nın çıkabilmesi için önce D'nin, sonra C'nin, sonra B'nin çıkması gerekir. Sokağın bir ucu kapalı olduğu için girişin tersi sırada çıkış zorunludur.

Tanımdaki önemli sözcük “yalnız”dır. Yığının içinde öğeler sıralıdır, ama bu sıraya dışarıdan yalnız tek bir noktadan dokunulur. Yığına öğe eklemeye push (üste ekleme), üstteki öğeyi çıkarmaya pop (üstten çıkarma) denir. Bu iki sözcük Türkçe metinlerde de çoğunlukla İngilizce hâliyle kullanılır; not da bu kullanımı izler.

Türkçe kaynaklarda stack için hem “yığın” hem “yığıt” sözcükleri geçer. Bu derste stack için “yığın” kullanılır. Öncelikli kuyrukların gerçeklendiği heap veri yapısı için ise “heap” sözcüğü korunur. C programlarında yığın fonksiyonlarının adları ders kitabı geleneğiyle yigit_ekle, yigit_al biçiminde kalmıştır. Bu adlar yalnız tanımlayıcıdır; kavramın adı yığındır.

6.1.2Yığının büyümesi ve küçülmesi

Boş bir yığına sırasıyla A, B, C, D ve E eklensin. Yığın dizi üzerinde tutulsun ve üst öğenin indisi top adlı bir değişkende saklansın. Boş yığında top −1'dir. Her eklemede top bir artar ve yeni öğe bu indise yazılır. Şekil 6.2 bu sürecin üç anını ve ardından yapılan ilk silmeyi gösterir.

Her eklemeden sonra üst öğe değişir: A eklenince üst A'dır, B eklenince B'dir ve bu böyle sürer. E eklendiğinde yığında beş öğe vardır ve top 4'tür. Öğe sayısı her zaman top + 1'dir. Ardından yapılan ilk silme E'yi verir, çünkü üstte E vardır. Bütün öğeler tek tek çıkarılsaydı çıkış sırası E, D, C, B, A olurdu. Bu, giriş sırasının tam tersidir.

Yığının ortasındaki bir öğeye, örneğin B'ye, doğrudan ulaşılamaz. B'yi almak için üstündeki C, D ve E'nin önce çıkarılması gerekir. Bu kısıt bir kusur değil, bir sözleşmedir. Yığını kullanan program, “en son açılan iş ilk kapanır” kuralının geçerli olduğu bir sorunla uğraşır. Yapının bu kurala başka bir şey izin vermemesi programı yalınlaştırır ve hatayı zorlaştırır. Yığının kullanıldığı her yerde bu kural vardır.

6.2Yığın soyut veri tipi

Bir veri yapısını önce “ne yapar” sorusuyla, sonra “nasıl yapar” sorusuyla ele almak, programı değiştirilebilir kılar. Soyut veri tipi (abstract data type, ADT), bir değerler kümesini ve bu değerler üzerinde tanımlı işlemleri, nasıl gerçeklendiklerinden bağımsız olarak tanımlar. Yığın ADT'si, yığının hangi işlemleri sunduğunu ve bu işlemlerin hangi koşullarda hata verdiğini söyler. Diziyle mi, listeyle mi gerçeklendiğini söylemez.

6.2.1İşlemler ve ön koşullar

Tablo 6.1 yığın ADT'sinin altı işlemini Horowitz–Sahni'nin ders kitabındaki adlarla verir. İşlemlerin yanındaki push, pop ve peek sözcükleri aynı işlemlerin yaygın İngilizce adlarıdır.

Tablodaki iki hata durumunun adları vardır. Dolu bir yığına öğe eklenmek istenmesine taşma (overflow), boş bir yığından öğe alınmak istenmesine alt taşma (underflow) denir. Taşma, yığının bir kapasitesi olduğu varsayımına dayanır. Kâğıt üzerindeki soyut yığın sınırsızdır; ama her gerçek bellek sonludur. Bu yüzden ADT, yigit_olustur işlemine bir max değeri verir ve yigit_dolu sorgusunu tanımlar.

Alt taşma ise kapasiteden bağımsızdır. Boş bir yığının üst öğesi yoktur; ondan öğe istemek anlamsızdır. yigit_al ve yigit_ust işlemlerinin ön koşulu “yığın boş değil”dir. Bu ön koşulu kimin denetleyeceği bir tasarım kararıdır. Çağıran taraf her pop'tan önce yigit_bos'u sorabilir. İşlemin kendisi de denetleyip bir hata kodu döndürebilir. İkinci yol daha güvenlidir, çünkü denetimi unutmak mümkün olmaz.

ADT'nin asıl değeri, kullanan kodla gerçekleyen kodu ayırmasıdır. Aynı altı işlem sabit bir diziyle, gerektikçe büyüyen bir diziyle ya da bağlı listeyle gerçeklenebilir. Yalnız ADT'deki işlemleri çağıran bir program, gerçekleme değiştiğinde değişmez. Notta bu üç gerçekleme sırayla kurulur ve aynı işlemlerin maliyetleri karşılaştırılır.

6.2.2Yığının kullanıldığı yerler

Yığın, bilgisayar bilimindeki en çok kullanılan yapılardan biridir. Kullanım alanlarının ortak noktası, işlerin iç içe açılıp kapanmasıdır. İçteki iş dıştakinden önce biter. Aşağıdaki örneklerin her birinde yığının üstü “şu an açık olan en içteki işi” tutar.

Çağrı yığını

Her fonksiyon çağrısı, dönüş adresi ve yerel değişkenleriyle birlikte bir çerçeveyi yığına iter. Fonksiyon dönünce çerçeve çıkarılır. En son çağrılan fonksiyon ilk biter.

İfade değerlendirme

Derleyiciler a + b * c gibi ara ek (infix) bir ifadeyi önce sonek (postfix) gösterime çevirir. Bu ifadenin sonek biçimi a b c * +'dır. Derleyici sonra bu gösterimi bir yığınla hesaplar. Sonek ifadede her sayı yığına itilir, her işleç üstteki iki değeri alıp sonucu geri iter.

Geri izleme

Labirentte yol arayan bir program her yol ayrımını yığına koyar. Çıkmaza girince yığının üstündeki, yani en son geçilen ayrıma döner ve oradan başka bir yol dener.

Parantez denetimi

Bir ifadedeki her kapanan parantez, en son açılan ve henüz kapanmamış parantezle eşleşmelidir. “En son açılan” sözü yığını doğrudan çağrıştırır.

Geri al

Bir metin düzenleyici yapılan her işlemi bir yığına koyar. Geri al komutu (Ctrl+Z) yığının üstündeki, yani en son yapılan işlemi geri alır. İkinci basış bir önceki işlemi geri alır.

Derinlik öncelikli arama

Bir çizgede derinlik öncelikli arama (depth-first search, DFS), ziyaret edilecek düğümleri bir yığında tutar. Böylece en son keşfedilen yoldan olabildiğince derine gidilir.

Sunumdaki etkileşimli yığın aracı bu kuralı tek düğmeyle gösterir. Dört kez push, ardından dört kez pop yapıldığında çıkan sıra, giren sıranın tersidir. Beşinci pop boş yığına yapılır ve araç bunu alt taşma olarak bildirir.

6.2.3Parantez denetimi

Kullanım alanlarından biri, yığının neden doğal bir seçim olduğunu kısa bir kodla gösterir. Bir dizgedeki (, [ ve { parantezlerinin dengeli olup olmadığı sorulsun. Dengeli bir dizgede her kapanan parantezin bir açanı vardır, türleri uyar ve sonunda açık parantez kalmaz. {a[i] = (b + c) * d;} dengelidir. ([)] dengeli değildir: sayılar tutar, ama ) geldiğinde en son açılan parantez ['dir.

Aşağıdaki fonksiyon, bir dizi ile üst indisini aynı yapıda tutan Yigit tipini kullanır. push ve pop başarı durumunu bool olarak döndürür; pop çıkardığı değeri ikinci argümanın gösterdiği yere yazar.

/* (, [ ve { için denge denetimi: her kapanan, en son açılanla eşleşmeli */
bool dengeli(const char *s) {
    Yigit y;  int ac;
    yigit_baslat(&y);
    for (int i = 0; s[i] != '\0'; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            if (!push(&y, c)) return false;       /* çok derin */
        } else if (c == ')' || c == ']' || c == '}') {
            if (!pop(&y, &ac)) return false;      /* açılmamış kapanış */
            if ((c == ')' && ac != '(') || (c == ']' && ac != '[') ||
                (c == '}' && ac != '{'))
                return false;                     /* tür uyuşmuyor */
        }
    }
    return yigit_bos(&y);                         /* açık kalan var mı? */
}

Fonksiyon dizgeyi soldan sağa bir kez tarar. Açan bir parantez görünce onu yığına iter. Kapanan bir parantez görünce yığının üstündeki açanı çeker. Yığın o anda boşsa, kapanan parantezin açanı yoktur ve sonuç yanlıştır. Yığından çıkan açanın türü kapananınkiyle uymuyorsa sonuç yine yanlıştır. Parantez olmayan karakterler atlanır. Tarama bittiğinde yığında öğe kalmışsa bazı parantezler hiç kapanmamıştır. Bu yüzden fonksiyon en sonda yığının boş olup olmadığını döndürür.

Fonksiyon şu girdilerle denendi: {a[i] = (b + c) * d;} ve x = f(a[2], {1, 2}); için 1 (doğru), ([)], ((), ()) ve ] için 0 (yanlış) döndü. Boş dizge dengelidir ve 1 döner. Her karakter en çok bir push ve bir pop doğurur. Push ve pop sabit sürdüğü için n karakterlik dizgede süre Θ(n)'dir. En kötü durumda bütün karakterler açan parantezdir ve yığın n öğe tutar; ek bellek O(n)'dir.

6.3Dizi ile yığın

Yığını gerçeklemenin en kısa yolu tek boyutlu bir dizidir. Dizinin 0 numaralı hücresi yığının altıdır. Öğeler 1, 2, 3 numaralı hücrelere doğru yukarı dizilir. Üst öğenin indisi ayrı bir tamsayı değişkende, top'ta tutulur. Bu kesim önce top değişkeninin anlamını ve iki sınır durumunu, sonra Horowitz–Sahni'nin C kodunu satır satır ele alır.

6.3.1top indisi, taşma ve alt taşma

Dizi yığınında bütün bilgi iki şeydedir: dizinin içeriği ve top'un değeri. top, yığının üstündeki öğenin indisidir. Yığında k öğe varsa bu öğeler yigit[0]'dan yigit[k−1]'e kadar olan hücrelerdedir ve top = k − 1'dir. Yığın boşken hiçbir öğe yoktur; bu durumda top = −1 seçilir. −1 geçerli bir indis değildir, ama ilk eklemede top bir artırılınca tam olarak 0 olur. Bu seçim kodu yalınlaştırır.

Şekil 6.3 iki sınır durumunu yan yana gösterir. Yığının boş olup olmadığı top < 0 sınamasıyla anlaşılır. Dizinin MAX_STACK_SIZE hücresi varsa son geçerli indis MAX_STACK_SIZE − 1'dir. top bu değere ulaştığında yığın doludur ve top ≥ MAX_STACK_SIZE − 1 sınaması doğru olur. Öğe sayısı her zaman top + 1'dir. top ile öğe sayısını karıştırmak, “bir eksik ya da bir fazla” (off-by-one) hatalarının en bilinen kaynağıdır. Örneğin dolu denetimini top ≥ MAX_STACK_SIZE diye yazan bir program, dizinin son hücresinin bir ötesine yazar.

C, dizi sınırlarını çalışma sırasında denetlemez. yigit[MAX_STACK_SIZE] ifadesi derlenir ve çalışır; ama dizinin hemen arkasındaki bellek hücresine erişir. Orada başka bir değişken varsa onun değeri bozulur. Program hemen çökmeyebilir ve hata çok sonra, ilgisiz bir yerde ortaya çıkar. Bu yüzden taşma ve alt taşma denetimi yığın kodunun isteğe bağlı bir süsü değildir. Denetimsiz bir push, komşu belleğin üzerine yazar.

6.3.2C tanımları

Horowitz–Sahni'nin ders kitabındaki ilk gerçekleme, yığını küresel bir dizi olarak tanımlar:

#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 101

typedef struct {
    int deger;
    /* diğer alanlar */
} element;

element yigit[MAX_STACK_SIZE];

void yigit_dolu(void) {
    printf("Yigit dolu!!!\n"); exit(-1);
}
void yigit_bos(void) {
    printf("Yigit bos!!!\n"); exit(-2);
}

#define MAX_STACK_SIZE 101 satırı yığının kapasitesini sabitler. Önişlemci, kodda geçen her MAX_STACK_SIZE'ı derlemeden önce 101 ile değiştirir. Kapasiteyi değiştirmek için bu satırı düzeltmek yeter.

element tipi, yığında saklanacak kaydı tanımlar. Şimdilik tek alanı vardır: deger. Yorum satırı, gerçek bir uygulamada bu kayda başka alanların da ekleneceğini hatırlatır. Örneğin bir labirent programı yığına satır, sütun ve yön bilgisini birlikte koyar. Öğeyi int yerine bir struct olarak tanımlamak, yığın kodunu öğenin içeriğinden bağımsız kılar. Kayda alan eklendiğinde yığın yordamları değişmez, çünkü onlar yalnız element değerlerini kopyalar.

element yigit[MAX_STACK_SIZE]; satırı yığının kendisidir. Bu dizi her fonksiyonun dışında tanımlandığı için bir küresel değişkendir (global variable). Programın bütün fonksiyonları ona doğrudan erişebilir. Küresel diziler sıfırla başlatılır ve program boyunca yaşar. top ise küresel değildir: çağıran fonksiyonda (çoğunlukla main'de) yerel bir değişken olarak tanımlanır ve yığın yordamlarına adresiyle aktarılır.

Son iki fonksiyon hata yordamlarıdır. yigit_dolu bir mesaj basıp programı exit(-1) ile, yigit_bos ise exit(-2) ile sonlandırır. exit, <stdlib.h>'de bildirilir ve hangi fonksiyonun içinden çağrılırsa çağrılsın bütün programı bitirir. Verilen sayı programın çıkış kodudur ve işletim sistemine iletilir. Unix türü sistemlerde kabuk −1'i 255 olarak görür; Windows'ta bu kod 4294967295 olarak raporlanır. Bu iki fonksiyonun adı ADT'deki yigit_dolu ve yigit_bos sorgularıyla aynıdır, ama işleri farklıdır: sorgu yapmaz, hata bildirir. Ad çakışması bu ilk gerçeklemenin kusurlarından biridir; daha iyi bir tasarımda bu adlar gerçek sorgulara verilir.

Ders kitaplarında bu tanımlar tek bir dosyada, küresel dizi ve küresel top ile verilir. Dersin sınavlarında ve ödevlerinde ise küresel değişken yasaktır. Bunun nedeni basittir. Küresel bir değişkeni programın her fonksiyonu değiştirebilir. Bir hata çıktığında değişkeni kimin bozduğunu bulmak için bütün programı okumak gerekir. Ayrıca aynı programda iki yığın gerektiğinde küresel tek dizi işe yaramaz. Bu bölümde küresel dizi yalnız ders kitabındaki kodu tanımak için kullanılır; ödevlerde yığın, kuyruk ya da başka bir yapı neyse yerel olarak tanımlanıp parametreyle aktarılır.

6.3.3yigit_ekle ve yigit_al

Ekleme ve çıkarma yordamları üçer satırdır:

void yigit_ekle(int *top, element item) {
    if (*top >= MAX_STACK_SIZE - 1)  /* yer var mı? */
        yigit_dolu();         /* uyar ve çık */
    yigit[++*top] = item;     /* önce işaretçiyi artır */
}                             /* sonra öğeyi yerleştir */

element yigit_al(int *top) {
    if (*top < 0)
        yigit_bos();          /* boşsa uyar ve çık */
    return yigit[(*top)--];   /* döndür, sonra azalt */
}

yigit_ekle iki parametre alır. int *top, çağırandaki top değişkeninin adresidir. element item, eklenecek öğenin bir kopyasıdır. İlk satır yer olup olmadığını sınar. *top, top işaretçisinin gösterdiği tamsayıdır, yani çağırandaki üst indisidir. Bu değer MAX_STACK_SIZE − 1'e ulaşmışsa yığın doludur ve yigit_dolu() programı bitirir. Yer varsa son satır çalışır: yigit[++*top] = item;. Bu satır iki iş yapar. Önce *top bir artar, sonra öğe yeni indise yazılır. Boş yığında *top −1'den 0'a çıkar ve öğe yigit[0]'a yazılır.

yigit_al yalnız top'un adresini alır. Yığın boşsa, yani *top < 0 ise yigit_bos() programı bitirir. Değilse return yigit[(*top)--]; satırı çalışır. Bu satır da iki iş yapar, ama ters sırada. Önce eski indisteki öğe okunur, sonra *top bir azalır. Okunan öğe fonksiyonun dönüş değeridir. Örneğin *top 2 iken yigit[2] döner ve *top 1 olur.

Çıkarılan öğe diziden silinmez. yigit[2] hücresinde eski değer durmaya devam eder. Ama artık yığının parçası değildir, çünkü yığının içeriğini top belirler: geçerli öğeler 0'dan top'a kadar olan hücrelerdir. Bir sonraki ekleme bu hücrenin üzerine yazar. Silmenin bir hücreyi temizlemek değil, sınırı aşağı çekmek olması, dizi yığınını hızlı yapan şeydir.

top neden adresle aktarılır? C'de bütün argümanlar değerle çağrı (call by value) kuralıyla aktarılır. yigit_ekle(top, item) diye bir çağrı, top'un değerinin bir kopyasını fonksiyona verirdi. Fonksiyon bu kopyayı artırır, ama çağırandaki top değişmezdi. Sonraki ekleme aynı hücreye yazardı. Çağıranın değişkenini değiştirmek isteyen bir fonksiyona o değişkenin adresi verilir: yigit_ekle(&top, item). Fonksiyon *top üzerinden çağırandaki asıl değişkene erişir.

Bu noktada bir yazım kuralı önemlidir. Fonksiyonun parametre listesinde *top diye görünen bir parametre, fonksiyonun içinde de her yerde *top olarak kullanılmalıdır. İçeride yalnız top yazılırsa işaretçinin kendisi, yani bir adres kullanılmış olur. if (top >= MAX_STACK_SIZE - 1) gibi bir sınama adresi bir tamsayıyla karşılaştırır. Derleyici en iyi durumda bir uyarı verir; program ise anlamsız bir karşılaştırma yapar. Sınavlarda bu hata çok sert değerlendirilir, çünkü işaretçi ile gösterdiği değer arasındaki farkı bilmemek, bu dersteki bütün yapıları yanlış kurmak demektir.

İki yordamın maliyeti de O(1)'dir. Her biri bir karşılaştırma, bir indis değişikliği ve bir dizi erişimi yapar. Bu işlerin sayısı yığındaki öğe sayısına bağlı değildir. Ek bellek de sabittir: yalnız parametreler kullanılır.

6.3.4Öncelik tuzağı: * ile ++ ve --

yigit[++*top] ve yigit[(*top)--] ifadeleri kısa ama dikkat ister. İlkinde parantez yoktur, ikincisinde vardır. Bu farkın nedeni C'deki işleç önceliğidir. Tablo 6.2 dört yazımı karşılaştırır.

Kural şöyledir. Son ek ++ ve -- işleçleri, tekli * işlecinden daha önceliklidir. Bu yüzden *top-- ifadesinde -- önce top'a bağlanır: azalan şey işaretçinin kendisidir. Ön ek ++ ile tekli * ise aynı öncelik düzeyindedir ve sağdan sola bağlanır. ++*top ifadesinde önce sağdaki * uygulanır, ++ onun sonucuna, yani gösterilen tamsayıya bağlanır. Bu yüzden push'ta parantez gerekmez, pop'ta gerekir.

(*top)-- yerine *top-- yazılırsa ne olur? İfade *(top--) olarak okunur. top--, işaretçinin eski değerini verir ve işaretçiyi bir int geriye kaydırır. * bu eski adresi okur. Okunan değer çağırandaki üst indisidir; dizi doğru hücreden okunur. Ama azalan şey yerel top işaretçisidir. Fonksiyon bitince bu yerel kopya yok olur. Çağırandaki top hiç değişmemiştir. Bu tür bir hata bu yüzden çok sinsidir: ilk pop doğru değeri döndürür.

Bu tuzaktan kaçınmanın en sağlam yolu, işaretçi üzerinden yapılan artırma ve azaltmayı ayrı bir satıra almaktır: önce (*top)++;, sonra yigit[*top] = item;. Kod bir satır uzar, ama okuyan herkes ne olduğunu hemen anlar. Ders kitabındaki kısa yazım da doğrudur; yeter ki parantezin neden orada olduğu bilinsin.

6.3.5Kod izleme

Yordamların davranışı küçük bir kapasiteyle daha iyi görülür. İzlemede MAX_STACK_SIZE = 4 alınır; dolu denetimi bu yüzden *top ≥ 3'tür. main'de top = −1 iken sırasıyla A, B, C eklenir, bir öğe alınır, sonra D, E ve F eklenmeye çalışılır. Tablo 6.3 her çağrıdan sonraki durumu verir.

Tablonun beşinci satırı dizinin silmeyi nasıl yaptığını gösterir. yigit_al C'yi döndürür ve top'u 1'e indirir. 2 numaralı hücrede C hâlâ durur. Altıncı satırda D eklenince aynı hücreye D yazılır ve C'nin izi kalmaz. Son satırda yer yoktur. yigit_dolu mesajı basar ve exit(-1) ile bütün programı bitirir. Bu davranış derlenip çalıştırılarak doğrulandı: program “ekle F ... Yigit dolu!!!” yazdı ve Windows çıkış kodunu 4294967295, yani −1 olarak raporladı.

Taşma anında bütün programı bitirmek kaba bir tepkidir. Yığın küçük bir kütüphane parçasıdır; programın geri kalanının ne yapacağını bilemez. Belki çağıran, yığın dolunca daha büyük bir yığın kuracaktı. Belki kullanıcıya bir mesaj gösterip işlemi iptal edecekti. exit bu kararları elinden alır. Ayrıca açık dosyaların düzgün kapatılması, ayrılmış belleklerin bırakılması gibi temizlik işleri de yapılamadan program biter. Daha iyi tasarım, hatayı çağırana bildirip kararı ona bırakmaktır.

6.4Yığını bir nesne gibi tasarlamak

Ders kitabındaki ilk gerçeklemenin üç zayıflığı vardır. Yığın küresel bir dizidir; bu yüzden programda yalnız bir yığın olabilir. top diziden ayrı yaşar; çağıran onu ayrıca tanımlayıp her çağrıya ayrıca vermek zorundadır. Hata durumunda program exit ile biter. Bu kesim üç sorunu birlikte çözen bir tasarım kurar: dizi ve üst indisi aynı yapıda durur, yordamlar yığını parametre olarak alır ve hata bir dönüş değeriyle bildirilir.

6.4.1Küresel dizi yerine struct

#include <stdbool.h>
#define KAP 100

typedef struct {
    int veri[KAP];
    int ust;               /* boşken -1 */
} Yigit;

void yigit_baslat(Yigit *y) { y->ust = -1; }
bool yigit_bos(const Yigit *y)  { return y->ust < 0; }
bool yigit_dolu(const Yigit *y) { return y->ust == KAP - 1; }
int  yigit_boyut(const Yigit *y) { return y->ust + 1; }
bool yigit_ust(const Yigit *y, int *x) {
    if (yigit_bos(y)) return false;
    *x = y->veri[y->ust];  return true;
}

Yigit yapısı iki alan taşır: KAP öğelik veri dizisi ve üst indisini tutan ust. Bir yığın artık tek bir değişkendir. Yigit a, b; tanımı birbirinden bağımsız iki yığın verir; her birinin kendi dizisi ve kendi üst indisi vardır. Biri dolarken öteki etkilenmez. Küresel değişken yoktur.

Her yordam yığını Yigit *y parametresiyle, yani adresiyle alır. Bunun iki nedeni vardır. Birincisi, push ve pop yığını değiştirir; değerle aktarılan bir kopya değişseydi çağırandaki yığın değişmezdi. İkincisi, Yigit büyük bir yapıdır: KAP = 100 iken yaklaşık 404 bayt tutar. Değerle aktarılsaydı her çağrıda bu 404 bayt kopyalanırdı. Adres ise 8 bayttır. Yapının alanlarına adres üzerinden ok işleciyle (->) erişilir: y->ust, (*y).ust'un kısa yazımıdır.

Yığını değiştirmeyen sorgular const Yigit *y alır. const niteleyicisi, fonksiyonun gösterilen yapıyı değiştirmeyeceğine söz verir. Fonksiyonun içinde y->ust = 0; gibi bir atama yazılırsa derleyici hata verir. Bu söz hem okuyana bilgi verir hem de yanlışlıkla yapılan değişiklikleri derleme sırasında yakalar.

Yordamların her biri tek satırdır. yigit_baslat, ust'u −1 yaparak boş yığın kurar. Yerel bir Yigit değişkeninin alanları başlangıçta belirsiz değerler taşır; bu yüzden her yığın kullanılmadan önce bir kez başlatılmalıdır. yigit_bos ve yigit_dolu artık gerçek sorgulardır ve bool döner. yigit_boyut öğe sayısını, yani ust + 1'i verir. yigit_ust, ADT'deki peek işlemidir. Yığın boşsa false döner ve *x'e dokunmaz. Değilse üst öğeyi *x'e yazar ve true döner. Değerin bir çıktı parametresiyle verilmesinin nedeni, dönüş değerinin başarı bilgisine ayrılmış olmasıdır. bool tipi ve true, false adları <stdbool.h> başlığından gelir.

Ekleme ve çıkarma da aynı düzenle yazılır:

bool push(Yigit *y, int x) {
  if (y->ust == KAP - 1) return false; /* taşma */
  y->veri[++y->ust] = x;
  return true;
}
bool pop(Yigit *y, int *x) {
  if (y->ust < 0) return false;   /* alt taşma */
  *x = y->veri[y->ust--];
  return true;
}

push önce taşmayı sınar. ust == KAP - 1 ise yer yoktur ve fonksiyon false döner. Program sürer; taşmayı öğrenen çağıran ne yapacağına kendisi karar verir. Yer varsa y->veri[++y->ust] = x; satırı önce ust'u artırır, sonra değeri yeni indise yazar. Burada öncelik tuzağı yoktur: -> işleci ++'dan önce uygulanır, yani ++y->ust ifadesi ++(y->ust) demektir.

pop önce alt taşmayı sınar. Yığın boşsa false döner ve *x'e dokunmaz. Değilse *x = y->veri[y->ust--]; satırı üst öğeyi *x'e kopyalar ve ardından ust'u bir azaltır. y->ust-- ifadesi de (y->ust)-- olarak okunur; azalan şey yapının alanıdır.

Bu sürüm hata durumunu dönüş değeriyle bildirdiği için kullanımı çok rahattır. Örneğin yığını boşaltırken her çıkan öğeyi yazdıran döngü tek satırdır: while (pop(&y, &x)) printf("%d ", x);. Döngü, pop ilk kez false döndüğünde, yani yığın boşaldığında durur. İşlemlerin hepsi yine O(1)'dir.

6.4.2Kod izleme: bool döndüren push ve pop

İzlemede KAP = 3 alınır; dolu denetimi ust == 2'dir. yigit_baslat(&y) ile boş yığın kurulur. Ardından sırasıyla 5, 8, 2 ve 9 itilir, sonra dört kez pop çağrılır. Tablo 6.4 her çağrıyı ve dönüş değerini verir.

İzleme bir test programıyla doğrulandı. Her push'un dönüş değerini yazdıran program “push 5:1 8:1 2:1 9:0” çıktısını verdi; 9 eklenemedi. Pop'lar sırasıyla 2, 8, 5 döndürdü, dördüncü pop false oldu. Aradaki ara sorgular da beklendiği gibi çalıştı: üç push sonrası yigit_boyut 3, yigit_dolu doğru ve yigit_ust 2 verdi.

İki gerçeklemenin farkı taşma satırında görülür. Küresel dizi sürümü bu noktada programı bitirirdi. bool sürümü ise false döner ve program kaldığı yerden sürer. Örnekte 9'un eklenemediğini çağıran öğrenir. İsterse kullanıcıya bir uyarı basar, isterse 9'u başka bir yere koyar. Tek bir yordamın bütün programın kaderini belirlemesi böylece önlenir.

6.4.3Arayüz ve gerçekleme

struct sürümü de hâlâ bir sorun taşır. Yigit yapısının alanları onu kullanan her koda açıktır. Kullanan bir programcı y.ust = 5; yazıp yığını bozabilir ya da y.veri[0]'a doğrudan erişip yığın kuralını delebilir. Daha büyük bir sorun da şudur: yığının gerçeklemesi değiştiğinde, örneğin dizi bağlı listeye çevrildiğinde, alanlara doğrudan erişen bütün kodlar bozulur.

C'de bu sorun, kodu bir başlık dosyası (header file) ve bir kaynak dosyası olarak ikiye bölerek çözülür. Başlık dosyası arayüzü (interface), yani dışarıya açılan tipleri ve fonksiyon bildirimlerini taşır. Kaynak dosyası gerçeklemeyi (implementation), yani bu fonksiyonların gövdelerini ve yapının içini taşır.

/* yigit.h: kullanıcı yalnız bunu görür */
#ifndef YIGIT_H
#define YIGIT_H
#include <stdbool.h>
typedef struct Yigit Yigit;  /* opak */
Yigit *yigit_olustur(int kapasite);
void yigit_yok_et(Yigit *y);
bool yigit_ekle(Yigit *y, int x);
bool yigit_al(Yigit *y, int *x);
bool yigit_bos(const Yigit *y);
#endif

Başlık dosyasının ilk ve son satırları çoklu ekleme korumasıdır (include guard). Büyük bir programda aynı başlık bir kaynak dosyasına dolaylı yollardan iki kez eklenebilir. #ifndef YIGIT_H sınaması, YIGIT_H adı henüz tanımlı değilse dosyanın içeriğini işler ve hemen ardından bu adı tanımlar. İkinci eklemede ad tanımlı olduğu için içerik atlanır. Böylece aynı tipin iki kez tanımlanması hatası önlenir.

Asıl önemli satır typedef struct Yigit Yigit; satırıdır. Bu satır struct Yigit adında bir yapının var olduğunu söyler, ama alanlarını söylemez. Böyle yalnız adı bildirilen bir tipe eksik tip (incomplete type) denir. Alanları kullanıcıdan gizlenen bu tipe opak tip (opaque type) adı da verilir. Kullanan kod eksik bir tipin değişkenini tanımlayamaz, çünkü derleyici onun kaç bayt tuttuğunu bilmez. Alanlarına da erişemez. Yapabileceği tek şey, bu tipe bir işaretçi tutmak ve işaretçiyi başlıktaki fonksiyonlara vermektir. Yığın bu yüzden yigit_olustur ile oluşturulur ve yigit_yok_et ile yok edilir.

/* yigit.c: gerçekleme */
struct Yigit { int *veri; int ust, kap; };

Yigit *yigit_olustur(int kap) {
  Yigit *y = malloc(sizeof *y);
  if (y == NULL) return NULL;
  y->veri = malloc(kap * sizeof *y->veri);
  if (y->veri == NULL) {
    free(y);  return NULL;
  }
  y->ust = -1;  y->kap = kap;
  return y;
}
void yigit_yok_et(Yigit *y) {
  if (y) { free(y->veri); free(y); }
}

Kaynak dosyasında yapının tam tanımı vardır. Bu sürümde dizi yapının içinde sabit boyutlu değildir. veri bir işaretçidir ve dizinin kendisi yigit_olustur sırasında, istenen kapasiteyle heap bellekten ayrılır. Böylece her yığının kapasitesi ayrı ayrı seçilebilir.

yigit_olustur iki ayırma yapar. Önce yapının kendisi için malloc(sizeof *y) çağrılır. sizeof *y, y'nin gösterdiği tipin, yani struct Yigit'in boyutudur. Bu yazım, tip adı değişse bile doğru kalır. Ayırma başarısızsa NULL döner. Sonra kap öğelik dizi için malloc(kap * sizeof *y->veri) çağrılır. Bu ikinci ayırma başarısızsa önemli bir ayrıntı vardır: ilk ayrılan yapı bloğu free(y) ile iade edilir ve ancak ondan sonra NULL döner. Bu satır unutulsaydı yapının bloğu hiçbir değişkenin gösteremediği bir bellek parçası olarak kalırdı; yani bir bellek sızıntısı (memory leak) oluşurdu. İki ayırma da başarılıysa ust −1, kap istenen kapasite yapılır ve yapının adresi döner.

yigit_yok_et ayırma sırasının tersini izler. Önce dizi, sonra yapı iade edilir. Sıra önemlidir: önce yapı iade edilseydi y->veri alanı artık geçersiz bir bellekten okunurdu. if (y) sınaması fonksiyonun NULL ile de güvenle çağrılabilmesini sağlar. C standardına göre free(NULL) zaten hiçbir şey yapmaz; ama y->veri'yi okumak için y'nin geçerli olması gerekir.

Sunumdaki gerçekleme dosyası kısalık için başındaki #include satırlarını ve üç yordamı göstermez. Tam bir yigit.c şu satırlarla başlar: #include <stdlib.h> (malloc ve free için) ve #include "yigit.h" (bildirimlerle tanımların uyuştuğunu derleyicinin denetlemesi için). Eksik yordamlar, struct sürümündeki push, pop ve yigit_bos'un aynısıdır; tek fark, dolu denetiminin sabit KAP yerine yapının kap alanıyla yapılmasıdır: if (y->ust == y->kap - 1) return false;. Bu tamamlanmış hâliyle iki ayrı yığın (kapasite 2 ve 5) kuran bir test programı derlenip çalıştırıldı. Kapasitesi 2 olan yığına üçüncü ekleme false döndü; iki yığın da yok edildikten sonra sayaçlı bir malloc/free sarmalayıcısı dört ayırma ve dört iade saydı. Sızıntı yoktur.

Bu bölünmenin değeri, gerçekleme değiştiğinde görülür. yigit.c diziden bağlı listeye çevrilsin. struct Yigit'in içi tamamen değişir; veri ve kap alanları kalkar, yerine bir düğüm işaretçisi gelir. Ama yigit.h aynı kalır. Bu yüzden yığını kullanan bütün dosyalar hiç değiştirilmeden, yalnız yeniden bağlanarak çalışmaya devam eder. Soyut veri tipinin “ne” ile “nasıl”ı ayırması C'de böyle somutlaşır.

6.4.4Yığınla dizge ters çevirme

Yığının en basit uygulaması bir diziyi ters çevirmektir. Öğeler sırayla yığına itilir, sonra sırayla çekilir. Yığın son gireni ilk verdiği için çıkış sırası girişin tersidir. Aşağıdaki fonksiyon bir dizgeyi bu yolla yerinde ters çevirir; struct sürümünün push ve pop yordamlarını kullanır.

void ters_cevir(char *s) {
  Yigit y;  int c, i;
  yigit_baslat(&y);
  for (i = 0; s[i] != '\0'; i++)
    push(&y, s[i]);     /* KAP yeterli varsayıldı */
  for (i = 0; pop(&y, &c); i++)
    s[i] = (char)c;
}

Fonksiyonun yerel bir Yigit y değişkeni vardır. Yığın, fonksiyonun çerçevesinde yaşar ve fonksiyon dönünce kendiliğinden yok olur; malloc ve free gerekmez. İlk döngü, dizgenin sonundaki '\0' karakterine kadar her karakteri yığına iter. push'un dönüş değeri burada denetlenmez; yorumdaki varsayım, dizgenin KAP = 100 karakterden kısa olduğudur. İkinci döngü, pop başarılı olduğu sürece çekilen karakteri dizgenin i. konumuna yazar ve i'yi artırır. Yığın boşalınca pop false döner ve döngü biter.

c değişkeni int'tir, çünkü pop ikinci argüman olarak int * bekler. push(&y, s[i]) çağrısında char değeri otomatik olarak int'e genişler. Dizgeye geri yazarken (char)c dönüşümü bu değeri yeniden char'a indirir. Karakterler zaten char aralığından geldiği için bilgi kaybolmaz.

Girdi "YIGIT" olsun. Tablo 6.5 iki döngünün her adımını verir.

Tablodaki ara dizgeler ilk bakışta şaşırtabilir. Üç adım boyunca s “TIGIT” olarak görünür. Bunun nedeni, “YIGIT” kelimesinin ortadaki üç harfinin (I, G, I) kendi içinde simetrik olmasıdır. Yazılan harfler zaten orada bulunan harflerle aynıdır. Yalnız ilk ve son adım dizgeyi gerçekten değiştirir. Program çalıştırılarak doğrulandı: "YIGIT" için TIGIY, "ab" için ba verdi; boş dizge boş kaldı.

Maliyet açıktır. n karakterlik bir dizgede birinci döngü n push, ikinci döngü n pop ve bir başarısız pop yapar. Her işlem O(1) olduğundan toplam süre Θ(n)'dir. Yığın n karakteri birden tuttuğu için ek bellek de Θ(n)'dir. Aynı iş iki indisle, baştan ve sondan karakter takas ederek O(1) ek bellekle de yapılabilir. Yığınlı sürümün değeri, yığının sırayı tersine çevirme yeteneğini açıkça göstermesidir. Aynı yöntem, sırası tersine çevrilmek istenen ama uzunluğu baştan bilinmeyen her akış için de çalışır.

6.5Bağlı yığın

Dizi yığınının kapasitesi baştan seçilir. Kapasite küçük seçilirse yığın taşar; büyük seçilirse kullanılmayan hücreler boşa yer kaplar. Bağlı liste bu ikilemi ortadan kaldırır. Her öğe için ayrı bir düğüm ayrılır ve yığın tam olarak öğe sayısı kadar düğüm tutar. Bu kesim yığını tek yönlü bir bağlı listeyle kurar.

6.5.1Üst neden liste başıdır

Bağlı listede her öğe bir düğümdür (node). Düğüm iki alan taşır: öğenin değerini tutan deger ve bir sonraki düğümün adresini tutan bag. Düğüm tipi kendi tipinden bir işaretçi içerdiği için kendine başvuran bir yapıdır:

typedef struct dugum {
    int deger;
    struct dugum *bag;
} dugum;

Yığının hangi ucu listenin hangi ucuna denk gelmelidir? Tek yönlü bir listede iki uç eşit değildir. Liste başına ekleme ve liste başından silme O(1)'dir: yalnız baş işaretçisi ve bir bağ değişir. Liste sonuna ekleme de son düğüm ayrıca tutulursa O(1)'dir. Ama liste sonundan silmek için sondan bir önceki düğümün bağını NULL yapmak gerekir. Tek yönlü listede bir düğümden öncekine geri dönülemez; sondan bir önceki düğüm ancak baştan yürüyerek, O(n) sürede bulunur.

Yığında ekleme ve silme aynı uçtan yapıldığı için bu ucun liste başı olması gerekir. Yığının üstünü gösteren top işaretçisi bu yüzden listenin ilk düğümünü gösterir. Son eklenen öğe listenin başında, ilk eklenen öğe listenin sonundadır. Boş yığın, top'u NULL olan yığındır. Özetle iki seçenek vardır: ya iki işaretçi tutulup son düğüm de izlenir ve yine de silme yavaş kalır, ya da tek işaretçiyle baş tutulur ve her şey hızlı olur. Doğru seçim ikincisidir.

Şekil 6.7 A, B, C sırasıyla eklenmiş bir bağlı yığını gösterir. Okların yönüne dikkat etmek gerekir. Oklar üstten alta doğrudur: her düğüm kendinden önce eklenmiş düğümü gösterir. Bir pop, top'u bir ok ileri kaydırır ve C'yi listeden çıkarır. Kaydırma yoktur, kapasite sınırı yoktur. Yığın ancak malloc yeni bir düğüm için yer bulamadığında taşar.

6.5.2Bağlı push

bool push(dugum **top, int x) {
  dugum *yeni = malloc(sizeof *yeni);
  if (yeni == NULL) return false;  /* bellek yok */
  yeni->deger = x;
  yeni->bag = *top;      /* eski üstü göster */
  *top = yeni;           /* yeni üst */
  return true;
}

Fonksiyon dugum **top parametresi alır. Bu bir işaretçiye işaretçidir: çağırandaki top değişkeninin adresidir. Push, çağırandaki top'u yeni düğüme çevirecektir. Değerle aktarılan bir kopya değişseydi çağıranın top'u eski düğümü göstermeye devam ederdi ve yeni düğüm kaybolurdu. Bu yüzden çağrı push(&top, 10) biçiminde yapılır. Fonksiyonun içinde *top, çağırandaki top değişkeninin kendisidir.

Gövde dört adımdan oluşur:

1. dugum *yeni = malloc(sizeof *yeni); heap bellekten bir düğümlük yer ayırır. Ayırma başarısızsa malloc NULL döner ve fonksiyon false ile çıkar. Yığın bu durumda hiç değişmemiştir.
2. yeni->deger = x; değeri yeni düğüme yazar. malloc'un verdiği bellek temizlenmemiştir; alanlar bu atamaya kadar belirsiz değerler taşır.
3. yeni->bag = *top; yeni düğümün bağını eski üste çevirir. Yığın boşsa eski üst NULL'dır ve yeni düğümün bağı da NULL olur.
4. *top = yeni; çağırandaki top'u yeni düğüme çevirir. Yeni düğüm artık yığının üstüdür.

Üçüncü ve dördüncü adımın sırası kritiktir. Önce bağlanır, sonra üst değiştirilir. Sıra ters olsaydı *top = yeni; satırı eski üstün adresini kaybettirirdi. Ardından gelen yeni->bag = *top; yeni düğümü kendisine bağlardı. Eski listenin bütün düğümleri hiçbir değişkenin gösteremediği bir hâlde, sızmış bellek olarak kalırdı.

Boş bir yığına sırasıyla 10, 20, 30 itilsin. Tablo 6.6 her satırdan sonraki durumu verir. Tabloda düğüm(10), değeri 10 olan düğümün adresi anlamına gelir.

Üçüncü çizimdeki ara durum öğreticidir. Yeni düğüm hazırdır ve 20'yi gösterir, ama yığın hâlâ 20 → 10'dur. Yığının yapısı tek bir atamayla, *top = yeni satırında değişir. Bu düzen hata durumunda da güvenlidir: malloc başarısız olsaydı fonksiyon ilk denetimde dönerdi ve yığına hiç dokunulmamış olurdu. Her push sabit sayıda iş yapar: bir ayırma, üç atama. Yığının uzunluğu bu sayıyı etkilemez; push O(1)'dir. malloc'un kendi süresi de pratikte sabit kabul edilir, ama bir dizi hücresine yazmaktan çok daha pahalıdır.

6.5.3Bağlı pop

bool pop(dugum **top, int *x) {
  dugum *eski = *top;      /* malloc yok! */
  if (eski == NULL) return false;  /* boş */
  *x = eski->deger;
  *top = eski->bag;        /* üstü ilerlet */
  free(eski);              /* belleği bırak */
  return true;
}

Pop da dugum **top alır, çünkü çağırandaki top'u bir sonraki düğüme ilerletecektir. Çıkarılan değer int *x çıktı parametresiyle verilir; dönüş değeri başarıyı bildirir. Gövde şu adımlardan oluşur:

1. dugum *eski = *top; üst düğümün adresini yerel bir işaretçide saklar. Bu satır yeni bellek ayırmaz; yalnız bir adresi kopyalar.
2. if (eski == NULL) return false; yığın boşsa alt taşmayı bildirir.
3. *x = eski->deger; değeri çağırana kopyalar. Bu satır düğüm iade edilmeden önce çalışmalıdır.
4. *top = eski->bag; çağırandaki top'u bir sonraki düğüme ilerletir. Bu da iadeden önce yapılmalıdır, çünkü bağ alanı iade edilecek düğümün içindedir.
5. free(eski); düğümün belleğini sisteme iade eder.

30 → 20 → 10 yığınına dört kez pop uygulansın ve her başarılı sonuç yazdırılsın. Tablo 6.7 çağrıları özetler.

Test programı 10, 20, 30 itip dört kez pop çağırdı ve “30 20 10 false” yazdı. Çıkış sırası girişin tersidir. Pop da sabit sayıda iş yapar: bir karşılaştırma, iki atama ve bir free. Maliyeti O(1)'dir.

Pop'taki adımların sırası, push'takinden de önemlidir. free(eski) çağrısından sonra eski'nin gösterdiği bellek artık programa ait değildir. eski->deger ya da eski->bag bu andan sonra okunursa davranış tanımsızdır. Program çoğu zaman doğru değeri okur, çünkü iade edilen bellek hemen başka bir işe verilmez. Bu da hatayı daha tehlikeli yapar: testlerde görünmez, ama başka bir malloc araya girdiğinde değer bozulur. Böyle iade edilmiş bir belleği gösteren işaretçiye sarkan işaretçi (dangling pointer) denir. Sağlam kural şudur: önce değeri ve bağı kurtar, en son free çağır.

6.5.4Bellek sorumluluğu ve yığını boşaltma

Bağlı yığında her düğümü malloc ayırır ve her düğümü bir free geri vermelidir. C'de bu sorumluluk tamamen programcıdadır. Program bitmeden yığında kalan düğümler de iade edilmelidir. Bu iş için bir temizleme yordamı yazılır:

typedef struct dugum {
    int deger;
    struct dugum *bag;
} dugum;

void yigit_temizle(dugum **top) {
    while (*top != NULL) {
        dugum *eski = *top;
        *top = eski->bag;
        free(eski);
    }
}                  /* sonunda *top == NULL */

yigit_temizle, yığın boşalana kadar üst düğümü çıkarır. Döngünün her turunda üç satır çalışır: üst düğümün adresi eski'ye alınır, *top bir sonraki düğüme ilerletilir, sonra eski iade edilir. Sıra yine aynıdır: bağ kurtarılmadan düğüm bırakılmaz. Döngü bittiğinde *top NULL'dır; çağırandaki top böylece boş yığını gösterir ve sarkan bir işaretçi olarak kalmaz. n düğümlü bir yığında döngü n tur döner; maliyet Θ(n)'dir. Ek bellek yalnız eski işaretçisidir, yani O(1).

Bu kodda dikkat çeken bir nokta, eski değişkeninin bir işaretçi değişkeni olmasıdır, yeni bir düğüm değil. Öğrenci kodlarında sık görülen bir yanlış, her işaretçiye malloc ile yer ayırmaktır: dugum *eski = malloc(sizeof *eski); eski = *top;. İlk satır bir düğümlük yer ayırır; ikinci satır eski'nin üzerine üst düğümün adresini yazar. Ayrılan bloğun adresi artık hiçbir yerde yoktur. Her pop'ta bir düğüm sızar. İşaretçiye malloc ancak işaretçinin göstereceği yeni bir nesne gerektiğinde yapılır. Var olan bir düğümü göstermek için yalnız atama yeter.

Bağlı yığının sızıntısız çalıştığı sayaçlı bir sarmalayıcıyla doğrulandı. Sarmalayıcı, malloc ve free çağrılarını bir makro yardımıyla kendi fonksiyonlarına yönlendirir ve her başarılı çağrıyı sayar. Test programı 10, 20, 30'u itip dört kez pop yaptı, sonra 1'den 5'e beş öğe daha itip yigit_temizle çağırdı. Sayaç sekiz malloc ve sekiz free gösterdi; temizlemeden sonra top NULL oldu. Aynı programda sizeof(dugum) 16 çıktı. Düğümün alanları 4 baytlık int ve 8 baytlık işaretçidir; işaretçinin 8'in katı bir adreste durması için derleyici araya 4 baytlık bir dolgu (padding) koyar. Bu yüzden 64 bitlik bir sistemde bağlı yığın, her int için dizinin dört katı bellek kullanır; malloc'un her blok için tuttuğu kendi kayıtları da buna eklenir.

6.6Dizi tabanlı mı, bağlı mı?

Şu ana kadar iki gerçekleme kuruldu: sabit kapasiteli dizi ve bağlı liste. Arada üçüncü bir seçenek daha vardır: dolduğunda kendini büyüten dizi. Bu kesim önce bu üçüncü gerçeklemeyi kurar, sonra maliyetini amortize analizle gerekçelendirir ve üç gerçeklemeyi karşılaştırır.

6.6.1Büyüyen dizi

Sabit dizinin sorunu kapasitenin baştan bilinmesi gerekmesidir. Çözüm, diziyi heap bellekte tutmak ve dolduğunda realloc ile daha büyük bir bloğa taşımaktır. Dolduğunda realloc ile büyütülen diziye dinamik dizi (dynamic array) denir. Asıl soru, ne kadar büyütüleceğidir. Her dolmada kapasite iki katına çıkarılırsa push'ların ortalama maliyeti sabit kalır. Aşağıdaki gerçekleme struct sürümünün düzenini izler:

typedef struct {
    int *veri;
    int ust, kap;           /* boşken ust = -1 */
} DYigit;

bool dy_baslat(DYigit *y, int kap) {
    y->veri = malloc(kap * sizeof *y->veri);
    if (y->veri == NULL) return false;
    y->ust = -1;  y->kap = kap;
    return true;
}
bool dy_push(DYigit *y, int x) {
    if (y->ust == y->kap - 1) {          /* dolu: kapasiteyi ikiye katla */
        int *yeni = realloc(y->veri, 2 * y->kap * sizeof *yeni);
        if (yeni == NULL) return false;  /* eski blok hâlâ geçerli */
        y->veri = yeni;
        y->kap *= 2;
    }
    y->veri[++y->ust] = x;
    return true;
}
bool dy_pop(DYigit *y, int *x) {
    if (y->ust < 0) return false;
    *x = y->veri[y->ust--];
    return true;
}
void dy_yok_et(DYigit *y) {
    free(y->veri);
    y->veri = NULL;  y->ust = -1;  y->kap = 0;
}

DYigit yapısı üç alan taşır: heap bellekteki dizinin adresi veri, üst indisi ust ve o anki kapasite kap. dy_baslat istenen başlangıç kapasitesiyle diziyi ayırır. dy_pop, struct sürümündeki pop'un aynısıdır.

Fark dy_push'tadır. Yığın doluysa yordam hata döndürmez; kapasiteyi iki katına çıkarmayı dener. realloc(y->veri, yeni_boyut), eski bloğu yeni boyuta getirir. Eski bloğun hemen arkasında yer varsa blok yerinde büyüyebilir. Yoksa realloc yeni bir blok ayırır, eski içeriği oraya kopyalar, eski bloğu iade eder ve yeni bloğun adresini döndürür. Kopyalanan öğe sayısı o anki kapasitedir.

realloc'un sonucu doğrudan y->veri'ye yazılmaz; önce yeni adlı geçici bir işaretçiye alınır. Bunun nedeni hata durumudur. realloc başarısız olursa NULL döner ve eski bloğa dokunmaz. Sonuç doğrudan y->veri'ye yazılsaydı eski bloğun adresi kaybolur, içindeki bütün öğeler sızardı. Geçici işaretçi sayesinde başarısızlıkta yığın eski hâliyle geçerli kalır ve fonksiyon false döner. Başarılıysa veri ve kap güncellenir, ardından öğe her zamanki gibi yazılır.

Başlangıç kapasitesi 2 olan bir yığına 10, 20, 30, 40, 50 itildiğinde kapasite şöyle değişir: 10 ve 20 yer bulur (kap = 2). 30 itilirken yığın doludur; kapasite 4'e çıkar, 2 öğe kopyalanır. 40 yer bulur. 50 itilirken kapasite 8'e çıkar, 4 öğe kopyalanır. Bu değerler test programında yazdırılarak doğrulandı: her push'tan sonra (ust, kap) çiftleri (0, 2), (1, 2), (2, 4), (3, 4), (4, 8) oldu. Sayaçlı sarmalayıcı iki malloc ve iki free saydı.

6.6.2Amortize maliyet

Büyüyen dizide tek bir push'un maliyeti duruma göre çok değişir. Çoğu push bir hücreye yazar ve O(1)'dir. Ama kapasitenin dolduğu anda yapılan push bütün öğeleri kopyalar ve O(n)'dir. En kötü durum analizi bu yüzden “push O(n)” der. Bu doğru, ama yanıltıcıdır: pahalı push'lar çok seyrektir. Bir işlem dizisinin toplam maliyetini işlem sayısına bölerek işlem başına ortalama maliyeti bulmaya amortize analiz (amortized analysis) denir. Buradaki ortalama olasılığa dayanmaz; en kötü işlem dizisi için bile geçerlidir.

Kanıt. Büyütme, yığın dolu iken push yapıldığında olur. Kapasite 1, 2, 4, 8, … diye ilerlediği için büyütmeler kapasite 1, 2, 4, …, 2^k iken yapılır. Kapasite c iken yapılan büyütme c öğe kopyalar. Son büyütme kapasite 2^k iken olmuşsa, bu anda yığında 2^k öğe vardır ve bir öğe daha itilir; dolayısıyla 2^k < n'dir. Toplam kopya sayısı 1 + 2 + 4 + … + 2^k = 2^k+1 − 1'dir. 2^k ≤ n − 1 olduğundan bu toplam en çok 2n − 3'tür; n'nin bir sabit katıdır. Her push ayrıca bir yazma yapar. Toplam iş n + (2n − 3) < 3n ile sınırlıdır ve push başına 3 birimden azdır. ∎

Kanıttaki kopya sınırı daha sıkı da verilebilir. Kopya toplamı 2^k+1 − 1 ve son kapasite 2^k+1'dir; yani toplam kopya, son kapasiteden bir eksiktir. Son kapasite de 2n'den küçüktür. Bu sayılar bir test programıyla doğrulandı: kapasitesi 1 olan yığına 1000 push yapıldığında 10 büyütme oldu, toplam 1023 öğe kopyalandı (2n = 2000'den az) ve son kapasite 1024'e ulaştı.

Büyütme oranının iki olması şart değildir; önemli olan oranın 1'den büyük sabit bir çarpan olmasıdır. Çarpan 1,5 seçilirse kopyalar biraz artar, boşa duran kapasite azalır; amortize maliyet yine O(1) kalır. Buna karşılık kapasite her dolmada sabit bir miktar, örneğin 10 hücre artırılırsa amortize maliyet bozulur. n push boyunca yaklaşık n/10 büyütme olur ve her biri o anki bütün öğeleri kopyalar. Toplam kopya 10 + 20 + … + n ≈ n²/20'dir; push başına maliyet Θ(n)'ye çıkar.

6.6.3Karşılaştırma ve ölçüm

Tablo 6.8 üç gerçeklemeyi altı ölçüte göre karşılaştırır.

Tablodaki “önbellek” satırı açıklama ister. İşlemci belleğe her erişimde tek bir sayıyı değil, çevresindeki 64 baytlık bir bloğu önbelleğe (cache) getirir. Dizi yığınında ardışık öğeler yan yana durduğu için bir bloğa birçok öğe sığar ve sonraki erişimler önbellekten karşılanır. Bağlı yığında her düğüm ayrı bir malloc bloğudur ve bellekte nerede duracağı belli değildir. Ardışık düğümlere erişim çoğu zaman yeni bir bloğun getirilmesini gerektirir.

Asimptotik maliyetler aynıdır, ama sabit çarpanlar çok farklıdır. Bunu görmek için üç gerçeklemede 10⁷ push ve ardından 10⁷ pop yapan bir program -O2 ile derlenip üç kez çalıştırıldı. Sabit dizi 25–35 ms, büyüyen dizi (başlangıç kapasitesi 16) 30–63 ms, bağlı yığın 680–806 ms sürdü. Bu değerler makineye göre değişir; ama oran tutarlıdır: bağlı yığın, dizi yığınlarından yaklaşık yirmi kat yavaştır. Farkın büyük bölümü her push'taki malloc ve her pop'taki free çağrısından, kalanı önbellek kayıplarından gelir.

Seçim için pratik bir kural şöyledir. Yığının alabileceği en büyük boyut biliniyorsa sabit dizi en yalın ve en hızlı çözümdür. Bilinmiyorsa büyüyen dizi pratikte en hızlısıdır. Bağlı yığın, düğümlerin zaten başka yapılarda yaşadığı ya da öğelerin tek tek yaratılıp silindiği durumlar için uygundur. Örneğin her öğesi büyük bir kayıt olan ve kayıtları başka listelerle paylaşan bir programda düğümleri yığına bağlamak, onları bir diziye kopyalamaktan ucuzdur.

6.7Çağrı yığını

Bilgisayarın en çok kullanılan yığını programcının yazdığı bir yığın değildir. Her C programı, fonksiyon çağrılarını yönetmek için derleyicinin ve işletim sisteminin kurduğu bir yığın kullanır. Buna çağrı yığını (call stack) denir. Bu kesim çağrı yığınının nasıl çalıştığını, nasıl taştığını ve özyinelemeli bir fonksiyonun bu yığın yerine kendi yığınımızla nasıl yazılabileceğini anlatır.

6.7.1Çerçeve

Bir fonksiyon çağrıldığında, çağrının yaşaması için gereken bilgiler bellekte bir bloğa yazılır. Bu bloğa çerçeve (stack frame, activation record) denir. Çerçevenin ilk parçası dönüş adresidir (return address): fonksiyon bitince çağırandaki hangi komuttan devam edileceğini gösterir. Çerçeve ayrıca fonksiyonun parametrelerini, yerel değişkenlerini ve çağıranın çerçevesine geri dönmek için gereken bilgiyi tutar. Çağrı, yeni bir çerçeveyi çağrı yığınına iter. return bu çerçeveyi çeker ve denetim dönüş adresine geçer. En son çağrılan fonksiyon ilk biter; çağrı yığını bu yüzden gerçek bir yığındır.

Özyinelemeli bir fonksiyon bu düzeni açıkça gösterir:

long fakt(int n) {
    if (n <= 1) return 1;          /* taban durum */
    return n * fakt(n - 1);        /* çağrı dönünce çarpma yapılır */
}

main, fakt(5)'i çağırsın. fakt(5), sonucunu hesaplamak için fakt(4)'ün sonucunu bekler; fakt(4) fakt(3)'ü, o da fakt(2)'yi, o da fakt(1)'i çağırır. Her çağrının kendi n'si vardır ve bu değerler birbirine karışmaz, çünkü her biri ayrı bir çerçevededir. fakt(1) taban duruma ulaşır ve 1 döndürür. O anda yığında en çok çerçeve vardır: main ile birlikte altı çerçeve. Sonra çerçeveler ters sırada çekilir: fakt(2) 2·1 = 2, fakt(3) 3·2 = 6, fakt(4) 4·6 = 24, fakt(5) 5·24 = 120 döndürür. Tablo 6.9 bu süreci özetler.

Çerçevelerin bellekte gerçekten üst üste dizildiği bir deneyle görülebilir. fakt'ın her çağrısında n parametresinin adresi yazdırıldı (-O0, Windows x86-64). Her çağrıda adres bir öncekinden 96 bayt küçüktü: main'deki bir yerel değişkenden fakt(5)'in n'sine 80 bayt, fakt(1)'in n'sine 464 bayt vardı. Bu sayılar derleyiciye, eniyileme düzeyine ve işlemciye göre değişir. Değişmeyen gözlem şudur: x86 işlemcilerde çağrı yığını yüksek adreslerden düşük adreslere doğru büyür ve her çağrı sabit büyüklükte bir çerçeve ekler. fakt(n) bu yüzden Θ(n) çerçeve, yani Θ(n) yığın belleği kullanır.

6.7.2Çağrı yığını nasıl taşar

Çağrı yığınının kapasitesi sınırlıdır ve programın başında sabitlenir. Tipik değerler birkaç megabayttır: Linux'ta 8 MB, Windows'ta Microsoft derleyicisiyle 1 MB. Bu çalışmadaki zig cc derleyicisi Windows programlarına 16 MB ayırıyordu. Yığın dolunca program yığın taşması (stack overflow) hatasıyla çöker. Üç tipik neden vardır.

Sonsuz özyineleme

Taban durumu olmayan ya da taban durumuna hiç ulaşmayan bir özyineleme her çağrıda bir çerçeve iter ve hiçbirini çekmez. Örneğin fakt'taki koşul n == 1 yazılsaydı fakt(0) çağrısı −1, −2, … diye sonsuza dek inerdi. Denemede her çağrısında 64 baytlık bir yerel dizi tutan sonsuz bir özyineleme yaklaşık 104 000 çağrı derinliğinde Windows'un STATUS_STACK_OVERFLOW (0xC00000FD) hatasıyla durdu.

Büyük yerel diziler

int a[1000000]; gibi bir yerel dizi çerçevenin içindedir ve tek başına 4 MB tutar. 1 MB'lık bir yığını tek başına taşırır. Denemede 16 MB'lık yığında bu dizi sığdı, 5 milyon öğelik (20 MB) dizi ise programı aynı hatayla çökertti. Büyük veriler malloc ile heap bellekte tutulur ya da static tanımlanır.

Yerel adres döndürme

return &yerel; yazmak, taşma değildir ama aynı yığın düzeninden doğan bir hatadır. Fonksiyon dönünce çerçevesi çekilir. O bellek bölgesi bir sonraki çağrının çerçevesi için yeniden kullanılır. Döndürülen adres artık başka bir çağrının yerel değişkenlerini gösterir; bir sarkan işaretçidir.

Yığın taşması bu dersin konusu olan her özyinelemeli yordamda göz önünde tutulmalıdır. Örneğin bağlı bir listeyi özyinelemeli olarak serbest bırakan bir fonksiyon, her düğüm için bir çerçeve iter. Bir milyon düğümlü bir listede bu, bir milyon çerçeve demektir ve yığını taşırabilir.

6.7.3Özyinelemeyi döngüye çevirmek

Çağrı yığını bir yığın olduğuna göre, her özyinelemeli algoritma çağrı yığınının yaptığı işi kendi yığınımızla yaparak bir döngüye çevrilebilir. Özyinelemeli bir çağrı, “şimdilik yarım bırakılan işi” bir çerçeveye koyar. Döngülü sürümde bu yarım iş açık bir yığına itilir. Faktöriyel için yarım kalan iş, “dönüşte n ile çarp” bilgisidir:

long fakt_dongu(int n) {
    Yigit y;  int k;  long sonuc = 1;
    yigit_baslat(&y);
    while (n > 1)                  /* "çağrıları" kendi yığınına it */
        push(&y, n--);
    while (pop(&y, &k))            /* "dönüşlerde" çarp */
        sonuc *= k;
    return sonuc;
}

Birinci döngü, özyinelemeli sürümün aşağı inen çağrılarını taklit eder: n'yi 1'e inene kadar yığına iter. 5 için yığın alttan üste 5, 4, 3, 2 olur. İkinci döngü dönüşleri taklit eder: yığından çekilen her değerle sonucu çarpar. Çarpımlar 2, 3, 4, 5 sırasıyla yapılır; özyinelemeli sürümdeki dönüş sırasının aynısıdır. Sonuç 120'dir. fakt_dongu(0) ve fakt_dongu(1) 1, fakt_dongu(10) 3628800 verdi; özyinelemeli fakt ile aynıdır.

Faktöriyelde bu çeviri gereksizdir; basit bir for döngüsü yeter. Ama ağaç gezinme, derinlik öncelikli arama ya da geri izleme gibi algoritmalarda yarım kalan iş tek bir sayı değildir. Yarım kalan iş bir durumdur ve yığına bu durum itilir. Kendi yığınımızı kullanmanın iki yararı vardır. Birincisi, kendi yığınımız heap bellekte büyüyebilir; çağrı yığınının birkaç megabaytlık sınırına takılmaz. İkincisi, yığına yalnız gereken bilgi itilir; çerçevenin dönüş adresi ve kaydedilmiş yazmaçlar gibi ek yükleri yoktur.

6.8Çoklu yığın

Bir program aynı anda birden çok yığın kullanabilir. Her yığına ayrı bir dizi vermek kolaydır, ama bellek israf edilir: bir yığın dolduğunda ötekilerde boş yer olsa bile o yere erişilemez. Bu kesim birden çok yığını tek bir bellek dizisinde paylaştırmayı ele alır.

6.8.1Tek dizide iki yığın

İki yığın için çok güzel bir çözüm vardır. m hücrelik dizide birinci yığın 0. hücreden yukarı, ikinci yığın m − 1. hücreden aşağı büyür. İki yığının üstleri birbirine doğru ilerler.

Boş durumda top1 = −1 ve top2 = m'dir; ikisi de dizinin dışındaki hayali bir hücreyi gösterir. Yığın 1'e ekleme top1'i artırır, yığın 2'ye ekleme top2'yi azaltır. Dizi, iki üst yan yana geldiğinde, yani top1 + 1 == top2 olduğunda doludur. Bu düzenin yararı, hiçbir hücrenin boşa gitmemesidir. Bir yığın az, öteki çok öğe tutsa bile dizi ancak toplam m öğe olduğunda dolar. Üç ve daha fazla yığın için bu hile işlemez, çünkü bir dizinin yalnız iki ucu vardır.

6.8.2Tek bellekte n yığın

n yığın için Horowitz–Sahni'nin çözümü, m hücrelik bellek dizisini n kesime (segment) bölmektir. Her yığın kendi kesiminde büyür. İki yardımcı dizi kullanılır. top[i], i. yığının üst öğesinin indisidir. sinir[i], i. yığının kesiminin hemen altındaki hücrenin indisidir. Yığın i, bellek[sinir[i]+1]'den bellek[sinir[i+1]]'e kadar olan hücreleri kullanır. Son yığının üst sınırını da aynı biçimde yazabilmek için sinir[n] = m − 1 eklenir.

Başlangıçta bellek eşit parçalara bölünür ve bütün yığınlar boştur: i = 0, …, n − 1 için top[i] = sinir[i] = (m/n)·i − 1. Bir yığının boş olması, üstünün kendi alt sınırına eşit olmasıdır: top[i] == sinir[i]. Dolu olması ise üstünün bir sonraki yığının alt sınırına ulaşmasıdır: top[i] == sinir[i+1]. Ekleme ve çıkarma bu iki sınamayla yazılır:

/* yığın i: bellek[sinir[i]+1 .. sinir[i+1]] */
bool ekle(int i, int x) {
  if (top[i] == sinir[i + 1]) return false; /* dolu */
  bellek[++top[i]] = x;
  return true;
}
bool al(int i, int *x) {
  if (top[i] == sinir[i]) return false;     /* boş */
  *x = bellek[top[i]--];
  return true;
}

Bu kod bellek, top ve sinir dizilerinin küresel olarak tanımlandığını varsayar; ders kitabındaki gibi kısa tutulmuştur. Gerçek bir programda bu üç dizi bir struct'ta toplanır ve yordamlara adresle verilir. Yordamların yapısı tek yığınınkiyle aynıdır, yalnız sabit sınırların yerini sinir dizisi alır. ekle, yığın doluysa false döner; değilse top[i]'yi artırıp değeri yazar. al, yığın boşsa false döner; değilse üst değeri *x'e yazıp top[i]'yi azaltır. İkisi de O(1)'dir.

6.8.3Kod izleme

m = 12 ve n = 3 olsun. Her yığına dört hücre düşer. Başlangıçta top = [−1, 3, 7] ve sinir = [−1, 3, 7, 11]'dir. Yığın 0 hücre 0–3'ü, yığın 1 hücre 4–7'yi, yığın 2 hücre 8–11'i kullanır. Sırasıyla ekle(0, 5), ekle(1, 7), ekle(0, 9), ekle(2, 4), ekle(0, 2), ekle(0, 8), ekle(0, 6) ve al(1, &x) çağrılıyor. Tablo 6.10 her çağrıyı verir.

İzleme bir test programıyla doğrulandı; her çağrıdan sonraki top dizisi tablodakiyle aynı çıktı. Yedinci çağrı düzenin zayıflığını gösterir. Yığın 0 dolmuştur, çünkü üstü bir sonraki yığının sınırına (sinir[1] = 3) ulaşmıştır. Oysa bellekteki 12 hücreden yalnız altısı doludur: yığın 0'da dört, yığın 1'de bir, yığın 2'de bir öğe vardır. Kalan altı hücre boştur. Yine de ekle, “dolu” der.

6.8.4Yer açma ve değerlendirme

Horowitz–Sahni bu sorunu bir stack_full(i) yordamıyla çözer. Yordam, i. yığın dolduğunda çağrılır. Önce sağdaki yığınlar arasında boş yeri olan ilkini arar. Bulursa arada kalan yığınları birer hücre sağa kaydırır ve böylece i. yığına bir hücre açar. Sağda yer yoksa aynı aramayı soldaki yığınlarda yapar ve i. yığının kendisi dahil arada kalanları birer hücre sola kaydırır. Hiçbir yerde boş hücre yoksa bellek gerçekten doludur. Aşağıda yalnız sağa kaydıran yarı, sadeleştirilerek verilmiştir:

/* yığın i doluyken sağda boş yer arar; bulursa arada kalan
   yığınları birer hücre sağa kaydırır (Horowitz'in fikri, sadeleştirilmiş) */
bool yer_ac_sag(int i) {
    int j = i + 1, k;
    while (j < N && top[j] == sinir[j + 1])   /* boş yeri olan ilk yığın */
        j++;
    if (j == N) return false;                 /* sağda yer yok */
    for (k = top[j]; k > sinir[i + 1]; k--)   /* bellek[sinir[i+1]+1 .. top[j]] */
        bellek[k + 1] = bellek[k];            /* bir sağa kayar */
    for (k = i + 1; k <= j; k++) {            /* sınırlar ve üstler de kayar */
        sinir[k]++;
        top[k]++;
    }
    return true;
}

Fonksiyon i'nin sağındaki yığınları sırayla dener. top[j] == sinir[j+1] olan, yani kendisi de dolu olan yığınları atlar ve boş yeri olan ilk yığında durur. Hiçbiri bulunmazsa false döner. Bulunursa sinir[i+1]+1'den top[j]'ye kadar olan hücreler birer hücre sağa kopyalanır. Bu hücreler i + 1'den j'ye kadar bütün yığınların öğeleridir. Kopyalamanın sağdan başlaması gerekir; soldan başlansaydı her hücre bir sonrakinin üzerine yazar ve değerler kaybolurdu. Son olarak bu yığınların hem alt sınırları hem üstleri bir artırılır. Yığın i'nin üst sınırı sinir[i+1] de bir artmış olur; yığın i bir hücre kazanır.

İzlemedeki duruma uygulanınca: yığın 0 doludur; sağındaki yığın 1'de yer vardır (top[1] = 4, sinir[2] = 7). Yığın 1'in tek öğesi olan 7, bellek[4]'ten bellek[5]'e kayar. sinir[1] 4'e, top[1] 5'e çıkar. Bundan sonra ekle(0, 6) başarılıdır ve 6, bellek[4]'e yazılır. Test programı bu adımları doğruladı: yer açmadan sonra top = [3, 5, 8], sinir = [−1, 4, 7, 11] oldu; ekleme sonrası yığın 0 “5 9 2 8 6”, yığın 1 “7”, yığın 2 “4” içeriyordu.

Bu yaklaşımın artıları ve eksileri açıktır. Artıları: tek bir dizi ve tek bir malloc yeter, yönetim kolaydır; push ve pop yine O(1)'dir; aynı fikir n kuyruğu tek dizide tutmak için de kullanılabilir. Eksileri: bir kesim dolunca, bellekte yer olsa bile “dolu” hatası alınır; yer açmak için yığınları kaydırmak pahalıdır. Kaydırılan öğe sayısı m'ye kadar çıkabilir. Bellek neredeyse doluyken her ekleme bir kaydırma gerektirebilir ve en kötü durumda her ekleme O(m) olur. Kesim boyutlarını önceden iyi kestirmek de zordur. Yığınların büyüme hızları farklıysa eşit bölme sık sık kaydırmaya yol açar.

6.9Hangi çıkış sırası mümkün?

Yığının giriş sırasını nasıl değiştirebildiğini anlamak için klasik bir soru sorulur. 1, 2, 3, 4 sayıları bu sırayla push edilecektir. Push'ların arasına istenen sayıda pop konabilir ve sonunda yığın boşaltılır. Pop'ların çıkardığı sayıların sırası, yani çıkış sırası, hangi permütasyonlar olabilir?

Birkaç sıra kolayca elde edilir. 1 2 3 4 için her push'tan hemen sonra bir pop yapılır. 4 3 2 1 için dört push, ardından dört pop yapılır. 2 4 3 1 için şu dizi yeter: push 1, push 2, pop (2), push 3, push 4, pop (4), pop (3), pop (1). Peki 3 1 4 2 elde edilebilir mi? İlk çıkan 3 olacaksa 3 itilmeden önce 1 ve 2 de itilmiş olmalıdır; 3 çıktığı anda yığında alttan üste 1 ve 2 vardır. Sonraki çıkacak öğe ya üstteki 2 ya da henüz itilmemiş 4 olabilir. 1, 2'nin altında kaldığı için 2'den önce çıkamaz. 3 1 4 2 bu yüzden imkânsızdır.

Bu akıl yürütme genel bir kurala dönüşür. Bir x çıktığı anda, x'ten önce itilmiş ve henüz çıkmamış bütün öğeler yığındadır ve itildikleri sıranın tersiyle çıkmak zorundadır. Kural, yasak bir desen olarak da söylenebilir.

Kanıt. Önce desenin imkânsız olduğu gösterilir. p_i çıktığında, ondan küçük olan p_j ve p_k çoktan itilmiştir, çünkü sayılar artan sırada itilir. İkisi de henüz çıkmamıştır, çünkü çıkış sırasında p_i'den sonra gelirler. Demek ki ikisi de yığındadır ve p_j < p_k olduğu için p_k daha sonra itilmiş, yani p_j'nin üstündedir. Bu durumda p_j, p_k'dan önce çıkamaz; oysa sırada önce gelir. Çelişki.

Ters yön için açgözlü bir yöntem kullanılır: sıradaki hedef p ise, p itilene kadar push yapılır, sonra üst öğe çekilir. Yöntem ancak hedef o anda yığının üstünde değilse ve zaten itilmişse takılır. Bu durumda hedef p_j'nin üstünde, ondan büyük ve henüz çıkmamış bir q vardır. q, sırada p_j'den sonra bir k konumundadır. Yığındaki öğelerin hepsi o ana dek çıkmış en büyük değerden, yani daha önceki bir konumdaki bir p_i'den küçüktür. Böylece p_j < q = p_k < p_i deseni bulunur. Desen yoksa yöntem hiç takılmaz ve sıra elde edilir. ∎

3 1 4 2 sırasında 3, 1, 2 konumları bu deseni oluşturur: 3 büyük, 1 küçük, 2 orta. Bu yüzden imkânsızdır. 2 4 3 1'de böyle bir üçlü yoktur. Elde edilebilen sıraların sayısı da bilinir. n öğe için bu sayı n. Catalan sayısıdır: C_n = (2n)! / ((n + 1)! · n!). İlk değerler 1, 2, 5, 14, 42, 132'dir. n = 4 için 24 permütasyonun yalnız 14'ü elde edilebilir. n = 3 için altı permütasyondan yalnız biri, 3 1 2, imkânsızdır. Bu sayılar, bütün permütasyonları açgözlü yöntemle deneyen bir betikle n = 1, …, 6 için doğrulandı; aynı betik, desen koşuluyla açgözlü yöntemin n ≤ 7 için her permütasyonda aynı sonucu verdiğini de denetledi.

6.10Karmaşıklık özeti

Tablo 6.11 bölümdeki işlemlerin maliyetlerini üç gerçekleme için yan yana verir. Her değer, ilgili kesimde gerekçesiyle açıklanmıştır.

Tablodaki temizleme satırı bir farkı vurgular. Dizi yığınları tek bir blokta durur; sabit dizide temizlemek için ust = -1 yapmak, büyüyen dizide tek bir free yeter. Bağlı yığında ise her düğüm ayrı bir bloktur ve n düğüm için n kez free çağrılır. Bellek satırındaki “≤ 2n” sınırı, kapasite 1'den başlayıp iki katına çıkarıldığında geçerlidir; kapasite hiç küçültülmezse çok sayıda pop'tan sonra boş kapasite n'nin çok üstünde kalabilir.

6.11Sık yapılan hatalar

Yığın kodunda görülen hataların çoğu birkaç kalıba girer. Aşağıdaki liste, bölümdeki kodların her birinde karşılaşılabilecek hataları bir araya getirir.

1. Sınır denetimini atlamak. Boş yığından pop ya da dolu yığına push, diziyi sınırlarının dışında okur ya da yazar. C bunu denetlemez; komşu bellek bozulur ve hata çok sonra, ilgisiz bir yerde görünür.
2. *top-- yazmak. İfade *(top--) olarak okunur ve işaretçiyi azaltır; çağırandaki üst indisi değişmez. Doğrusu (*top)--'dir. Derleyici uyarı vermez.
3. top ile öğe sayısını karıştırmak. top son öğenin indisidir; öğe sayısı top + 1'dir. Dolu denetimi top == MAX - 1'dir, top == MAX değildir.
4. Bağlı push'ta önce *top = yeni yazmak. Eski listenin adresi kaybolur, yeni düğüm kendini gösterir.
5. Pop'ta değeri free'den sonra okumak ya da düğümü hiç bırakmamak. İlki sarkan işaretçiyle tanımsız davranış, ikincisi bellek sızıntısıdır.
6. Geçici işaretçiye gereksiz malloc yapmak. dugum *eski = malloc(…); eski = *top; her çağrıda bir düğüm sızdırır. Var olan bir düğümü göstermek için atama yeter.
7. realloc sonucunu doğrudan asıl işaretçiye yazmak. Başarısızlıkta eski bloğun adresi kaybolur.
8. bool sonuçlarını yok saymak. Başarısız bir push'un öğesi sessizce kaybolur; başarısız bir pop'tan sonra eski değer kullanılmaya devam eder.

6.12Alıştırmalar ve çözümleri

Sunumun alıştırma slaytındaki altı soru aşağıda çözümleriyle verilmiştir. Çözümlerin hepsi derlenip küçük test programlarıyla çalıştırıldı.

6.12.1Hata döndüren yigit_ekle

Soru. Küresel dizi yığınında yigit_ekle'yi exit yerine bool döndürecek biçimde yeniden yazmak.

bool yigit_ekle(int *top, element item) {
    if (*top >= MAX_STACK_SIZE - 1)
        return false;          /* taşma: karar çağıranın */
    yigit[++*top] = item;
    return true;
}
bool yigit_al(int *top, element *item) {
    if (*top < 0)
        return false;          /* alt taşma */
    *item = yigit[(*top)--];
    return true;
}

Taşma durumunda fonksiyon false döner ve yığına dokunmaz. Yer varsa öğeyi yazıp true döner. yigit_al'ın da aynı biçimde yazılması gerekir; öğeyi dönüş değeri olarak vermek artık mümkün olmadığı için bir çıktı parametresiyle, element *item ile verir. Kapasite 3 iken 10, 20, 30, 40 eklemeye çalışan test programı “1 1 1 0” yazdı: dördüncü ekleme reddedildi. Ardından yığını boşaltan döngü 30, 20, 10 verdi ve top −1'e döndü. Program hiçbir noktada exit ile bitmedi.

6.12.2Tek dizide iki yığın

Soru. Tek dizide iki yığın için ekle(k, x) ve al(k) yordamlarını yazmak (k = 1 ya da 2).

#define M 10
int dizi[M];
int top1 = -1, top2 = M;     /* ikisi de boş */

bool ekle(int k, int x) {
    if (top1 + 1 == top2) return false;   /* ortada buluştular: dolu */
    if (k == 1) dizi[++top1] = x;         /* yığın 1 yukarı büyür */
    else        dizi[--top2] = x;         /* yığın 2 aşağı büyür */
    return true;
}
bool al(int k, int *x) {
    if (k == 1) {
        if (top1 == -1) return false;     /* yığın 1 boş */
        *x = dizi[top1--];
    } else {
        if (top2 == M) return false;      /* yığın 2 boş */
        *x = dizi[top2++];
    }
    return true;
}

Boş durumda top1 = −1, top2 = M'dir. Dolu denetimi iki yığın için ortaktır: top1 + 1 == top2. Yığın 1'e ekleme dizi[++top1], yığın 2'ye ekleme dizi[--top2] ile yapılır; yığın 2 aşağı büyüdüğü için üstü azalır. Çıkarmada boş denetimleri ayrıdır: yığın 1 için top1 == -1, yığın 2 için top2 == M. Yığın 2'den çıkarma dizi[top2++] ile yapılır.

M = 10 iken yığın 1'e yedi, yığın 2'ye beş ekleme denendi. Yığın 1'in yedisi de girdi; yığın 2'nin ilk üçü girdi, sonraki ikisi reddedildi, çünkü toplam on hücre dolmuştu (top1 = 6, top2 = 7). Bir yığının çok, ötekinin az öğe tutması hiçbir hücreyi boşa harcamadı. Bütün işlemler O(1)'dir.

6.12.3Boyutunu bilen bağlı yığın

Soru. Bağlı yığını, top ile birlikte bir boyut alanı da tutan bir struct içine taşımak.

typedef struct {
    dugum *top;
    int boyut;
} BYigit;

void by_baslat(BYigit *y) { y->top = NULL;  y->boyut = 0; }

bool by_push(BYigit *y, int x) {
    if (!push(&y->top, x)) return false;  /* bağlı push yeniden kullanılır */
    ++y->boyut;
    return true;
}
bool by_pop(BYigit *y, int *x) {
    if (!pop(&y->top, x)) return false;
    --y->boyut;
    return true;
}
void by_temizle(BYigit *y) {
    yigit_temizle(&y->top);
    y->boyut = 0;
}

BYigit, üst işaretçisiyle öğe sayısını birlikte tutar. Yordamlar bağlı yığının push, pop ve yigit_temizle yordamlarını yeniden kullanır; onlara &y->top, yani yapının içindeki işaretçi alanının adresini verir. boyut yalnız başarılı işlemlerden sonra değişir: başarısız bir push (bellek yok) ya da başarısız bir pop (yığın boş) sayacı bozmaz. Böylece öğe sayısı, listeyi saymaya gerek kalmadan O(1)'de bilinir. Altı push ve bir pop sonrası boyut 5 oldu; temizlemeden sonra 0 oldu ve sayaçlı sarmalayıcı altı malloc'a karşı altı free saydı.

6.12.4Yığınla dizge ters çevirme

Soru. Bir dizgeyi yığın kullanarak ters çeviren void ters(char *s) yordamını yazmak.

Çözüm. Bu yordam, Tablo 6.5'te izlenen ters_cevir'in aynısıdır: karakterler sırayla push edilir, sonra pop edilerek aynı diziye geri yazılır. Süre Θ(n), ek bellek Θ(n)'dir. Sağlam bir sürüm, dizgenin uzunluğunu önce strlen ile bulup yığını bu kapasiteyle (örneğin yigit_olustur(n) ile) kurar; böylece KAP varsayımına gerek kalmaz.

6.12.5En alttaki öğe

Soru. Yalnız push ve pop kullanarak bir yığının en alttaki öğesini döndüren yordamı yazmak; yardımcı bir yığın kullanılabilir.

/* y boş değilse en alttaki öğeyi *x'e yazar; y'yi eski hâline getirir */
bool en_alt(Yigit *y, int *x) {
    Yigit yard;  int v;
    if (yigit_bos(y)) return false;
    yigit_baslat(&yard);
    while (pop(y, &v))           /* hepsini yardımcı yığına aktar */
        push(&yard, v);
    *x = v;                      /* son çıkan, en alttakiydi */
    while (pop(&yard, &v))       /* geri aktar: sıra korunur */
        push(y, v);
    return true;
}

Yordam, yığındaki bütün öğeleri yardımcı yığına aktarır. Aktarma sırasında en son çekilen öğe, asıl yığının en alttaki öğesidir; v değişkeni döngü bittiğinde onu tutar. Sonra öğeler yardımcı yığından asıl yığına geri aktarılır. İki aktarma da sırayı ters çevirdiği için asıl yığın ilk hâline döner. Yığın baştan boşsa v hiç atanmayacağı için yordam en başta false döner. Alttan üste 4, 7, 1, 9 tutan yığında yordam 4'ü verdi ve yığın üstten okunduğunda yine 9, 1, 7, 4 çıktı. n öğeli yığında 2n push ve 2n + 2 pop yapılır; süre Θ(n), ek bellek Θ(n)'dir.

6.12.6fakt(5) çağrısında çerçeve sayısı

Soru. fakt(5) çağrısında yığında en çok kaç çerçeve olur? main dahil çizmek.

Çözüm. Taban durum n <= 1 olduğundan çağrılar fakt(5), fakt(4), fakt(3), fakt(2), fakt(1)'dir. fakt(1) çalışırken bu beş çerçeve ile main'in çerçevesi birlikte yığındadır: en çok 6 çerçeve. Çizim, Tablo 6.9'un “fakt(1) çağrılır” satırıdır: alttan üste main, fakt(5), fakt(4), fakt(3), fakt(2), fakt(1). Taban durum n == 0 olarak yazılsaydı fakt(0) da çağrılır ve sayı 7 olurdu.

6.13Özet

• Yığın, ekleme ve silmenin yalnız üst uçtan yapıldığı sıralı bir listedir. Son giren ilk çıkar (LIFO). Ekleme push, çıkarma pop, çıkarmadan okuma peek adını alır.
• Dolu yığına ekleme taşma, boş yığından çıkarma alt taşmadır. Yığın ADT'si işlemleri ve bu hata durumlarını gerçeklemeden bağımsız tanımlar.
• Dizi yığınında top üst öğenin indisidir: top = −1 boş, top = MAX − 1 dolu; öğe sayısı top + 1'dir. Push yigit[++*top] = item, pop return yigit[(*top)--] ile yazılır. *top-- işaretçiyi azaltır ve hatalıdır.
• exit ile biten yordamlar yerine bool döndüren yordamlar kararı çağırana bırakır. Dizi ve üst indisi bir struct'ta tutulur; küresel değişken kullanılmaz. Başlık dosyasındaki opak tip, gerçeklemeyi kullanan koddan gizler.
• Bağlı yığında top liste başıdır; push ve pop O(1)'dir. Push'ta önce bağlanır, sonra üst değişir; pop'ta önce değer ve bağ kurtarılır, en son free çağrılır. Her malloc'un bir free'si olmalıdır; yığın yigit_temizle ile Θ(n)'de boşaltılır.
• Büyüyen dizi dolduğunda kapasitesini realloc ile iki katına çıkarır. Tek bir push O(n) olabilir, ama n push'ta toplam kopya 2n'den azdır; push'un amortize maliyeti O(1)'dir. Pratikte dizi yığınları, her push'ta malloc yapan bağlı yığından çok daha hızlıdır.
• Çağrı yığını, her çağrı için dönüş adresi, parametreler ve yerellerden oluşan bir çerçeve iter. Sonsuz özyineleme ve büyük yerel diziler onu taşırır; yerel bir değişkenin adresini döndürmek sarkan işaretçi doğurur. Her özyinelemeli algoritma kendi yığınını tutan bir döngüye çevrilebilir.
• Çoklu yığında tek bir bellek dizisi top[i] ve sinir[i] ile paylaşılır. İki yığın uçlardan büyüyerek hiç hücre harcamaz. n yığında bir kesim dolunca yığınlar kaydırılarak yer açılır; bu O(m) sürebilir.
• 1, …, n sırasıyla itilince elde edilebilen çıkış sıraları, “büyük, küçük, orta” deseni içermeyen sıralardır; sayıları Catalan sayısıdır (n = 4 için 14).

6.14Kavram listesi

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

• yığın stack
• son giren ilk çıkar LIFO (last in, first out)
• üst top
• push (üste ekleme) push
• pop (üstten çıkarma) pop
• taşma overflow
• alt taşma underflow
• soyut veri tipi abstract data type (ADT)
• gerçekleme implementation
• arayüz interface
• başlık dosyası header file
• çoklu ekleme koruması include guard
• opak tip opaque type
• eksik tip incomplete type
• küresel değişken global variable
• değerle çağrı call by value
• işleç önceliği operator precedence
• birleşme yönü associativity
• const niteleyicisi const qualifier
• bağlı liste linked list
• düğüm node
• malloc malloc
• free free
• realloc realloc
• bellek sızıntısı memory leak
• sarkan işaretçi dangling pointer
• dinamik dizi dynamic array
• kapasite capacity
• amortize analiz amortized analysis
• önbellek cache
• çağrı yığını call stack
• çerçeve stack frame (activation record)
• dönüş adresi return address
• yığın taşması stack overflow
• özyineleme recursion
• taban durum base case
• parantez denetimi balanced parentheses
• ifade değerlendirme expression evaluation
• sonek postfix
• geri izleme backtracking
• geri al undo
• derinlik öncelikli arama depth-first search (DFS)

6.15Kendini Dene

1. KAP = 3 olan struct yığınına sırasıyla push 4, push 7, pop, push 1, push 6, push 2 uygulanıyor; sonra yığın while (pop(&y, &x)) döngüsüyle boşaltılıyor. Hangi push false döner ve döngü hangi değerleri çıkarır?

   Cevap

   4 ve 7 girer; pop 7'yi çıkarır, yığın [4] olur. 1 ve 6 girer; yığın [4, 1, 6] ile doludur (ust = 2). Bu yüzden push 2 false döner. Döngü 6, 1, 4 çıkarır ve dördüncü pop'ta durur.

2. yigit_al'da return yigit[(*top)--]; yerine return yigit[*top--]; yazılmıştır. Yığın boşalana kadar yigit_al çağıran bir döngü ne yapar?

   Cevap

   *top--, *(top--) olarak okunur: azalan şey fonksiyonun yerel işaretçisidir, çağırandaki top değişmez. Her çağrı aynı üst öğeyi döndürür ve yığın hiç boşalmaz; döngü sonsuza dek sürer. Derleyici bu hatayı uyarıyla bildirmez.

3. 1, 2, 3, 4, 5 sırasıyla itiliyor. 3 5 4 2 1 ve 5 3 4 1 2 çıkış sıralarından hangisi elde edilebilir?

   Cevap

   3 5 4 2 1 elde edilebilir: push 1, 2, 3, pop (3), push 4, 5, pop (5), pop (4), pop (2), pop (1). 5 3 4 1 2 elde edilemez: 5 çıkınca yığın [1, 2, 3, 4] olur ve 3, 4'ün altında kalır. Desen olarak 5, 3, 4 üçlüsü “büyük, küçük, orta”dır.

4. Boş bir bağlı yığına push 10, push 20, push 30, pop, push 40 uygulanıyor. Yığın baştan sona nasıl görünür? O ana kadar kaç malloc ve kaç free yapılmıştır? yigit_temizle'den sonra toplam free sayısı kaç olur?

   Cevap

   Yığın 40 → 20 → 10 → NULL'dır. Dört push dört malloc, bir pop bir free yapmıştır. yigit_temizle kalan üç düğümü iade eder; toplam free 4 olur ve malloc sayısına eşitlenir.

5. Kapasitesi 1 olan boş bir büyüyen dizi yığınına 9 push yapılıyor; her dolmada kapasite iki katına çıkıyor. Kaç büyütme olur, toplam kaç öğe kopyalanır ve son kapasite kaçtır?

   Cevap

   Büyütmeler 2., 3., 5. ve 9. push'ta, kapasite 1, 2, 4 ve 8 iken olur: 4 büyütme. Kopyalanan öğe sayısı 1 + 2 + 4 + 8 = 15'tir (2n = 18'den az). Son kapasite 16'dır.

6. Bağlı pop'ta free(eski); satırı *x = eski->deger; satırından önceye alınıyor. Program testlerde çoğu zaman doğru çalışıyor. Neden yine de hatalıdır?

   Cevap

   free'den sonra eski sarkan bir işaretçidir ve eski->deger'i okumak tanımsız davranıştır. İade edilen bellek hemen başka bir işe verilmediği için eski değer çoğu zaman yerinde durur; bu yüzden testler geçer. Araya başka bir malloc girdiğinde ya da bellek ayırıcı bloğa kendi kayıtlarını yazdığında değer bozulur.

7. m = 12, n = 3 olan çoklu yığın başlangıç durumundayken ekle(1, ·) arka arkaya kaç kez başarılı olur? Bu sırada al(0, &x) ne döndürür?

   Cevap

   Yığın 1 hücre 4–7'yi kullanır; top[1] 3'ten 7'ye çıkana kadar dört ekleme başarılıdır, beşincisi top[1] == sinir[2] (7 == 7) yüzünden reddedilir. Yığın 0 boştur (top[0] == sinir[0] = −1); al(0, &x) false döndürür.

8. Tek dizide iki yığın (M = 10) boşken yığın 1'e 4, yığın 2'ye 6 öğe ekleniyor. Bir sonraki ekle(1, x) çağrısı ne döndürür? Neden?

   Cevap

   top1 = 3, top2 = 4 olur. top1 + 1 == top2 doğru olduğu için dizi doludur ve çağrı false döndürür. On hücrenin hepsi doludur.

9. Kapasite her dolmada iki katına çıkarılmak yerine 10 hücre artırılsaydı n push'un toplam maliyeti ne olurdu?

   Cevap

   Yaklaşık n/10 büyütme olur ve her biri o anki öğelerin hepsini kopyalar: 10 + 20 + … ≈ n²/20. Toplam maliyet Θ(n²), push başına amortize maliyet Θ(n) olur. Amortize O(1) için kapasitenin sabit bir çarpanla büyümesi gerekir.

6.16İleri okuma

• E. Horowitz, S. Sahni ve S. Anderson-Freed, Fundamentals of Data Structures in C (2. baskı), Bölüm 3.1–3.2, 3.7 ve 4.3: bu notun izlediği dizi yığını, dinamik diziyle yığın, çoklu yığın ve bağlı yığın kodlarının kaynağıdır.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (3. baskı), Kesim 10.1 ve Bölüm 17: yığını sözde kodla kısaca tanımlar; dinamik tabloların amortize analizini toplama, muhasebe ve potansiyel yöntemleriyle ayrıntılı verir.
• R. Sedgewick, Algorithms in C, Parts 1–4, Bölüm 4: yığını bir soyut veri tipi örneği olarak C'de, arayüz ve gerçekleme ayrımıyla ele alır.
• D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Kesim 2.2.1–2.2.2: yığınların ardışık bellekte gerçeklenmesini, çoklu yığınların kaydırmalı yönetimini ve yığınla elde edilebilen permütasyonları alıştırmalarıyla inceler.

6.17Kaynaklar

1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. baskı, Bölüm 3.1–3.2, 3.7 ve 4.3.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3. baskı, MIT Press, Bölüm 10.1 (yığınlar) ve 17 (amortize analiz).
3. R. Sedgewick, Algorithms in C, Parts 1–4, 3. baskı, Addison-Wesley, Bölüm 4.
4. D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3. baskı, Addison-Wesley, 1997, Kesim 2.2.1–2.2.2.

İlgili sayfalar: Bölüm 6 sunumu · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.