...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
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:
- bağlı liste (linked list) ile yığın (stack) örnek kodu (C Dilinde)
- bağlı liste (linked list) ile yığın (stack) örnek kodu (C++ dilinde)
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.
1,472 views
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
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
çok güzel bir açıklama.teşekkür ederim zaman ayırıp anlattığınız için
ben bu stack ve listelemeyi kullanarak bir dosyadan okunan 2 sayıyı carpmayı nasıl yapabiliriz. yada fgetchar ı kullanarak . yani ınput dosyasında olan iki sayıyı 2 ayrı listeye atıp bu sayıları çarpacak ve sonucu da br lsitede tutacak . yardımcı olursanız sevınırm
Sorunuzu doğru anladıysam, çok büyük iki sayı, dosyalarda bulunuyor ve siz de bu dosyalardan her seferinde bir karakter okuyorsunuz. Dosyadan, sayının tamamı okunamayacak kadar büyük sayı olduğu için bu yolla okuyup sayıları nasıl çarpacağımızı soruyorsunuz.
Bakın dosyalardan birisindeki örnek sayı aşağıdaki gibi olsun:
1231432142121312312
diğerinde de aşağıdaki sayılar olsun
3432423423412312714
Şimdi bu iki sayıyı , C dilinde bir değişkende tutamayacağımıza göre, bir yol bulup bunları çarpmalıyız. İlk okulda öğrendiğimiz üzere çarpma işlemine son haneden başlanır ancak ne yazık ki son hane, dosyanın sonunda bulunuyor ve dosyayı okumaya başladığımızda elimize ilk hane geliyor.
Olsun, bu durumu tersine çevirmek mümkün. Veri yapılarından yığın (stack) tam da bunun için tasarlanmış. Başlıyoruz dosyadan okuduğumuz sayıları yığına (stack) koymaya.
Neticede stackin en üstünde, çarpılacak olan sayıların son haneleri bulunuyor.
Örneğin ilk yığının en üstünde, son sayı olan 2, ikinci yığında ise son sayı olan 4 bulunuyor.
Bu iki sayıyı çarpıp elde var bilgisi ile sonraki sayılara geçiyoruz ve böylece bütün sayılar çarpılana kadar devam ediyoruz.
Örneğimizden devam edecek olursak, 2×4 = 8 (elde var 0). 8′i bir kenara yazıp sonraki sayılara geçiyoruz (stackten pop ediyoruz)
1×1 = 1 (elde var 0 )
3×7 = 1 (elde var 2 )
2×2 = 4 + 2 = 6 (elde var değeri buraya eklendi)
Görüldüğü üzere elde var değeri için ilave bir değişken tutulması gerekiyor. Ayrıca yukarıdaki sonuçlar da bir listede durabilir.
Şimdiye kadar olan sayılar için temsili liste:
Head -> 6 -> 1 -> 1 -> 8 -> NULL
Sürekli başa ekleme yapılan (insert front) yukarıdaki şekilde bir liste, sonucu tutmak için uygundur. Veya bu veriyi işlemeyecekseniz doğrudan ekrana basmak gibi yollar da bulunabilir.
Bilemiyorum açıklayıcı oldu mu ama anlaşılmayan birşey olursa daha detaylı anlatabilirim.
başarılar
yardımcı oldunuz teşekkürler.bu stack yerine linked list e atıp karakterleri snra carpma işlemi yapan örnek ufak bir kod var mı peki elinizde desem cok mu olmus olurm :d
Aslında stack ve linked list farklı yapılar değiller. Yani olmaları gerekmiyor. Linked list, stack veya queue olarak kullanılabilir. Yukarıdaki anlattığım algoritmayı linked liste uyarlayabilirsiniz.
Hazır kod yok ne yazık ki. Ancak bağlı liste kodlarına (linked list) bir göz atmanızı tavsiye ederim. Aşağıda bağlantıyı veriyorum :
http://www.bilgisayarkavramlari.com/2007/05/03/linked-list-linkli-liste-veya-bagli-liste/
Başarılar
çok olduğumun farkındayım ama lined listlerle yaparken karaker karakter okumak için fgetchar kullanmak lazım diye biliyorum . bu fgetchar ın kullanımını anlatablir misinziz rica etsem ?
merhabalar
5+4*7+8 bu stringi kaakter karakter okuyup rakamları bir classa operatörleri ayrıbir classa yerleştiren daha sonra operatör sınıfından ilk operatörü alıp rakam sınıfından iki rakam alan (başta + operatörü var diğer class da da 7,8 alır toplar sonuc 15 dahasonra 15 i tekrar sayı sınıfına atar sonra operatör sınıfından * yı alır diger class dan 15 ve 4 alır bu operatör sınıfında hiç elemn kalmayana kadar devam eder sonuc 65 olnca sonucu geri döndürür)bunu stack ile nasıl yapabiliriz … yardımcı olursanız sevinirim
bu meşhur bir ödev sorusudur. yanlız soru ile ilgili hatalarınız var. Algoritma tasarımınızda işlem önceliğini göz ardı etmişsiniz. Örneğin bahsettiğiniz şekilde işlem yapılınca sonuç 65 çıkıyor.
Oysaki ilk yapılması gereken işlem 4*7 ve ardından toplama işlemleri. Yani sonuç 65 değil, 28 + 5 + 8 = 41 olmalı.
Sorunun çözümü için ön işlem hesaplaması (prefix calculation, veya literatürde polonya yazımı hesaplaması (polish notation calculator) olarak da geçer) anlamanızda yarar var. Bu gösterimde sayılar prefix olarak aşağıdaki şekilde yazılıp hesaplanır:
* + 2 3 4 = 10 (önce * 2 3 sonra + 4 işlemi yapılır)
Benzer gösterim de son işlem hesaplaması (postfix calculator veya ters polonya yazımı hesap makinesi (reverse polish notation calculator) ) şeklinde geçer ve işlemler aşağıdaki şekilde yazılır:
2 3 4 + * = 11 (önce 2 * 4 sonra + 3 işlemi yapılır)
Gelelim sizin probleminize,
infix gösterimi ile yazılan (yani işlemlerin (operators), sayıların arasında bulunması durumu) denklemler için aşağıdaki gibi stack (yığın) yapısı izlemeniz gerekiyor:
Sizin verdiğiniz örnek üzerinden gidelim:
5 + 4 * 7 + 8
Öncelikle iki ayrı yığın (stack) tutuyoruz. Birisi sayıları (S1 olarak göstereceğim), diğeri ise işlemleri (S2 olarak göstereceğim ) barındırıyor.
S1 –> 5 4
S2 –> +
İşlemin ilk 3 sembolüne baktığımızda yukarıdaki gibi bir durum ortaya çıkıyor. Yani basitçe 5+4 kısmına baktık. Devam edelim:
S1 –> 5 4 7
S2 –> + *
Bu aşamada, * ve + işlemleri üst üste geldi. Şayet üst üste gelen işlemlerden öncelikli olan yukarıda ise yığına (stack) yerleştiriyoruz. Yani şu anda * işlemi + işleminden öncelikli olduğu için işlemi yapmadık ama yığına yerleştirdik.
Bir sonraki adımda, sıradaki işlem + olarak gelecek ( denklemin sonunda bulunan + 8 kısmı). Bu durumda + işlemi *’dan düşük öncelikli olduğu için yığına konulamaz. Bunun yerine yığındaki işlem yapılır.
S2 yığınında en üstte bulunan işlem (pop sonucu gelecek olan terim) * işlemidir. Bunu pop ediyoruz. Ayrıca S1 yığınından da iki değeri pop ediyoruz: 4 ve 7
İşlemi yapıyoruz :
4 * 7 = 28
çıkan sonucu S1′e yerleştiriyoruz:
S1 –> 5 28
S2 –> +
son durumda gelen yeni değere bakalım : + 8
Yine yerleştirme yapmıyoruz çünkü yeni işlem + olarak geldi. İşlem yığını olan S2′de ise aynı önceliğe sahip + işlemi bulunuyor. Bu durumda yığında bulunan işlemi yapabiliriz:
S1 –> 33
S2 –> boş
Şimdi gelen yeni terimleri yerleştirelim:
S1 –> 33 8
S2 –> +
Son olarak denklem bittiği için stackteki işlemleri yapıyoruz:
33 + 8 = 41 olarak sonuç bulunuyor.
başarılar
hocam öncelikle teşekkür ederim verdiğiniz bilgiler için.benim sorunum aslında algoritmada değil
kodda ben sayıları bir classa operatorleri diğer classa atmayı beceremedim c++ da. yardımcı olursanız gerçekten cok makbule geçer çünkü gerçekten bayadır uğraşıyorum
class tasarımınızda bir hata olması çok yüksek ihtimal. sınıf tasarımınızı ve metot prototiplerinizi yollarsanız sizin için inceleyerek hatayı bulabilirim. Örneğin class diagram ve fonksiyonlarınızın parametrelerini yollayabilirsiniz.
başarılar
Merhabalar,stack yapısını kullanarak labirent yapmaya çalışıorum,bağlı liste ile oluşturlmuş bir stack yapsıı ne demek o şekilde yazmam gerekmiş?yiğina giriş noktasından itibaren izlenen yol eklenecek,giriş noktası sol üst köşe olcakmış bu kodu nasıl yazarım ben şöyle düşündüm
int maz[0][0]=Yigin.indis dizinin içine ne yazmam gerk ki 0 0 dedim ama sol üst köşede bir yer olcak belki bu nokta bir duvar,sırayla aratmam mı gerk acaba,yardımcı olursanz çok sevinirim.
Konu ile ilgili örnek bir kodu yazıp, aşağıdaki adreste yayınlamıştım. Okuyabilirsiniz.
http://www.bilgisayarkavramlari.com/2011/11/04/labirentte-yol-bulma-kodu/
Benim anlamadigim nokta stack veri yapisini kendimiz mi tasarliyoruz yoksa programlama dillerinin icinde geliyor mu?(push pop gibi fonksiyonlar yani)
Kendimiz her zaman için tasarlayabiliriz. Örneğin yukarıdaki yazıda, C dili için tasarım verilmiştir. Ayrıca bazı dillerde stack yapısı hazır da sunulmaktadır. Örneğin JAVA, C# gibi dillerde hazır bulunur. Ancak standart C dilinde hazır bir stack yapısı bulunmaz. Kullanılmak istendiğinde kodlanmalıdır.
java dilinde hazır stack yapısı için java.util.stack kütüphanesi kullanılabilir. Bu yapının kullanıldığı bir uygulamaya aşağıdaki bağlantıdan ulaşabilirsiniz:
http://www.bilgisayarkavramlari.com/2011/11/04/labirentte-yol-bulma-kodu/
s.a hocam bir bağlı listeye, bir yığıtı nasıl aktarabiliriz?
yığıt ile stack mi kastediliyor acaba? yani yığıt ile kastedilen heap ise farklı bir uygulama gerekir ancak stack ise, bu yazıda bulunan örnek kodların işinizi görmesi gerekir. Basitçe bir yığın (stack) dizide veya bağlı listede tutulabilir (linked list) ayrıca aktarma işlemine gerek yoktur. Yukarıdaki örnek kodda bu tutma işleminin nasıl yapıldığı anlatılmıştır. Şayet dizi temelli bir yığında (stack) tutuyor ve bağlı listeye (linked list) aktarmak istiyorsanız aşağıdaki gibi bir kod işinizi görür :
while(!stack.isEmpty())
liste.add(stack.pop());
Başarılar
mrb hocam yukarıda yığıtı link-list ile gerceklemissiniz link-list yerine bunu eleman sayı belli olan ornegin double tipinde 100 elemanlı bir diziyle gerceklemek istesek dizinin dolu veya bos oldugunuda denetleyerek nasıl olur ugrastım ama yapamadım diziyi bosaltamıyorum push tada pop tada sorun yasadım yardımcı olursanız sevinirim
Hocam cevap bekliyorum 2 gün sonra 2 gün sonra 2.vizeler baslıyo ve dizilerle push pop gercekleme cıkacak kafamda tasarımını bir turlu olusturamadım hocanın istediği dizi[100] elemanlı olsun ornegin bunun doluluk bosluk durumlarınıda inceleyen C programı
ben boyle bisey yazdım hocam#include “stdio.h”
#define MAXVAL 100
double val[MAXVAL];
int sp = 0;
void push (double f){
if (sp==100)
printf(“yıgıt daha eleman alamaz”);
else{
val[sp] = f;
++sp;
}
}
double pop(void){
double w;
if (val[0] == ‘*’){
printf(“yıgıtta eleman kalmadı”);
}
else {
w = val[sp-1];
val[sp-1] = ‘*’;
–sp;
}
return w;
}
int main(void)
{
double p;
push(3);
push(5);
push(9);
push(7);
p = pop();
printf(“%0.f”,p);
p= pop();
printf(“%0.f”,p);
p = pop();
printf(“%0.f”,p);
p = pop();
printf(“%0.f\n”,p);
p = pop();
printf(“%0.f”,p);
return 0;
ama yıgıtta eleman kalmadıgı zaman yıgıtta eleman kalmadı0 donuyo sonundaki sıfır niye geliyo orayı anlayamadım
Anladığım kadarıyla dizi ile yığın kodlamak istiyorsunuz. Basit bir kodlamayı aşağıdaki şekilde yapabilirsiniz:
#define limit 100 double a[limit]; int sayac = 0; int push(double eklenen){ if(sayac<limit){ a[sayac++] = eklenen; return 1; // basarili } return -1; // hata limit dolu daha fazla eklenemez } double pop(){ if(sayac > 0) return a[sayac -- ]; return -1; // hata stack boş olduğu halde pop }kodunuzdaki hataya gelince. pop fonksiyonunda double w tanımlamışsınız. bu değişkene değer atamadığınız için kullandığınız compiler muhtemelen içerisine 0 atıyor.
pop fonksiyonunuzda içinde değer kalmayınca ekrana değer kalmadı yazdırıyorsunuz (if’e giriyor) ancak sonra return w yapıyorsunuz. Bu durumda içinde değer olarak 0 olan değer döndürülüyor ve main fonksiyonunda ekrana printf ile yazılıyor dolayısıyla sonda gördüğünüz 0 değeri buradan geliyor.
Başarılar
double pop(){
if(sayac > 0)
return a[sayac -- ];
return -1; // hata stack boş olduğu halde pop
Hocam burda yazdıgınız kodda if deyiminden çıktıktan sonra return -1 dondurecek yanlıs mı dusunuyorum
if(sayac > 0)
return a[sayac -- ];
else
return -1; // hata stack boş olduğu halde pop
else koymamız gerekmez mi?
yine yazdıgınız kodun bu kısmındada aynı sey aklıma takıldı
if(sayac<limit){
a[sayac++] = eklenen;
return 1; // basarili
}
return -1; // hata limit dolu daha fazla eklenemez
yine else olmalı mı sorusu aklıma geliyo
yani stack dolmadığı halde -1 dondurmez mı program?
if deyiminden sadece hata olduğunda çıkacağı için bir sorun yok. Kod doğru. Yani if doğru ise zaten return yapılacak ve alttaki sizi endişelendiren return satırı hiç çalışmayacak. O satırın çalışması sadece hata olduğunda mümkün ki biz de zaten bu durumda -1 döndürmek istiyoruz. Benzer durum diğer fonksiyon için de geçerli.
Başarılar
tek bağlı ve çift vağlı listeyede örnek kod verirmisiniz. java ve netbeans için
tesekkur ederim hocam
Bağlı liste konusunun anlatımı ve örnek kodlar aşağıdaki adreste yer alıyor. İstediğiniz kod var mı hatırlamıyorum ancak oradaki kodlara bir bakıp şayet istediğiniz kod yoksa oraya yorum olarak yazmanız halinde, vakit bulunca eklemeye çalışırım.
http://www.bilgisayarkavramlari.com/2007/05/03/linked-list-linkli-liste-veya-bagli-liste/
Başarılar