BİL207U-VERİ YAPILARI
Ünite 3: Yığın ve Kuyruk Yapısı
Giriş
Programlama dillerinde çalışırken genelde veriler listeler halinde düzenlenir. Liste olarak düzenlenen verilerle çalışmak için kullanılan Array ve ArrayList sınıfları önceki ünitelerde incelenmişti. Bu veri yapıları, verilerle çalışmak için uygun bir biçimde gruplandırmaya yardımcı olsa da her iki yapıda da sorun çözümlerini fiilen tasarlamak ve uygulamak için gerçek bir soyutlama sağlamaz. Anlaşılması kolay soyutlamalar sağlayan liste yönelimli iki veri yapısı yığın ve kuyruk yapılarıdır. Yığın yapısında veriler listenin yalnızca bir ucundan eklenir ve aynı uçtan çıkarılır. Kuyruk yapısında ise veriler bir uca eklenir ve listenin diğer ucundan kaldırılır. Veri yapılarını uygun ve verimli kullanmayı öğrenmek, uzman programcıyı ortalama programcıdan ayıran becerilerden biridir. Uzman programcı, bir programın verilerini uygun bir veri yapısında düzenlemenin verilerle çalışmayı kolaylaştırdığını bilir. Aslında veri soyutlamayı kullanarak bir bilgisayar programlama problemini düşünmek, probleme ilk etapta iyi bir çözüm bulmayı kolaylaştırır.
Yığın (Stack) Yapısı
Yığın yapısı, programlama dillerinde en sık kullanılan veri yapılarından biridir ve anlaşılması kolaydır. Tek taraflı veri giriş ve çıkışına izin veren yığın yapısı, verileri sıralı olarak tutar. Yığın; yalnızca yığının tepesi olarak adlandırılan, listenin sonundan erişilebilen ögelerin bir listesi olarak tanımlanabilir. Yığın için standart model, bir restorandaki tabak yığınıdır. Yığındaki tabaklar her zaman üstten çıkarılır. Yığına ekleme yapılacaksa da üstten ekleme yapılabilir. Yığın, Son Giren İlk Çıkar (LIFO-Last In First Out) veri yapısı olarak bilinir.
Yığın Operasyonları
Bir yığındaki iki temel işlem, yığına ögelerin eklenmesi ve ögelerin yığından çıkarılmasıdır. Yığınlara öge eklemek için Push (itme) işlemi kullanılır. Yığından ögeyi çıkarTmak için ise Pop(Çekme) işlemi kullanılabilir. Bir yığın üzerinde gerçekleştirilecek diğer birincil işlem ise en üstteki ögeyi görüntülemektir. Pop işlemi en üstteki ögeyi döndürürken ögeyi yığından kaldırır. Ögeyi yığından kaldırmadan sadece görüntülemek için kullanılan işlem ise C# dilinde Peek(Tepe) olarak adlandırılır. Diğer dillerde de Peek işlemine benzer operasyonlar (Top vs.) vardır. Bir yığın uygulaması, verileri tutmak için temel bir yapı kullanmalıdır. Yığın uygulamasında, yeni ögeler eklendiğinde yeniden boyutlandırma konusunda kolaylık sağlayacağı için ArrayList kullanılacaktır. C# nesne yönelimli programlama konusunda yetenekli bir programlama dilidir. İhtiyacımız olan en önemli değişken, yığın ögelerini depolamak için bir ArrayList nesnesidir. İzlememiz gereken diğer veri, dizin işlevi gören basit bir tam sayı değişkeni ile kullanacağımız yığının üst kısmıdır. Yeni bir Yigin nesnesi başlatıldığında değişken başlangıçta -1 olarak ayarlanır. Yığına her yeni öge Push edildiğinde değişken 1 artırılır. Uygulanacak ilk yöntem Push metodudur. Kod, ArrayList Ekle metodunu çağırır ve
kendisine iletilen değeri ArrayList’e ekler. Pop yöntemi üç şey yapar: en üstteki ögeyi yığından çıkarmak için RemoveAt metodunu çağırır, index değişkenini 1 azaltır ve son olarak yığından çıkarılan nesneyi döndürür. Peek metodu, argüman olarak indeks değişkenini alır ve en üstteki ögeyi döndürür. Clear yöntemi, ArrayList sınıfında aynı isimli metodu çağırır. Count özelliği, yığındaki ögelerin sayısını yanlışlıkla değiştirmek istemediğimiz için salt okunur bir özellik olarak yazılmıştır.
Stack Sınıfı
Stack sınıfı, bir LIFO koleksiyonunu veya bir yığını temsil eden ICollection arabiriminin bir uygulamasıdır. Sınıf, C#’ta yığına aktarılan ögelere dinamik olarak ayrılacak alan sağlayan bir ara bellek oluşturmak için kullanılır. Stack sınıfı; değerleri ekleme (push), kaldırma (pop) ve gözetleme (peek) yöntemlerini içerir. Yığındaki ögelerin sayısını belirlemek, yığının tüm ögelerini temizlemek ve yığın değerlerini bir dizi olarak döndürmek için de kullanılan yöntemler vardır. Stack sınıfı kullanarak yeni bir yığın oluşturmak için çeşitli yöntemler vardır. Varsayılan stack oluşturucusu, başlangıç kapasitesi 10 veri olan boş bir yığın oluşturur. Stack sınıfı dinamik bir yapıdadır. Veriler eklendikçe yığının kapasitesi arttırılır. Yığınlar tam kapasiteye her ulaştığında, kapasiteleri iki katına çıkarılır. Örneğin 10 veri kapasiteli bir stack, son değerde eklendikten sonra 20 veri kapasitesine genişletilir. Varsayılan stack oluşturucusunun yerine boyut belirtilerek de yığın oluşturulabilir. Yığının başlangıç kapasitesi yığın oluşturulurken belirtilir. İlk oluşturulma esnasında boyut belirtmek daha verimli programlar yazılmasını sağlayabilir. Yığın boyutunun her zaman eleman sayısından 1 fazla olması gerekir. Mevcut yığınınız 20 eleman içeriyorsa yığını oluştururken 21 eleman ile oluşturabilirsiniz. Stack sınıfı ile diğer yığın oluşturucu yöntemi, başka bir koleksiyon nesnesinden bir yığın nesnesi oluşturmanıza olanak tanır. Örneğin, constructora hazır bir dizi ilettiğinizde yeni yığın dizinin elemanları ile oluşturulur.
Stack Sınıfında Temel Yığın İşlemleri
Programın akışına göre yığınlar üzerinde farklı işlemler yapılabilir. Daha önceki konularda anlatıldığı Push ve Pop birincil yığın işlemlerindendir. Yığına veri eklemek için Push, yığından veri kaldırmak için ise Pop yöntemleri kullanılır.
Peek Yöntemi
Yığınlar ile çalışırken bazı durumlarda tepedeki değeri kontrol etmemiz gerekir. Pop işlemi yığının tepesindeki değeri versede, değeri yığından kaldırdığı için her zaman kullanılamaz. Peek yöntemi, ögeyi yığından çıkarmak zorunda kalmadan yığının tepesindeki ögenin değerine bakmamızı sağlar. Bu yöntemi, yığının en üstündeki ögeyi çıkarmadan değerini öğrenmek için kullanabilirsiniz.
Clear Yöntemi
Yığının içerisindeki tüm elemanları temizlememiz gereken durumlarda, eleman sayısı kadar Pop işlemi uygulamak yerine Clear yöntemi uygulanabilir. Clear yöntemi;
yığındaki tüm elemanları kaldırır, öge sayısını sıfır olarak ayarlar. Bir yığının gerçek kapasitesini inceleyemeyeceğimiz için Clear yönteminin bir yığının kapasitesini etkileyip etkilemediğini söylemek zordur. Bu nedenle kapasitenin başlangıçtaki varsayılan 10 öge boyutuna ayarlandığını varsaymak en iyisidir.
Contains Yöntemi
Bir ögenin, yığın içerisinde bulunup bulunmadığını kontrol etmek için Contains yöntemi kullanılabilir. Contains yöntemi öge yığının içeriğinde mevcut ise True değer, mevcut değilse False değer döndürür.
CopyTo ve ToArray Yöntemleri
CopyTo yöntemi, bir yığının içeriğini tek boyutlu bir diziye kopyalamak için kullanılır. Hedef dizi, tüm yığın nesnelerinin veri türüyle aynı olmalıdır. CopyTo yöntemi, hedef dizi ve başlangıç indeksini gösteren iki parametre alır. Yığının ögeleri LIFO şeklinde kopyalanır. Yığına son eklenen öge, dizinin ilk elemanı olacaktır.
Yığın Sınıfı Örneği: Girilen Kelimeyi Ters Çevirme
Yığınlar, programlama dünyasında birçok sorunu çözebilen yapılardır. Kitabınızın bu bölümünde yığın yapıları kullanılarak basit bir problem çözülecektir. Bu bölümdeki problem farklı yapılar kullanılarak çözülse de amaç yığın yapısını incelemektir. Çözülmek istenilen problem, konsoldan girilen kelimenin tersinin yine konsol ekranında yazdırılmasıdır.
Kuyruk (Queue) Yapısı
Doğrusal veri yapılarının diğer önemli yapısı Kuyruk (Queue) yapılarıdır. Kuyruk; verilerin liste olarak tutulduğu, yeni gelen verinin listenin arkasına eklendiği, kaldırma işleminin ise listenin önündeki veriye uygulandığı bir yapıdır yani her zaman ilk önce giren veri ilk çıkar (FIFO-First In First Out). Kuyruk yapısına, banka sırası örnek olarak verilebilir. Bankada sırası gelen müşteri işini bitirir ve sıradakinin işlemi başlar. Yeni gelen müşteriler kuyruğun arkasından sıraya eklenir. Kuyruklar, ögeleri oluştukları sırayla depolamak için kullanılır. Bir işletim sistemine veya yazdırma biriktiricisine gönderilen işlemleri sipariş etmek için kullanılabilir.
Kuyruk Operasyonları
Kuyruk yapıları için üç temel işlem vardır. Bu işlemlerden ikisi listeye eleman eklemek ve listeden eleman kaldırmak için kullanılır. Kuyruğa yeni öge ekleme işlemi Enqueue (Sıraya Alma) olarak adlandırılır. Kuyruktan öge çıkarma işlemi ise Dequeue (Sıradan Çıkarma) olarak adlandırılır. Enqueue işlemi kuyruk sırasının sonuna bir öge ekler. Dequeue işlemi sıranın önündeki ögeyi kaldırır. Bir kuyrukta gerçekleştirilecek diğer temel işlem, başlangıç ögesini görüntülemektir. Yığın yapısında incelediğimiz Peek yöntemi kuyruk yapısında da kullanılır. Kuyruk yapısının en öndeki ögesini görüntülemeyi sağlar ancak listeden çıkarmaz.
Kuyruk Sınıfı Örnek Uygulama
C# dilinde, Yığın yapısında olduğu gibi, kuyruk yapısını oluşturmak içinde dil ile birlikte gelen nesneler kullanılabilir. Queue nesnesi kullanılarak yeni bir kuyruk oluşturulabilir. Nesne varsayılan olarak 32 eleman kapasiteli bir kuyruk oluşturur. Kuyruğun kapasitesi doldukça bir sonraki kapasite iki katı olacak şekilde arttırılır. Yani varsayılan değer (32 öge) ile oluşturulan kuyruğun kapasitesi dolduğunda 64 eleman kapasitesine çıkarılacaktır. Buradaki kapasiteyi her defasında iki katına çıkaran sayı, büyüme faktörü olarak adlandırılır. Varsayılan kapasite dışında istenen büyüklükte kuyruk oluşturulabilir.
Öncelikli Kuyruklar: Kuyruk Sınıfından Türetme
Bildiğiniz gibi kuyruk, yapıya ilk yerleştirilen ögenin yapıdan çıkarılan ilk öge olduğu bir veri yapısıdır. Bunun sonucu olarak kuyruğa ilk giren ögenin en eski öge olduğu anlaşılabilir. Bazı uygulamalarda, kuyruktan çıkarılacak ögenin en eski olan değil en yüksek öncelikli verinin olması gerekebilir. Ögelerin kuyruk içerisindeki önemini belirten duruma öncelik sırası denir. İşlemlerinde öncelik sıralarını kullanan birçok uygulama vardır. Örneğin bilgisayarlar üzerinde çalışan işletim sistemleri uygulamalar arasında öncelik sıralarını farklı belirleyebilir. Dosya kopyalama gibi işlemlerin öncelik sırası yazdırma gibi işlemlerden daha önce gelebilir. İşlemler veya görevler genellikle önceliklerine göre numaralandırılır; Öncelik 0 işlemi, Öncelik 20 görevinden daha yüksek önceliğe sahiptir. Bir öncelik kuyruğunda depolanan ögeler, normalde anahtarın öncelik düzeyi olduğu ve değerin ögeyi tanımladığı anahtar-değer çiftleri olarak oluşturulur. Öncelik sırası için değiştirilmemiş bir Queue nesnesi kullanılamaz. Dequeue yöntemi, çağrıldığında kuyruktaki ilk ögeyi kaldırır. Öncelik sırası uygulamak istenen Queue nesnesinde, önceliğe göre kuyruktan çıkarma işlemi yapmak için Dequeue işlemi devre dışı bırakılır. Queue nesnesinden programın ihtiyacına göre öncelikli kuyruk sınıfı üretilebilir.