Yığın ve Kuyruk Veri Yapıları

Konu Anlatımı

Yığın ve Kuyruk Veri Yapıları

Yığın ve kuyruk veri yapıları, elemanların hangi sırayla eklenip çıkarılacağını kurala bağlayan iki temel veri yapısıdır. Programlama Temelleri dersinde diziler ve fonksiyonlar konusu işlendikten sonra bu iki yapı, dizilerin çok sınırlı kullanımını daha düzenli hâle getirir.

1. Ne Öğreneceğiz ve Ön Bilgi

Bu konuda yığın ve kuyruk kavramlarını, iki yapı arasındaki çalışma farkını ve bu farkın günlük sistemlerde nerede göründüğünü öğreneceğiz. Bir atölyede üretilen parçaların sevk sırası, bir belge merkezinde işlemlerin sıraya giriş biçimi ve bir programdaki geri alma düğmesi hep bu iki kurala göre çalışır.

Ön bilgi olarak dizide eleman ekleme, okuma ve silme işlemlerini bilmek yeterlidir. Dizi değişkeninin uzunluğunu ve her konumun bir indisle gösterildiğini hatırlamak, yığın ve kuyruğun aslında dizi üzerinde kurulabildiğini anlamayı kolaylaştırır. Fonksiyon kavramı da önemlidir; çünkü ekleme ve çıkarma işlemleri çoğu zaman ayrı fonksiyonlar hâlinde yazılır.

2. Temel Kavramlar ve Sınıflandırma

Veri yapısı, verilerin bellekte nasıl saklanacağını ve üzerlerinde hangi işlemlerin yapılacağını belirleyen düzendir. Yığın, son giren ilk çıkar düzeninde çalışır: yeni eleman üst uca eklenir ve çıkarma da üst uçtan yapılır. Kuyruk ise ilk giren ilk çıkar düzenindedir; yeni eleman son uca eklenir, eleman baş uçtan çıkarılır.

Her iki yapıda da ekleme ve çıkarma yalnızca uç tarafta gerçekleşir. Ortadan eleman eklemek ya da çıkarmak bu yapıların doğasına aykırıdır, çünkü kuyrukta elemanların sırası, yığında ise üstteki öğenin ilk çıkması bozulur.

Yığında öğe sayısı için üst göstergesi, kuyrukta elemanın çıkacağı yer için baş, yeni elemanın eklendiği yer için son göstergesi kullanılır. Kapasite sınırına ulaşıldığında eklemeye devam edilemez; buna üst taşması denir. Boş bir yapıdan eleman almaya çalışmak ise alt taşmasıdır.

3. Basit Örnek ve Adım Adım Çözüm

Bir ifadede parantezlerin dengeli olup olmadığını yığınla denetleyelim. İfade şöyle yazılmıştır: { [ ( ) ] }. Açılış ve kapanış işaretleri iç içe geçtiği için denetim yalnızca sayımla değil, hangi işaretin hangisine eşleştiği bilgisiyle yapılmalıdır.

1. Adım 1: Yığını boş kabul et ve okuma göstergesini ilk karaktere getir.
2. Adım 2: Süslü açılış işaretini gördüğünde yığının üstüne ekle.
3. Adım 3: Köşeli açılış işaretini gördüğünde yığının üstüne ekle.
4. Adım 4: Parantez açılış işaretini gördüğünde yığının üstüne ekle.
5. Adım 5: Kapanış işaretlerinde yığının üstündeki açılış işaretini al.

Üç açılış işareti de üç kapanış işaretiyle eşleştiği için işaretler bittiğinde yığında hiçbir eleman kalmaz. Yığının boş olması denge sağlandığını gösterir. Yığında açılış işareti kalması durumunda ise kapanış eksiktir ve ifade dengeli değildir.

4. İleri Örnek ve Saha Uygulaması

