Stack (Yığın)

Tek taraflı giriş ve çıkışlara açık olan. İlk giren son çıkar LIFO (Last in First Out) mantığı ile çalışan bir ADT örneğidir.
Temelde iki veya üç fonksiyonu bulunur bunlar:
Push -> Stack içerisine bir bilgi koymaya (Stack’in en tepesine koyar)
Pop -> Stack içerisinden bir bilgi almaya (Stack’in en tepesinden alır)
Top -> Stack’in en tepesindeki bilgiyi alır ancak stackten çıkartmaz sadece okur
Stack Yığın
Bu fonksiyonlar sayesinde bir stack kullanılabilir hale gelmiş olur. Aynı fonksiyonlar ile PDA (push down Automata) ‘da tasarlanabilir.

Temel olarak stack, bir array veya Linked List üzerine inşa edilebilirler.
Örnek olarak bir dizi üzerine inşa edilen stack için bir değişken, dizide o anda kaç değer olduğunu tutacak ve her pop işleminden sonra bu değer azaltılırken, her push işleminden sonra arttırılacaktır.

Benzer uygulama linked list üzerinde yapılırsa, pop işlemiyle sondan bir düğüm silinecek veya push işlemi ile sona bir düğüm eklenecektir.

aşağıda basit bir bağlı liste üzerinde stack kullanılan kod örneği verilmiştir:

Yukarıdaki kodlar dev-cpp ile test edilmiştir.

Bağlı liste üzerinden yığın kodlamasının açıklaması (Cansu Hanım’ın sorusu üzerine ekliyorum)

Yukarıdaki bağlı liste kodunu anlamaya öncelikle kullandığımı veri yapısını oluşturan bir düğümü anlayarak başlayalım. Düğüm yapısı için kullanılan kodu ele alırsak:

Yukarıdaki bu kodda bulunan lnode isimli yapı (Struct) iki üyeye sahiptir. Buradaki data isimli int değişkeni, düğüm içindeki verileri tutmak için kullanılmakta ve yine kendi tipinden (lnode) bir gösterici (pointer) ile next isimli bir değişken tanımlanmaktadır. Bu ikinci gösterici değişkenin amacı, kendi tipinden düğümleri göstermek ve bu sayede bağlı listeyi inşa etmektir.

Kodun 8. Satırında ise global bir düğüm değişkeni olan iter tanımlanmış ve NULL olarak içeriği atanmıştır. Bu değişken bağlı listenin ilk elemanını tutmak için kodun geri kalan kısmında kullanılacaktır.

Veri yapımızı tanıdıktan sonra, bağlı liste üzerindeki yığın (stack) fonksiyonlarını anlamaya çalışalım. Bu kodda kullanılan 3 fonksiyon şunlardır:

void push(int) -> bu fonksiyon, yığına veri eklemek için kullanılır
int pop() -> bu fonksiyon, yığından veri almak için kullanılır
void printStack() -> bu fonksiyon ise yığının içeriğini ekrana basmak için kullanılır.

Bu fonksiyonların çalışmalarını anlamaya push fonksiyonu ile başalayalım.

Yukarıdaki kodun, 11. satırında buluna if kontrolü ile, iter göstericisinin ilk değeri kontrol edilmiştir. Buradaki amaç, bağlı listenin ve dolayısıyla yığının içinin boş olup olmadığını anlamaktır. Şayet yığın boşsa (ve dolayısıyla iter’in değeri NULL ise) o zaman hafızada (ram) yeni bir düğüm tanımlanmış ve iter değişkeni bu düğümü gösterecek şekilde atanmıştır (kodun 13. satırı). Ayrıca bu yeni düğümün gösterdiği bağlantı NULL olarak atanmıştır. Bu sayede veri yapımızın son göstericisini NULL olarak ayarlanmış olunur.

