Kuyruklar (queue)
21/11/2008 ·
KUYRUK
Kuyrukların Özellikleri
· Giriş Sırası = Çıkış Sırası
Tek bir kasanın hizmet verdiği bir süpermarkette ödeme yapmak için bekleyen insanların oluşturduğu sıra gibi bir diziye “kuyruk” (queue) adı verilir. Bu ödeme kuyruğuna ilk giren kişi sonra girenlerden önce ödemesini yapıp gider (ilk-gir, ilk-çık, yani first-in, first-out, ya da kısaca FIFO). En son giren işi ise en son ödeme yapacak olan kişidir (son-gir, son-çık, yani last-in, last-out ya da kısaca LILO). Bu FIFO ve LILO özellikleri beraberce “giriş sırasıyla çıkış sırasıyla aynıdır” diye ifade edilebilirler.
· Sırayla erişim
Bir kuyruk oluşturacak bir veri grubundaki elemanlar birbirleriyle bağlantılı olmalıdır ki kuyruktaki her eleman kuyruğa girdiği sırayla işlem görebilsin. Bağlantılı bir listede olduğu gibi bir kuyrukta da her eleman bir sonraki elemanın yerini bildiren bir adres değişkenine sahip olmalıdır, veya kuyruk elemanlarının adresleri ayrı bir adres değişkenleri dizisinde saklanmalıdır.
Kuyruklarla İlgili Özel İşlemler
· Sona Ekleme
Bir süpermarket kasası önündeki ödeme kuyruğuna aradaki bir noktadan girilmez. Fiziksel bariyerler yoksa bile etik prensipler veya toplum baskısı bunu engeller. Aynı şey kuyruk oluşturacak şekilde sıralanıp bağlanmış değişkenler için de doğrudur. Bir kuyruğa ancak en son konumdan yeni bir eleman eklenebilir.
Eğer kuyruğun son elemanının adresi pSON gibi bir değikleme için tek gereken şey yeni elemanı son elemandan sonraki eleman olarak tanıtmaktır. Bu işlemden sonra yeni eleman yeni son eleman olacaktır:
2‑8 Bir kuyruğun sona yeni bir eleman eklenmesi
pSON.pSonraki=pYeniEleman
pSON=pYeniEleman
· Önden Çıkartma
Bir dizi veya listedeki elemanlar, eğer programcı belli bir andan sonra hiç ama hiç gerekli olmayacak elemanları silmek için komutlar yazmamışsa, program çalışıp bitinceye kadar var olmaya devam ederler. Halbuki bir kuyruktaki elemanlar, üzerlerinde gerekli işlemler yapıldığı zaman –tıpkı ödemesini yapmış süpermarket müşterileri gibi- kuyruktan ayrılmalıdırlar. Kural gereği olarak, kuyruğun ilk elemanı kuyruktan ilk ayrılan eleman olacaktır:
2‑9 Öndeki elemanın kuyruktan çıkartılıp silinmesi
pİLK.Değer = BOŞ
pİLK = pİLK.pSonraki
BOŞ değer atanması başlangıçta en önde yer alan elemanın hafızadan silinmesi içindir. Bu işlem yapılmayıp bu değişken hafızada bırakılsa bile ikinci komuttaki işlemle kuyruktan çıkartılmış olacaktır.
Yığınlar (Stacks)[1]
Yığınların Özellikleri
· Son Giren İlk Çıkar
Aynı anda çok sayıda müşteriye hizmet veren büyük bir lokantada tabaklar bir yandan yıkanıp yığılırken bir yandan da yeni müşterilere servis yapmak için yığından çıkartılırlar. Bu tabak yığınının ilginç bir özelliği vardır: Yığına ilk giren tabak en altta kalmış olacağı için yığındaki diğer tabakları devirmeden yerinden kolayca alınamaz. Dolayısıyla servis yapacak bir garson çabucak işine dönmek için yığının en üstündeki tabağı, yani yığına en son eklenmiş tabağı alıp gidecektir. Kısacası bir yığını diğer veri yapılarından ayırt eden özellik son-gir, ilk-çık (last-in, first-out, kısaca LIFO) diye adlandırılır. Bir yığına ilk giren elemansa son çıkacak olan elemandır (first-in, last-out, kısaca FILO).
· Bağlantılılık
Bir yığın oluşturacak bir veri grubundaki elemanlar da birbirleriyle bağlantılı olmalıdır. Üstteki eleman çıkartılırsa sıra onun altındakine gelecektir. Üstteki elemanın bir altındaki eleman zaman sırasında göre önceki elemandır, ama liste ve kuyruklarda yaptığımız gibi alttaki elemanı sonraki eleman olarak düşüneceğiz.
Yığınlarla İlgili Özel İşlemler
· Üste Ekleme
Bir yığına da ancak en üst konumdan yeni bir eleman eklenebilir.
Eğer yığının en üst elemanının adresi pÜST gibi bir adres değişkeniyle belirlenmişse, tek gereken şey bu üst elemanı yeni eklenecek elemandan sonraki eleman olarak tanıtmaktır. Bu işlemden sonra yeni eleman üst eleman olacaktır:
Kod Örneği 2‑10 Bir yığının üstüne yeni bir eleman eklenmesi
pYeniEleman.pSonraki = pÜST |
· Üstten Çıkartma
Yığındaki en üst eleman üzerinde gerekli işlemler yapıldığı zaman yığından çıkarılmalıdır. Bunun için yapılacak şey boş elemanı “silmek” için gereken işlem neyse onu yapmak ve ondan bir önceki elemanı yeni üst eleman olarak işaretlemektir.
Kod Örneği 2‑11 Yığının üst elemanının çıkartılması
pÜST.Değer = BOŞ |
Nesneye Yönelik Programlama Dillerinde Veri Yapıları
Sınıf Değişkenleri
Bu bölümde kısaca gözden geçirdiğimiz en temel türden veri yapıları üzerinde yapılabilecek işlemler (yeni eleman sokma veya silme, önden çıkartma, sona ekleme, vb.) veri yapısını oluşturan elemanların türlerine bakmaksızın, belli adımlar atılarak gerçekleştirilirler. Dolayısıyla, programında bir bağlantılı liste, bir kuyruk vb. yarataıp kullanacak olan bir programcı belli işlemler için gereken belli adımları bilip o adımları gerçekleştirecek komutları programına eklemelidir. Yüzbinlerce programcı bu tür veri yapıları üzerinde çalışacak komut dizilerini tekrar tekrar yazmak zorunda kalmasınlar diye bu komut dizilerini önceden hazırlanmış fonksiyonlar halinde paketleyip programcıların kullanımına sunmak en mantıklı çözümdür. Yapısal programlama dillerine ait derleyicilerle birlikte gelen fonksiyon kütüphaneleri veri yapılarının kullanımını kolaylaştırabilirler. Nesneye yönelik programlama dilleri ise belli bir veri yapısı üzerinde belli işlemler yapabilecek fonksiyonları veri yapısının kendisiyle birlikte paketleyip sunarak programcıların işlerini daha da kolaylaştırırlar. Nesneye yönelik bir programlama dilinde, bir programcı belli bazı değişkenleri gruplandırarak bir karmaşık değişken veya bir veri yapısı tanımı yatattığında, o değişken grubu üzerinde gerekli işlemler yapacak belli fonksiyonları da değişken grubu tanımına ekleyebilir. Kendisiyle ilişkili fonksiyonları da tanımında barındıran bir veri grubuna “sınıf değişkeni” (class variable) denir.
Üye Fonksiyonlar
Bir sınıf değişkeninin tanımına dahil edilmiş fonksiyonlara “üye fonksiyonlar” (member functions) veya “metodlar” denir. Bir sınıf değişkeni olarak tanımlanmış bir veri yapısını bir programda kullanmak için sınıf değişkeninin üye fonksiyonlarını çağırmak yeterlidir. Örneğin, C++ dilinde bir bağlantılı liste list türü bir sınıf değişkeni ile temsil edilebilir. Tamsayı elemanlardan oluşan bir liste türü değişken
list
şeklinde, ondalıklı sayılardan oluşan bir liste ise
list
şeklinde tanımlanabilir. Aşağıdaki kod örneği bu türden bir tamsayı listesi yaratıp ona elemanlar ekleyip çıkartan bir C++ programının parçasını gösteriyor:
Kod Örneği 2‑12 Bir C++ programında bir bağlantılı liste tanımlanması ve eleman eklenmesi
list |
İngilizce bilmeyen okuyucularımız için açıklayalım: Bu örnekte kullanılan push_back() üye fonksiyonu liste sonuna, push_front() üye fonksiyonu ise liste önüne eleman eklemek için kullanılabilir. pop_back() liste sonundan, pop_front() liste başından eleman çıkartmak için kullanılırlar.
Listeler, kuyruklar veya daha karmaşık veri yapılarını temsil eden sınıf değişkenlerini kullanmak programcıların işlerini kolaylaştırdığı gibi, onlara kısa ve kolay anlaşılır programlar yazma imkanını da verir, ama veri yapıları üzerinde yapılacak işlemleri ortadan kaldırmaz veya kısaltmaz. N adım gerektiren bir arama işlemi veya N2 adım gerektiren bir sıralama işlemi, ilgili üye fonksiyonlarını çağıran birer komuttan ibaret bile olsalar aynı sayıda adım gerektirirler. Bu tür bir üye fonksiyon kullanan bir algoritmanın adım sayısını hesaplarken, her bir komutun gerektirdiği adım sayısını bilip ona göre hesap yapmalıyız. Biz bu ders notlarının metin kısmında gerçek program örnekleri vermeyeceğiz, ama bazı kod örneklerimizi daha kısa ve anlaşılır olsunlar diye nesneye yönelik bir programlama dilini kullanıyormuş gibi yazacağız.
ÖRNEK1
#include
#include
using namespace std;
int main ()
{queue<int> myqueue;
int myint;
cout << "Tam sayi giriniz (enter 0 to end):n";
do {
cin >> myint; myqueue.push (myint);} while (myint);
cout << "kuyrugun icerigi: ";
while (!myqueue.empty())
{cout << " " << myqueue.front();
myqueue.pop(); } return 0;
}Örnek 2
// queue::empty #include #include using namespace std; int main () { queue<int> myqueue; int sum (0); for (int i=1;i<=10;i++) myqueue.push(i); while (!myqueue.empty()) { sum += myqueue.front(); myqueue.pop(); } cout << "total: " << sum << endl; return 0; } |
çıktı:
total: 55 |