Temel Veri Yapıları 3 - Kuyruk ve Yığıt

STL kütüphanesi içerisinde bulunan temel veri yapılarını incelediğimiz döküman serimizin ilk iki bölümünde vektör ve liste veri yapılarından bahsetmiştik. Serinin bu dökümanında ise liste veri yapısının çeşitli problemler için özelleşmiş bir hali olarak niteleyebileceğimiz yığıt (stack) ve kuyruk (queue) veri yapılarına göz atacağız.

Yığıt (stack)

Yığıt veri yapısı bize dinamik olarak eleman ekleme ve her defasında en son eklenen elemanı elde etme imkanı sağlar. Örneğin bir masa üzerinde üst üste duran tabakları düşününün. Tüm tabak kümesi bir yığıttır. Her yeni tabak eklediğinizde tabağı en üste koyarsınız. Her tabak alışınızda ise yine en üstteki tabak alınabilir. Şimdi tabakları her hangi bir C veri tipi ile ya da sizin oluşturduğunuz yapı (struct) ile değiştirin, işte bir STL yığıtınız var :)

Yığıt veri yapısını programlarımızda kullanmak içini şu include tanımlarını yapmamız gerekiyor:

#include <stack>
using namespace std;

Diğer tüm STL veri yapılarında olduğu gibi herhangi bir veri tipi için yığıt oluşturabilirsiniz. İsterseniz 'double' tipinde verileri tutmak üzere bir yığıt oluşturalım.

stack<double> yigit;

Şu anda yığıtımızın hiç elemanı yok. Yığıta eleman eklemek için .push() yordamını kullanıyoruz. Bu yordam yardımı ile yığıtımıza birkaç değer yükleyelim.

yigit.push(2001);
yigit.push(2002);
yigit.push(2003);

Daha öncede belirttiğimiz gibi şu anda yığıtımızın en üst kısmında en son eklenen eleman olan 2003 değeri bulunmakta. Yığıt veri yapısında yığıtın en üstünde bulunan elemanın değerini .top() yordamı ile öğrenebiliriz.

double enUst = yigit.top();                  // enUst = 2003

Yığıtın en üstünde bulunan elemanı yığıttan çıkarmak için .pop() yordamı kullanılır. Bu yordamın kullanımı sonucunda yığıtta en üstün bir altındaki eleman yeni yığıt baş elemanı olur.

yigit.pop();                  // 2003 elemanı yığıttan atıldı, şu anda yığıtın en üstünde 2002 var.

Yığıttaki elemanların sayısı .size() yordamı ile öğrenilebilir.

int elemanSayisi = yigit.size();                  // elemanSayisi = 2

Yığıtta eleman olup olmadığını öğrenmek için .empty() yordamını da kullanabiliriz. Unutmamamız gereken birşey: eğer yığıtta eleman yok ise kesinlikle .pop() ve .top() yordamlarını kullanmıyoruz.

bool bos = yigit.empty();                  // bos = false;

Kuyruk (queue)

STL kuyruk (queue) veri yapısı bize FIFO (first in,first out = ilk giren ilk çıkar) kuyrukları kullanma imkanı verir. FIFO kuyruklar gerçek hayatta karşılaştığımız çeşitli kuyruklar ile mantıksal olarak özdeştirler. (örneğin otobüs kuyruğu, marketteki kasa önü kuyruğu vb.). Kuyruğa istediğimiz kadar eleman ekleyebiliriz. Kuyruktan eleman aldığımız zaman en önce eklenen elemana ulaşırız. Gördüğünüz gibi kuyruğun bu kullanım şekli yığıt veri yapısının tam olarak tersidir. (Yığıtları LIFO kuyruklar (last in, first out = son giren ilk çıkar) olarak da adlandırıyoruz).

Her ne kadar işleyiş mantıkları tam olarak zıt olsa da yığıt ve kuyruk veri yapılarında kullandığımız yordamlar birebir aynıdır. Aşağıdaki örneği inceleyelim:

#include <queue>                  // kuyruk kullanmak için bu include tanımı gerekli
using namespace std;

void main(void) {

    queue<int> kuyruk;                  // int tipinde elemanları tutacak bir kuyruk oluşturuyoruz
    kuyruk.push(1);                  // sırası ile kuyruğa elemanlar ekliyoruz.
    kuyruk.push(2);
    kuyruk.push(3);                  // şu anda kuyruğun en başındaki eleman 1, en sonundaki eleman ise 3

    printf("ilk gelen %d^\n",kuyruk.top());                  // ekrana ilk eleman olan 1 yazdırılıyor
    kuyruk.pop();                                                   // 1 elemanı kuyruk başından atılıyor, yeni kuyruk başı 2
    printf("sonraki %d^\n",kuyruk.top());                  // ekrana 2 yazdırılıyor                
    kuyruk.pop();                                                  // 2 kuyruktan atıldı, yeni kuyruk başı son eleman olan 3
    printf("son gelen %d",kuyruk.top());                // ekrana 3 yazdırılıyor
    kuyruk.pop();                                                 // 3 kuyruktan atılıyor. kuyruk şu anda boş.

}

Birdahaki dökümanda map (hash table) veri yapısını inceleyeceğiz. Bu döküman ile ilgili _her_türlü_ konuda sitemizin forumlarını kullanarak bana sorular sorabileceğinizi, ve görüşlerinizi dile getirebileceğinizi lütfen unutmayın. Tekrar görüşmek üzere..

Deniz Aydınoğlu :: 2002 :: www.oyunyapimi.org