Merhaba sevgili dergi okuyucuları,

Bu ay sizlere soyut veri yapıları hakkında bilgiler vereceğim. Değineceğim veri yapıları arasında bu ay yığıt (stack), kuyruk (queue) ve ağaç (tree) yer alacak. Yazı bittiğinde siz de artık yığıt, kuyruk ve ağaç konusunda deneyimli birer kullanıcı olacaksınız.

Haydi başlayalım...

İlk olarak bu veri yapılarını genel anlamda anlatmaya çalışacağım. Yığıt, kuyruk ve ağaç verilerimizi işlerken kullanabildiğimiz veri yapılarıdır. Yani verilerimizi kitaplar olarak düşünürsek yığıt ve kuyruk birbirinden farklı amaçlar için üretilmiş kütüphaneler olacaklardır. Bir kitap okuyucusu için kütüphanenin nasıl, ne zaman, nerede üretildiği önemli değildir. Önemli olan kitaplarını koyabilecek bir kütüphane bulabilmesidir. Aynı şekilde yığıt, kuyruk ve ağaç için de kullanıcı yığıt, kuyruk ve ağacın veri yapılarının nasıl kodlandığını bilmek istemez; sadece bu veri yapılarının nasıl kullanılacağını bilmek ister. Bu sebeplerle bu veri yapılarına erişimimiz ve kullanımımız esnasında çağıracağımız metodların kullanımı oldukça kolaydır.

Şimdi de gelin bu veri yapılarını inceleyelim.

Yığıttan (stack) başlayalım ve örneklerle anlatalım. Bir arama kurtarma ekibini yönettiğinizi varsayalım. İnsanlar bir binada mahsur kalmış durumdalar ve siz helikopterle binanın tepesine gelip o an binanın çatı katına çıkabilmiş kişiyi alıp gideceksiniz. Şimdi bir de binadaki insanlar açısından bakalım olaya. Bu bina içerdiği kurallar bakımından biraz ilginç. İlk kural, her kata yalnız ve yalnız bir kişi yerleştiriliyor. İkinci kural, alt kat dolmadan bir üst kata herhangi birisi yerleştirilemiyor. Diğer bir kural, bu binadan ayrılacak olan kişi bulunduğu kattan daha yüksek katlarda kimsenin kalmadığına emin olmak zorunda. Ve son kural ise, binaya giriş ve çıkış binanın dışarısı ile tek bağlantı noktası olan çatı katından yapılıyor. Şimdi size geri dönelim. Sırasıyla çatı katına çıkabilmiş kişiyi alıp güvenli bir yere götürüp tekrar binaya gidiyorsunuz. Fakat ortada bir sorun var gibi, binada kimsenin kalmadığını nereden anlayacaksınız ? İşte burada devreye son teknoloji ile donatılmış binamızın çatı katındaki bir tabela giriyor. Bu tabela tüm katların boş olup olmadığını gösteriyor. Bu tabela sayesinde binada kimsenin kalmadığına emin oluyorsunuz ve arama kurtarma görevinizi başarıyla gerçekleştiriyorsunuz.

Yukarıda anlattığım kısa hikaye aslında yığıtı çok güzel bir şekilde özetliyor. Bu binaya yerleşecek kişinin en alt kattan başlayarak dolu olmayan ilk kata yerleşmesi, binadan çıkacak kişinin en üst kattan başlayarak dolu olan ilk kattaki kişi olması, binanın boş olup olmadığının bilinebilmesi bunlar bir yığıtın ana özellikleri olarak gösterilebilir. Yığıt dendiğinde bilmemiz gereken şey, yığıta gönderdiğimiz obje yığıtın en üst katına yerleşir (push) ve yığıttan obje çağırdığımızda bize yığıtın en üst katındaki, yani yığıta en son konulan obje dönülecektir (pop).

Kuyruk ile devam edelim ve yine örneklerle anlatalım. Bir banka sahibi olduğunuzu düşünün. Sahibi olduğunuz banka büyük bir mali krizin eşiğinde ve müşterilerin paralarını çekmek için bankanıza doğru yöneldikleri haberini alıyorsunuz. Pencereden dışarıya baktığınızda müşterilerin teker teker bankanızın önünde kuyruğa girdiklerini görüyorsunuz. Parasını çeken sıradan çıkıyor ve sıranın en önüne gelen yeni kişi parasını çekmeye hazırlanıyor. Ve bu arada sıraya yeni gelen kişiler de teker teker sıranın en arkasına dahil olarak sırayı büyütüyor. Sırada kimse kalmadığında siz de pencereden ayrılıp işinizin başına dönüyorsunuz.

