Sıra | DOSYA ADI | Format | Bağlantı |
---|---|---|---|
01. | Yiğin Ve Kuyruk | ppt | Sunumu İndir |
Transkript
1Ders İçeriği• Yığın– Tanım ve Operasyonları• Kuyruk– Tanım ve Operasyonları
Yığın ve Kuyruk• Yığın ve kuyruk modelleri verinin geçici olarak saklanması gerektiği ve işlemlerin belirli bir sırada yapılması gerektiğinde kullanılan bir yapıdır. • Bellek parçası üzerinde işleyen yığın ve kuyruk yapıları işleyiş olarak birbirlerine ters olarak çalışmaktadırlar. 2
Yığın ve Kuyruk3İşlem Yığın KuyrukEkleme Koy(push) Ekle(add)Alma Al(pop) Çıkart(get)Sıfırla Sıfırla(reset) Sıfırla(reset)
Yığın Yapısı• Yığın tüm ekleme ve silme işlemlerinin bir uçtan yapıldığı bir veri yapısıdır.• Alternatif olarak, yığın yapısında silinecek eleman listeye eklenen son elemandır. Bu işlem son giren ilk çıkar (last in first out - LIFO) şeklinde isimlendirilir.• Klasik örnek: kafelerdeki üst üste dizili tabaklar.4
Yığın Yapısı5yığınkoy(3);koy(2);koy(12);1223yığın23yığınal();1251123yığınkoy(11);koy(5);
Yığın Gerçekleştirimi• Yığın yapısını gerçekleştirmek için 2 yol vardır.– Dizi kullanmak– Bağlantılı liste kullanmak6
Dizi Gerçekleştirimi• Yığın yapısı dizi üzerinde en fazla N tane eleman tutacak şekilde yapılabilir.7122323al();121123koy(11);
Yığın ve Operasyonları8public class Yigin { int kapasite=100; // maksimum eleman sayısı int S[]; //Yığın elemanları – pozitif tam sayı int p; // eleman sayısı public Yigin(){ // yapıcı yordams[] = new int[kapasite]; p = 0; } int koy(int item); int al(); int ust(); boolean bosmu(); boolean dolumu();}
Yığın Operasyonları – bosmu, dolumu9// yığın boşsa true döndürpublic boolean bosmu() { if (p < 1) return true; else return false;} //bitti-bosmu// Yığın doluysa true döndürpublic boolean dolumu(){ if (p == kapasite-1) return true; else return false;} // bitti-dolumu
10Yığın Operasyonları: koy// Yığının üstüne yine bir eleman koy// Başarılı ise 0 başarısız ise -1 döndürür.int koy(int yeni){ if (dolumu()){ // Yığın dolu. Yeni eleman eklenemez. return -1; } S[p] = yeni; p++; return 0;} /bitti-koy
11Yığın Operasyonları: ust // Yığının en üstündeki sayıyı döndürür// Yığın boşsa, -1 döndürürpublic int ust(){ if (bosmu()){ // Yığın başsa hata dönder System.out.println(\Stack underflow\); return -1; } return S[p-1]; }
12Stack Operations: al// En üsteki elemanı dönder.// Yığın boşsa -1 dönder.public int al(){ if (bosmu()){ // Yığın boşsa hata dönder System.out.println(“Stack underflow”); return -1; } int id = p-1; // en üsteki elemanın yeri p--; // elemanı sil return S[id]; }
13Yığın Kullanım Örneğipublic static void main(String[] args){ Yigin y = new Yigin(); if (y.bosmu()) System.out.println(“Yığın boş”); y.koy(49); y.koy(23); System.out.println(“Yığının ilk elemanı: ”+ y.al()); y.koy(44); y.koy(22); System.out.println(“Yığının ilk elemanı: ”+ y.al()); System.out.println(“Yığının ilk elemanı: ”+ y.al()); System.out.println(“Yığının ilk elemanı: ”+ y.ust()); System.out.println(“Yığının ilk elemanı: ”+ y.al());. if (y.bosmu()) System.out.println(“Yığın boş”); }
Bağlantılı Liste GerçekleştirimiBaşlangıç durumukoy(3)15629Baş3 eklendikten sonra15629Başal()3 alındıktan sonra15629Başal()9 alındıktan sonra1562Baş
15Bağlantılı Liste Gerçekleştirimipublic class YiginDugumu { int eleman; YiginDugumu sonraki; YiginDugumu(int e){ eleman = e; sonraki = NULL; }}public class Yigin { private YiginDugumu ust; public Yigin() {ust = null;} void koy(int eleman); int al(); int ust(); boolean bosmu();};
16Yığın Operasyonları: koy, bosmu// Yığına yeni eleman eklepublic void koy(int eleman){ YiginDugumu x = new YiginDugumu(eleman); x.sonraki = ust; ust = x;}// Yığın boşsa true döndürpublic boolean bosmu(){ if (ust == NULL) return true; else return false;}
17Yığın Operasyonları: ust// Yığının ilk elemanını döndürpublic int ust(){ if (bosmu()){ System.out.println(“Stack underflow”); // Boş yığın return -1; // Hata } return ust.eleman;} //bitti-ust
18Yığın Operasyonları: Al// Yığının en üst elemanın siler ve döndürür.public int Al(){ if (bosmu()){ System.out.println(“Stack underflow”); // Boş yığın. return -1; // Hata } YiginDugumu temp = ust; // Bir sonraki elemana geç ust = ust.sonraki; return temp.eleman;} //bitti-al
19Yığın Kullanım Örneğipublic static void main(String[] args){ Yigin y = new Yigin(); if (y.bosmu()) System.out.println(“Yığın boş”); y.koy(49); y.koy(23); System.out.println(“Yığının ilk elemanı: ”+ y.al()); y.koy(44); y.koy(22); System.out.println(“Yığının ilk elemanı: ”+ y.al()); System.out.println(“Yığının ilk elemanı: ”+ y.al()); System.out.println(“Yığının ilk elemanı: ”+ y.ust()); System.out.println(“Yığının ilk elemanı: ”+ y.al());. if (y.bosmu()) System.out.println(“Yığın boş”); }
Uygulama• Derleyici/kelime işlemciler– Derleyicileri düşünecek olursak yazdığımız ifadede ki parantezlerin aynı olup olmadığını kontrol ederler.– Örneğin: 2*(i + 5*(7 – j / (4 * k)) ifadesinde parantez eksikliği var. \)\– Yığın kullanarak ifadedeki parantezlerin eşit sayıda olup olmadığını kontrol eden programı yazınız.20
Uygulama• Yığın kullanarak parantez kontrol:1) Boş bir yığın oluştur ve sembolleri okumaya başla2) Eğer sembol başlangıç sembolü ise ( ‘(‘,’[’,’{’ ) Yığına koy3) Eğer sembol kapanış sembolü ise ( ‘)’,’]’,’}’ )I. Eğer yığın boşsa hata raporu döndürII. Değilse Yığından alEğer alınan sembol ile başlangıç sembolü aynıdeğilse hata gönder4) İfade bitti ve yığın dolu ise hata döndür.21
Kuyruk Yapısı• Kuyruk tüm ekleme işlemlerinin bir uçtan, silme işlemlerinin ise diğer uçtan yapıldığı bir veri yapısıdır.• Alternatif olarak, kuyruk yapısında silinecek eleman listede en uzun süre olan elemandır. Bu işlem ilk giren ilk çıkar (first in first out - FIFO) şeklinde isimlendirilir.• Klasik örnek: Yemek sırasında bekleyen öğrenciler.22
Kuyruk Yapısı23 19 10 523Ekle()Çıkart()• Kuyruğun başı ve sonu vardır.• Ekleme operasyonu Ekle(Enqueue)• Silme operasyonu Çıkart(Dequeue)
Kuyruk Yapısı• Kuyruk tüm ekleme işlemlerinin bir uçtan, silme işlemlerinin ise diğer uçtan yapıldığı bir veri yapısıdır.• Genel Kuyruk Operasyonları– ekle(eleman) – kuyruğun sonuna elemanı ekler – cikart() – en öndeki elemanı çıkartır ve döndürür– bosmu() – kuyruk boşsa true döndürür– dolumu() – kuyruk doluysa true döndürür24
Kuyruk Gerçekleştirimi• 2 tür gerçekleştirim vardır:– Dizi kullanarak– Bağlantılı liste kullanarak25
Dizi Kullanarak Gerçekleştirim• N boyutlu bir dizi kullanılır.• ön kuyruğun ilk elemanını tutar. Dizide ilk elemanın kaçıncı indisten başlayacağını belirtir.• arka kuyrukta son elemandan sonraki ilk boşluğu tutar.• elemanSayisi kuyruktaki eleman sayısını tutar.• Boş kuyruk eleman sayısının sıfır olduğu durumdur.• Dolu kuyruk eleman sayısının N’ye eşit olduğu durumdur.26
27Dizi Kullanarak Gerçekleştirim• Kuyruğu N boyutlu bir dizi (int K[N]) ve 3 değişken (int on, int arka, int elemanSayisi) ile gerçekleştirebiliriz.Qon = 3 arka = 3Boş kuyruk• on ve arka birbirlerine eşit ve elemanSayisi = 0 Boş kuyrukelemanSayisi = 0 1 2 3 4 5 60Qon = 38615arka = 6Yarı dolu kuyruk24 7• on kuyruktaki ilk elemanı tutar• arka son elemandan sonraki ilk boş yeri tutar.9elemanSayisi = 3 1 2 3 4 5 60Qon = 38615arka = 3Dolu kuyruk 24 7• on ve arka birbirlerine eşit ve elemanSayisi=7 Dolu kuyruk.9elemanSayisi = 7 1 2 3 4 5 60
28Dizi Kullanarak GerçekleştirimQon = 38615arka = 120 eklensonra420 1 2 3 4 5 60Qon = 38615arka = 6İlk durumQon = 38615arka = 044 eklensonraQon = 486arka = 1420012 345620684Arka = 1Ön = 4Kuyruğun kavramsal görünümü:Döngüsel dizi 1 2 3 4 5 60 1 2 3 4 5 60 1 2 3 4 5 60elemanSayisi = 3elemanSayisi = 4elemanSayisi = 515 silinsonraelemanSayisi = 4Ekle(4)Ekle(20)Çıkart()
29Dizi Gerçekleştirimi: Tanımlama ve Operasyonlarpublic class kuyruk { private int K[N]; // kuyruk elemanlarını tutan dizi private int on; // kuyruğun başı private int arka; // kuyruğun sonu private int elemanSayisi; // kuyruktaki eleman sayısı public kuyruk(); public boolean bosmu(); public boolean dolumu(); public int ekle(int item); public int cikart(); };
30Kuyruk Operasyonları: Yapıcı, bosmu, dolumu// yapıcı yordampublic Kuyruk(){ on = arka = elemanSayisi = 0;} // Kuyruk boşsa true döndürpublic boolean bosmu(){ return elemanSayisi == 0;} // Kuyruk doluysa ture döndürpublic boolean dolumu(){ return elemanSayisi == N;}
31Kuyruk Operasyonları: Ekle// Kuyruğa yeni bir eleman ekle // Başarılı olursa 0 başarısız olursa -1 döndürpublic int ekle(int yeni){ if (dolumu()){ System.out.println(“Kuyruk dolu.”); return -1; } K[arka] = yeni; // Yeni elemanı sona koy arka++; if (arka == N) arka = 0; elemanSayisi++; return 0;}
32Kuyruk Operasyonları: Çıkart// Kuyruğun önündeki elemanı çıkart ve döndür.// Kuyruk boşsa -1 döndürpublic int cikart(){ int id = -1; if (bosmu()){ System.out.println(“Kuyruk boş”); return -1; } id = on; // ilk elemanın olduğu yer on++; if (on == N) on = 0; elemanSayisi--; return K[id]; // elemanı döndür}
33Kuyruk Kullanım Örneği01 public static void main(String[] args){02 Kuyruk k;0304 if (k.bosmu()) 05 System.out.println(“Kuyruk boş”); 0607 k.ekle(49);08 k.ekle(23);09 10 System.out.println(“Kuyruğun önü: ”+ k.cikart());11 k.ekle(44);12 k.ekle(22);1314 System.out.println(“Kuyruğun ilk elemanı: ”+ k.cikart()); 15 System.out.println(“Kuyruğun ilk elemanı: ”+ k.cikart()); 16 System.out.println(“Kuyruğun ilk elemanı: ”+ k.cikart());17 System.out.println(“Kuyruğun ilk elemanı: ”+ k.cikart()); 1819 if (k.bosmu()) 20 System.out.println(“Kuyruk boş”); 21 }
34Dizi Gerçekleştirimi: Son Söz• Kuyruğu N-1 elemanlı bir dizi (int K[N]) ve 2 tane değişken (int on, int arka) ile gerçekleştirebiliriz.• Aşağıdakileri nasıl tanımlayabileceğimizi düşünün. – Boş kuyruk– Dolu kuyrukQon = 38615arka = 2Dolu kuyruk 24 7Qon = 3 arka = 3Boş kuyruk• On ve arka birbirine eşit ise boş kuyruk• On ve arka arasında 1 tane boşluk varsa dolu kuyruk
Bağlantılı Liste GerçekleştirimiBaşlangıç durumuekle(3)15629Ön Arkacikart()15629Ön3Arka3 eklendiktensonracikart()1562Ön3Arka9 çıkartıldıktan sonra156Ön3Arka2 çıkartıldıktan sonra
36Tanımlama ve Operasyonlarpublic class KuyrukDugumu { public int eleman; public KuyrukDugumu sonraki; public KuyrukDugumu(int e){ eleman = e; sonraki = null; }}public class Kuyruk{ private KuyrukDugumu on; // Kuyruğun önü private KuyrukDugumu arka; // Kuyruğun arkası public Kuyruk(){ on = arka = null; } public boolean bosmu() { ... } public void ekle(int eleman) { ... } public int cikart() { ... }}
37Kuyruk Uygulamaları•Yazıcı kuyruğu•Telesekreter