Bir atölyede üretilen parçaların sevk edilmesi düşünülsün. Üretim sırasını bozmamak için ilk üretilen parça ilk sevk edilmelidir, bu yüzden sevk listesi bir kuyrukla tutulur. Buna karşılık bir iş emrindeki geri alma düğmesi, en son yapılan işlemi iptal ettiği için yığınla çalışır. Aynı programda iki yapının birlikte bulunması olağandır.

Saha uygulamasında karar gerektiren durum şudur: üretim hattında bir arıza çıkar ve hat durdurulur. Bekleyen parçaların listesini yığınla tutarsanız, hat yeniden çalıştığında en son üretilen parça ilk sevk edilir ve sevk sırası karışır. Bu yüzden durdurma anında kuyruğun başındaki parçanın numarası ayrıca bir kâğıda yazılmalı, hat yeniden başladığında bu numaradan devam edilmelidir.

• Kuyruk kapasitesi, üretim hattının bir vardiyada işleyebileceği parça sayısına göre belirlenir.
• Yığın kapasitesi, geri alınabilecek en uzun işlem sayısına göre seçilir.
• Her iki yapıda da eleman sayısı her adımda güncellenerek taşma ve alt taşması denetlenir.

5. Karşılaştırma Tablosu ve Denetim

Bu denetimler geliştirme sırasında adım adım yapılmalıdır. Önce küçük bir örnek elle izlenmeli, sonra kod yazılmalıdır. Yazılan kodda eleman sayısını tutan değişkenin her ekleme ve çıkarmada güncellenip güncellenmediği kontrol edilmelidir; gösterge atlandığında yapı sessizce bozulur ve hata ancak denetim sırasında anlaşılır.

İkinci denetim çıkarma sırasının doğruluğudur. Yığında çıkarılan değer, dizideki üst gösterge konumundaki değer olmalıdır. Kuyrukta ise baş gösterge her çıkarmadan sonra bir konum ilerletilir. Baş gösterge son uca ulaştığında sıfırlanması, baş taraftaki elemanların boşuna silinmesini önler.

Son bir ayrıntı: dizilerde eleman silme işlemi birinci konumdan yapılıyorsa kuyruk kurulamaz, çünkü her çıkarmada bütün elemanlar bir konum kayar ve kod yavaşlar. Bu durumda kuyruk yerine halka biçiminde bir gösterge çözümü ya da iki ayrı gösterge kullanmak gerekir.

6. Sık Yapılan Hatalar, Özet ve Kendini Dene

• Göstergeyi güncellememek: Ekleme sonrasında üst gösterge ilerletilmezse yeni eleman bir sonraki çıkarmada görülmez ve yığın boşmuş gibi davranır.
• Boş yapıdan çıkarma denemek: Eleman sayısı denetlenmeden çıkarma yapılırsa alt taşması oluşur; programa durdurma eklenmelidir.
• Kuyruğun baş taraftan büyütülmesi: Baş ucuna eleman eklenirse sıra karışır; kuyrukta ekleme daima son uca yapılır.
• Yığını kuyruk gibi kullanmak: Son eklenen ilk çıkar düzenini bekleyen bir işlem varsa kuyruk seçilirse hizmet sırası karışır.

Özet: Yığın ve kuyruk, eleman sırasını kurala bağlayan veri yapılarıdır. Yığın son giren ilk çıkar, kuyruk ilk giren ilk çıkar düzeninde çalışır; işlemler hep uçlarda yapılır. Yığın geri alma ve parantez denetiminde, kuyruk bekleyen işlerde kullanılır. Kapasite sınırı üst taşmasına, boş yapıdan almak alt taşmasına yol açar.

Kendini dene:

• Bir dizi üzerinde yığın kurmak için hangi göstergeye ihtiyaç vardır?
• Kuyrukta baş ve son gösterge aynı konumu gösterdiğinde eleman sayısı nasıl bulunur?
• Dengeli parantez denetiminde yığının boş kalması ne anlama gelir?
• Yazıcı belge kuyruğu için yığın neden uygun değildir?