Yığın Veri Yapısı

Merhabalar,
Bu yazımda yığın veri yapısından bahsetmek istiyorum. Çalışması LIFO (Last In First Out - Son Giren İlk Çıkar) ilkesine dayanmaktadır. Fiziksel bir örnek vermek gerekirse yalnızca bir tek arabanın geçebileceği kadar genişlikte olan çıkmaz bir sokağa arabaların ard arda girmesi gibidir. Son giren araba ilk çıkmalıdır ki diğer arabalar çıkabilsin.

Peki Ne İşe Yarar?
Günümüzde bir çok sistem hafıza yönetiminde bu veri yapısını kullanmaktadır. Özellikle sıranın önemli olduğu durumlarda. Mesela, programlama dillerinde açtığımız parantezlerin kapatılıp kapatılmadığının kontrolü, işletim sistemi düzeyinde fonksiyonların çağrımı sırasında parametrelerin aktarımı, aritmetik işlemlerde işlem önceliğinin sağlanması ( çarpmanın toplamaya üstünlüğü), karakter katarlarının ters çevrilmesi vb. bir çok alanda kullanılmaktadır.

Teknik olarak açıklamak gerekirse...
Belirli bir hafıza bölgesini programcıdan soyutluyoruz. Direk erişimi engelliyoruz. Programcıya hafızaya erişmesi için fonksiyonlar veriyoruz. Bunlar push, pop ve isEmpty olabilir. Sırasıyla açıklayalım.

• Push

Yığına bir eleman eklemek istediğimizde bu fonksiyonu çağırırız. Fonksiyona veridiğimiz değer yığının en sonuna eklenir.

• Pop

Yığından bir eleman çekmek için kullanılır. Bu fonksiyon bize yığının en sonundaki yani son eklediğimiz elemanı yığından alır bize verir. Daha önceki elemanlara erişmek için Pop fonksiyonunu çağırmaya devam etmeliyiz. Bu fonksiyon herhangi bir parametre almaz.

• isEmpty

Bu fonksiyon ile yığının boş olup olmadığını kontrol edebiliriz.
Siz fonksiyonlarınıza istediğiniz ismi verebilirsiniz. Korumanız gereken tek şey LIFO ilkesidir. Geri kalan kısmı değiştirmekte özgürsünüz.

Hemen Java ile bir örnekleme yapalım:

package test;

import java.util.ArrayList;

class Stack
{
 private ArrayList<Object> objectList; // nesneleri tutacak generic yapımız.
 
 public Stack()
 {
  objectList = new ArrayList<Object>(); // nesnemizi üretelim.
 }
 
 public boolean isEmpty()
 {
  return objectList.isEmpty(); // liste boş ise yığında boştur.
 }
 
 public void Push(Object obj)
 {
  objectList.add(obj); // yığına eleman ekleyelim.
 }
 
 public Object Pop()
 {
  if (objectList.isEmpty())
   return null; // yığın boş ise eleman çekemeyiz. Sonuç null değeri.
  Object o = objectList.get(objectList.size()-1); // sondan bir elemanı alalım.
  objectList.remove(objectList.size()-1); // sonra bu elemanı yığından çıkartalım.
  return o; // geriye döndürelim.
 }
}


public class Main{

 public static void main(String[] args) {

  Stack s = new Stack();
  if (s.isEmpty())
   System.out.println("yığın boş.");
  s.Push(5);
  if (s.isEmpty())
   System.out.println("bu satırı görmememiz gerekiyor.");
  s.Push(45);
  System.out.println(s.Pop());
  System.out.println(s.Pop());
  System.out.println(s.Pop());
  System.out.println(s.Pop());
  if (s.isEmpty())
   System.out.println("yığında eleman yok.");
 }

}

En basit haliyle böyle gerçeklenebilirdi sanırım. Veri yapılarını açıklamaya devam edeceğim.
Görüşmek üzere...

Bağlı Listeler

Merhabalar,
Bu yazımda sizlere bağlı liste veri yapısından bahsedeceğim. Veri yapısı deyince kulağa egzotik gelebilir. Ama inanın bildiğiniz şeylerden farklı bir şey anlatmayacağım. "Bildiklerimizi bir araya getirerek bilmediğimiz bir yapıyı tanımlama" şeklinde anlıyorum veri yapılarını...

Nedir? Neden gerek duyulmuştur?
Bağlı liste veri yapısı hafızanın farklı bölgelerinde bulunan verileri birbirine katar şeklinde bağlayan yapıdır.Dizi vb. yapılar zaten bu işi sağlamıyor mu? şeklinde bir soru aklınıza tam bu satırda gelmiş olmalı. Evet sağlıyor ama bir yere kadar. Diziler hafızanın belirli bir noktasında ardışıl olarak gelir. Yani dizinin ilk elemanı hafızanın 100 nolu adresinde bulunuyorsa dizinin ikinci elemanı 101 nolu gözde bulunacaktır. Ayrıca diziler ilk oluşturulduğunda uzunluğu belli olmak zorundadır. Daha sonra genişleme imkanı yoktur. Ancak tekrar boyutlandırma yapılabilir ki bu iş oldukça maliyetlidir. İşte böyle dinamik genişleyen ucuz maliyetli bir yapıya ihtiyaç duyulduğu sırada keşfedilmiş olmalı bağlı listeler.

Bağlı derken?
Bağlı listenin her bir elemanı hafızada birbirine bir sonraki elemanın aderesini gösterecek bilgiye sahiptir. Biz yalnızca ilk elemanın adresini biliriz. İkinci elemana ulaşmak için önce birinci elemana gideriz, ondan bir sonraki yani ikinici elemanın adresini alırız daha sonra ikinci elemana ulaşabiliriz. Üç, dört, beş ... hafıza dolana kadar üretilebilir, ulaşım mekanizması hep aynı. Bağlı derken bu mekanizma kastediliyor.

İhtiyaca göre...
Sorunlar farklı olunca çözümler, dolayısıyla gereksinimler de farklı oluyor. Bağlı liste veri yapısı iki çeşittir. Tek yönlü ve çift yönlü. İlkinde sadece ileri yönlü haraket yapmak mümkünken ikinci tipde geri gelme de mümkündür. Siz kendi probleminize en uygun tipi seçmelisiniz.

Bırak gevezeliği de biraz kod yaz!

Tek yönlü bağlı liste, C örneği

#include <stdio.h>
#include <stdlib.h>

typedef struct _eleman
{
 struct _eleman *sornakiEleman; // bir sonraki elemanı işaret eder.
 int veri; // yapının sakladığı veri. istenilen tipte istenildiği kadar veri eklenebilir.
} eleman;

typedef struct
{
 eleman *ilkEleman; // bağlı listeyi temsil eden yapı. Yalnızca ilk elemanı işaret ediyor.
} bagliListe;

bagliListe *bagliListeUret();
void elemanEkle(bagliListe*,int);
void elemanCikart(bagliListe*,int);
void listele(bagliListe*);

int main()
{
 bagliListe * bl = bagliListeUret(); // yeni bir bağlı liste ürettik.
 elemanEkle(bl,6); // eleman ekleyelim.
 elemanEkle(bl,34);
 elemanEkle(bl,987);
 elemanEkle(bl,5);
 elemanEkle(bl,2);
 listele(bl); // listele.
 system("pause");
 elemanCikart(bl,3); // 3. elemanı çıkart. ( ilk eleman 0'dan başlar)
 listele(bl); // tekrar listele, farkı gör.
 system("pause");
}

bagliListe *bagliListeUret()
{
 bagliListe* bl = (bagliListe*)malloc(sizeof(bagliListe)); // yeni bir bağlı listeyi hafızada oluşturup ilgili adresi alıyoruz.
 bl->ilkEleman = NULL;
 return bl;
}

void elemanEkle(bagliListe* bl,int veri)
{
 eleman *e = (eleman*)malloc(sizeof(eleman)); // yeni bir eleman oluşturalım.
 e->sornakiEleman = NULL;
 e->veri = veri;
 eleman *son = NULL; // katarın son elemanı.
 son = (eleman *)bl->ilkEleman; // başlangıç elemanını bağlı listeden alalım.
 if (son==NULL) // listemiz boş mu?
 {
  bl->ilkEleman = e;
  return;
 }
 while(son!=NULL) // değilse özyinelemeli olarak son elemana erişmeye çalış.
 {
  if (son->sornakiEleman==NULL)
   break;
  son = (eleman*)son->sornakiEleman; // düğümler arası atlama.
 }
 son->sornakiEleman = e; // nihayet son düğümün işaretçisine kendi adresimizi yazıyoruz.
}

void listele(bagliListe* bl)
{
 eleman *e = NULL;
 e=(eleman *)bl->ilkEleman;
 int i=0;
 while(e!=NULL) // özyinelemeli listeleme fonksiyonu.
 {
  printf("%i. eleman verisi = %i\n",i++,e->veri);
  e = (eleman*) e->sornakiEleman;
 }
}

void elemanCikart(bagliListe * bl, int sira)
{
 eleman *e = NULL;
 e=(eleman *)bl->ilkEleman;
 eleman *onceki = NULL;
 int i=0;
 if (e==NULL) // listemiz boş mu?
 {
  printf("Liste bos oldugu icin cikartma yapilamiyor!\n");
  return;
 }
 while(e!=NULL)
 {
  if (i==sira)
   break;
  i++;
  onceki = e;
  e = (eleman*) e->sornakiEleman; 
 }
 onceki->sornakiEleman = e->sornakiEleman; // silmek istediğimiz elemanın bir önceki düğümü ile bir sonraki düğümü birbirine bağlıyoruz. Böylelikle aradan çekilerek silinmiş izlenimi oluşturuluyor.
 free(e); // hafıza sızıntısını önlemek için serbert bıraktığımız elemanı hafızadan silmeyi unutmayalım.

}

Diğer yüksek seviyeli dillerde (Java, C# vb.) bu veri yapısını yapmak çok daha kolay. Mantıktan yola çıkarak o dillerde de sorunsuz bir şekilde bağlı liste veri yapısını oluşturabileceğinize inanıyorum.
Görüşmek üzere...