Yukarıda anlattığım kısa hikaye kuyruk hakkında çok önemli bilgiler içeriyor. Banka sırasına giren her kişi bir objeyi temsil ediyor. Sıraya ilk gelen kişi sıranın en sonundaki kişinin arkasına geçiyor (enqueue). Sıradan çıkan ilk kişi sıranın en önünde bulunan ve işini bitirmiş olan kişi oluyor (dequeue). Kuyruk hakkında bilmemiz gereken şey eklediğimiz obje, listemizin en sonuna eklenir ve istekte bulunduğumuz obje, listenin başından verilir. Ayrıca bu normal kuyruk yapısı dışında, öncelik kuyruğu (priortiy queue) veya olay kuyruğu (event queue) gibi diğer kuyruk yapıları da kullanılmaktadır.

Yığıt ile kuyruk arasındaki farklara değinelim. Yığıtta da kuyrukta da giriş yapan obje listenin sonuna eklenir. Bir istek yapıldığı takdirde yığıt listenin son elemanını dönerken (LIFO - Last In Fırst Out) kuyruk ilk elemanını döner (FIFO - First In First Out). Yığıt daha çok geri iz takibinde (backtracking) kullanılırken, kuyruk çeşitli ağaç (tree), çizge (graph) veya bağlı liste (link list) veri yapılarının içeriklerini dolaşırken kullanılır.

Şimdi de ağaç kavramına göz atalım. Bir organizatör olduğunuzu düşünün. Bir parti düzenliyorsunuz ve olabilecek maksimum sayıda katılımcıya ihtiyacınız var. Yani olabildiğince hızlı tanıtım yapmanız lazım. Hemen en yakın arkadaşlarınızı arıyorsunuz ve onlara partiniz hakkında bilgi verip onları partinize çağırıyorsunuz. Daha sonra en yakın arkadaşlarınızın her biri kendi en yakın arkadaşlarını arıyor ve bu böyle devam ediyor. Parti günü sadece birkaç kişiye haber vermenize rağmen çok büyük bir katılım oluyor ve iyi bir organizasyon yapmanın sevincini yaşıyorsunuz.

Yukarıda anlatmış olduğum kısa hikaye ağaç veri yapısını özetliyor aslında. Her ağaç yapısının bir adet kökü (root) bulunur. Ağaç veri yapısı içindeki her objenin bir alt katmanda bulunan objelerle üst-alt (parent-child) ilişkisi vardır. Her üstöğenin birden fazla altöğesi olabilir; fakat her çocuğun bir ebeveyni olmak zorundadır. Ağaç veri yapısı her objenin altöğelerinin yeni objelerin üstöğeleri olması esasına dayanarak işler. Ağaç veri yapısındaki ilk obje köktür. Bu veri yapısındaki her objenin en üst düzeydeki akrabalık ilişkisi kökledir. Yukarıdaki hikayemizi hatırlarsak kök görevini organizatör almıştı. Organizatörün aradığı her arkadaşı, ağaç veri yapısındaki kökün çocukları yani altöğeleriydi. Her çocuk bir başka çocuk grubunun ebeveyni yani üstöğesi olacağından ağaç veri yapısı hızlı bir büyüme gösterdi ve organizatörümüz sadece birkaç kişiyi aradığı halde partisine tahmininden çok daha yüksek bir katılım oldu. Ağaç veri yapısı, bir elemanın çocuk sayısıyla üstel orantılı olarak, çok yüksek bir büyüme hızına sahip olduğu için çok yüklü miktarlarda veri saklayabilir. Ağaç veri yapısının içerdiği her objenin bir üstöğesi olduğu için herhangi bir objeye ulaşmamız ağacın içerdiği veri boyutu ile doğru orantılı değildir.

Ağaç veri yapıları daha çok veri saklamak için kullanılırken kuyruk ve yığıt; ağaç ve benzeri veri saklama amaçlı veri yapılarını dolaşmak için kullanılırlar. Bu sayede veri saklama ve sakladığımız verilere ulaşma çok daha kolay ve verimli olur. Ağaçların birçok farklı çeşidi de bu kolaylıkların kullanım alanlarına göre özelleşmesiyle ortaya çıkmıştır. Ağacın çocuk sayısı, dengesi, tuttuğu verilerin cinsi gibi pek çok etken ağaçların farklı çeşitlerinin kullanılmasında göz önüne alınan unsurlardır. Ağaç çeşitlerini tek tek ele almayı başka bir yazımıza bırakıyoruz.

Yığıt, kuyruk ve ağaç hakkında anlatacaklarım bu kadar. Umarım sizin için yararlı bir döküman olmuştur. Diğer ay yine burada buluşmak üzere..