Kodun 17. satırında push fonksiyonuna parametre veren ve yığına eklenmek istenen data değişkeni, yeni oluşturduğumuz bu düğümün içerisine veri olarak kaydedilmiş ve ardından yeni bir düğüm oluşturularak bağlı listenin başına eklenmiştir.

Bu fonksiyonun çalışmasını aşağıdaki şekilde hayal etmemiz mümkündür:

Yukarıdaki temsili resimlerde gösterilen 4. durum için, kodun 18. satırında yeni bir düğüm göstericisi tanımlanmış ve bu düğüm göstericisi, bağlı listenin ilk elemanını, kendi next göstericisi ile kodun 19. satırında göstermiştir. Bu sayede bağlı listenin başına yeni bir düğüm eklenmiş ve daha sonraki ekleme işlemleri için bu düğüm boş olarak tutulmuştur. Zaten kodun 11. satırında bağlı listenin boş olup olmadığının kontrol edilmesi ve şayet boş ise yeni bir düğüm eklenmesinin sebebi de budur.

Push fonksiyonu yukarıdaki şekilde, bağlı listeye yeni veri geldikçe ekleme işlemi yapar ve liste içerisine veri eklenerek temsili olarak sola doğru büyür. Listenin son elemanı her zaman için NULL değerindedir ve listeye yeni eklenen değerler soldan eklenir.

Kodun 44. satırına kadar olan main fonksiyonu içerisinde bulunan push fonksiyonları çalıştırıldığında bağlı listenin hali aşağıdaki şekli alır:

Push fonksiyonunun çalışmasına baktıktan sonra sıradaki fonksiyonumuz olan pop fonksiyonunu inceleyelim:

pop fonksiyonu, iter ile gösterilmekte olan düğümden (node) bir sonraki düğümün verisini döndürmekte ve iter göstericisini sağa doğru ilerletmektedir.

kodun 28. satırındaki free fonksiyonunun amacı, bu ilk başta tutulan düğümün hafızadan (ram) kaldırılması ve gereksiz yere yer kaplamamasıdır.

Son olarak yığının (stack) içeriğini ekrana basan fonksiyonumuz olan printStack fonksiyonunu incelersek:

bu kodda, temp isminde geçici bir gösterici, iter’in gösterdiği ilk elemandan başlayarak bağlı listenin sonuna kadar olan bütün elemanları sırasıyla ekrana basmaktadır.

« Array (Dizi) | Pointer (Gösterici) ve Diziler (Arrays) »

Yorumlar

Toplam 3 yorum var.

cansu | 06 Jan 2010, 13:09
programı tam olarak anlayamadım
mesela push 10 dedik ama burdaki ekran çıktısı atıyorum 198556-10
oluyo
push 20 de ise 1985-20-10 şeklinde bu neden kaynaklanıyo yardımcı olabilirmisiniz
Şadi Evren ŞEKER | 06 Jan 2010, 14:45
program, başta bulunan ve iter tarafından tutulan boş düğümü (node) de basıyor. Şayet bu tip baştaki anlamsız sayıları görmek istemiyorsanız, kodun 33. satırındaki
lnode *temp = iter;
kodunu aşağıdaki şekilde değiştiriniz:
lnode *temp = iter->next;
Bu defa yığının ilk elemanından başlanarak basılır ve aslında daha başta olan ve içerisinde veri olmayan boş düğüm basılmaz.

Yukarıdaki yazının içerisine kodun nasıl çalıştığını açıklayan bir kısım eklemeye çalışayım belki yardımcı olur.

başarılar
cansu | 09 Jan 2010, 22:39
çok güzel bir açıklama.teşekkür ederim zaman ayırıp anlattığınız için

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Stack (Yığın)' isimli yazı 04 May 2007 tarihinde, saat: 12:22 'de �adi Evren �EKER tarafından gönderilmiş, toplam 1591 defa okunmuştur.

Benzer yazıları Bilgisayar Kavramları, C/C++, JAVA, Programlama Dilleri, veri yapıları kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar