KUYRUK YAPILARI:
Kuyruk yapıları insanların yabancı olmadıkları ve insanlara uzak olmayan bir yapıdır. Günlük yaşamda bu yapı ile sık sık karşılaşırız. Örneğin bir otobüs durağında, bir markette veya bir bankada karşı karşıya kaldığımız durum doğrusal kuyruk yapılarına tıpa tıp uyar. Otobüs durağına ilk gelen kişi otobüse ilk biner diğer gelenlerde sırası ile otobüse biner. Aynı durum markette de geçerlidir. Kasaya önce gelen parasını önce öder ve gider sıra ile diğerleri de işlerini yaparak kuyruktan çıkar[1].
Ör: n elemanlı doğrusal bir kuyruk tanımı
K: Kuyruğun ismidir. Büyük parantez içindeki ‘n’ kuyruğun alabileceği en fazla eleman miktarı ve tip de kuyrukta işlem görecek verilerin tipini belirtir[1].
Kuyruğun uçlarına verilen isimler bekleme sırasının hareket yönüne göre belirlenir. Elemanların çıkarıldığı uca kuyruk başı (head), eklendiği uca ise kuyruk sonu (tail) adı verilir. Ekmek kuyruğunda kuyruk başı ekmeği alan kişidir. Kuyruk sonu ise sıraya en son giren kişidir[3].
Kuyruk ve yığın modelleriyle, program tasarımında birçok yerde karşılaşılır. Örneğin, verinin geçici olarak bir yerde tutulması gerektiğinde işlerin ilk karşılaşıldığı sırada yapılması için sıraya koyulması gerektiği yerlerde ya da bu modellerin davranışına denk düşen bir problemin çözümünde ilk başvurulan “veri yapısı/modeli” denilebilir[2].
1.1 Doğrusal Kuyruk Yapısı:
Doğrusal kuyruk bir doğrusal listedir. Örneğin doğrusal bir kuyruk yapısı şekilde görülmektedir. Kuyruğun bir başı bir de sonu vardır. Kuyruğa eleman ekleme işlemi kuyruk sonundan (Ks) eleman çıkarma işlemi de kuyruk başından (Kb) genel kuyruk tanımında olduğu gibi doğrusal kuyruk yapısı tanımlanırken kuyruğa bir isim verilir ve kuyruğun eleman sayısı belirtilir.
Ör: 10 elemanlı tamsayı türünde bir kuyruk tanımı şöyledir;
Kuyruğun yapısı kuyruğa ilk giren eleman ilk çıkar mantığına göre çalışır. Diğer bir deyişle, kuyruk “ilk gelen ilk servis alır” mantığına göre çalışan bir veri yapısıdır.
Yığında tek indis elemanı var iken, kuyrukta iki adet indis elemanı bulunur. Bu elemanlara Kb ve Ks denir. Kb kuyruktan eleman çıkarmak için kullanılan değişken Ks ise kuyruğa eleman eklemek için kullanılan değişkendir. Doğrusal kuyrukta kuyruğa eleman eklemek istendiğinde kuyruğun Ks değişkeni eleman çıkarmak istendiğinde ise kuyruğun Kb değişkeni işleme alınır.
Kuyruk indis elemanları olan Ks ve Kb değerleri daima arttırılırlar. Yığında bulunan indis elemanı yığına eleman eklenirken attırılır ama yığından eleman çıkarılırken değeri azaltılır. (FİFO-First İn First Out)[1].
Kuyruğa eleman ekleme ve eleman çıkarma işlemi belirli kısıtlar dahilinde yapıldığı için doğrusal kuyrukta ortalardaki bir elemana ulaşmak için onun önünde bulunan tüm elemanların kuyruktan çıkarılması gerekir. Bu durum yığın yapısına benzediği için kuyruk üzerinde yapılacak işlemleri sınırlar. Daha sonra inceleneceği gibi öncelikli elemanı işleyen kuyruklarda bu durum ortadan kalkmaktadır.
İstenen eleman en önde olacak şekilde öncelikli kuyrukların oluşturulmasına olanak veren algoritmalar geliştirilmiştir. Doğrusal kuyruk yapısını en uygun gerçek yaşamdan market orada alış veriş yapan müşteriler verilebilir. Alışveriş yapmak üzere markete gelen müşteriler kasadan geçerken sırayla geçerler ve kasaya ilk gelen ilk defa kasadan geçer. Bilgisayarda sisteme gelen “iş” istekleri bir kuyrukta sıraya sokulur işleme alınmak istenen işler kuyruktan çıkarılarak işleme alınırlar[1].
1.1.1 Doğrusal Kuyruğa Eleman Ekleme :
Diğer veri yapılarında olduğu gibi tanımlanan doğrusal kuyruk yapısında da eleman ekleme ve eleman çıkarma işlemleri yapılabilmelidir. Böylece tanımlanan kuyruk yapısı programlar tarafından kullanılabilir.
Algoritma Doğrusal Kuyruğa Eleman Ekle (k,Kb,Ks,n,İş)
// Bu algoritma “n” eleman kapasiteli “k” isimli doğrusal kuyruğa “iş” elemanı ekler. “Ks”, “Kb” değerleri kuyruğun indisleridir.//
1.1.2 Doğrusal Kuyruktan Eleman Çıkarma :
Veri yapılarında saklanan veriler ihtiyaç halinde kuyruktan çıkarılıp işlenebilmelidirler. Algoritma 1.1.2’de doğrusal kuyruk yapılarında saklanan verilerin ihtiyaç halinde bu yapıdan çıkarılmasını sağlayan algoritma verilmiştir.
Algoritma Doğrusal kuyruktan eleman çıkarma (k, iş, Kb, Ks)
Doğrusal kuyruk yapıları bilgisayar belleğini etkili kullanan veri yapıları değildir. Doğusal kuyrukta dikkat edilirse Kb ve Ks değerleri devamlı arttırılmakta bu durum kuyruğa eleman eklemede problem yaratmaktadır.
Şekil 1.2. Doğrusal Bir Kuyruğa Eleman Ekleme ve Çıkarma İşlemi[1].
Başlangıçta kuyruk boş olsun sonra sırası ile A,B,C elemanlarını kuyruğa ekleyelim. Sonra kuyruktan A ve B elemanlarını çıkaralım. Şimdi de D ve E elemanlarını kuyruğa eklemek isteyelim. Şekilde de görüleceği üzere D elemanı kuyruğa problemsiz eklenir. Ancak E elemanı eklenmek istendiğinde kuyrukta problem oluşur. Oysa başlangıçta kuyruktan çıkarılan A ve B elemanlarının yerleri boştur.
Doğrusal kuyruğun indis değişkenleri olan Kb ve Ks’nin değerlerinin daima arttırılması yukarıda olduğu gibi problem yaratmaktadır. Doğrusal kuyruk yapısının neden olduğu bu problem dairesel kuyruk ile çözülmektedir[1].
1.2. Dairesel Kuyruk Yapısı:
Doğrusal kuyrukta eleman eklerken oluşan problem, dairesel kuyruk kullanılarak önlenir. Dairesel kuyruk yapısı şekil 1.2.1’ de görülmektedir. Dairesel kuyruk fiziksel olarak yer bulunduğu sürece doğrusal kuyruğun eleman eklemede çıkardığı problemleri çözer. Eğer dairesel kuyruk fiziksel olarak dolu ise o zaman eleman eklemek mümkün olmaz.
Dairesel kuyruk yapısı ile bellek daha etkin kullanılır. Dairesel kuyruğa eleman ekleme ve eleman çıkarma algoritmaları aşağıda verilmiştir. Dairesel kuyruk yapısında elemanlar bir dizide olduğu gibi art arda gelmekteler ve kuyruğun en son elemanı kuyruğun birinci elemanını işaret etmektedir[1].
Algoritma Doğrusal Kuyruk Yapısına Eleman Ekleme (Kb, Ks, K, n, İş)
//Bu algoritma n elemanlı dairesel “k” kuyruğuna “iş” elemanını ekler. Kb ve Ks kuyruğu ilk ve son elemanı gösteren indislerdir.
Algoritma Dairesel Kuyruk Yapısından Eleman Çıkarma (Kb,Ks,K,n,İş)
// Bu algoritma “n” elemanlı dairesel “K” kuyruğundan “Kb” ile gösterilen elemanı çıkarır ve “İş” değişkenine yükleyerek istek yapan algoritmaya gönderir.//
1.3. Öncelikli Kuyruklar:
Kuyruk tanımında, İGİÇ yapısı esas olarak alınmıştır. Oysa ki, biraz daha geniş anlamda, kuyruğu elemanları listenin neresinden eklenirse eklensin, aynı uçtan eksilen veri yapıları olarak ta tanımlayabiliriz. Toplumsal hayatımızda, bir arkadaşımızı gördüğümüzde, ya da acelemiz olduğunda başkalarının haklarını hiçe sayarak kuyruğa aralardan girmeye “kaynama ya da kaynak” adı veririz. Fark edildiği zaman kuyruktakilerin protestolarına yol açan bu davranış kaynayana öncelik sağlar. Pek adil görünmeyen bu işlem bilgisayarda öncelikle yapılmasını istediğimiz işler için, ya da kuyruğu belli bir mantık yapısı ile (ör; alfabetik sırada) kurmak istediğimiz zaman işimize yarar[3].
Öncelikli kuyruk uygulamasında kuyruğa girecek verilerin veya nesnelerin birer öncelik değeri vardır ve ekleme bu öncelik değerine bakılarak yapılır. Eğer eklenecek verinin önceliği en küçük ise, yani en önceliksiz ise, doğrudan kuyruğun sonuna eklenir; diğer durumlarda kuyruk üzerinde arama yapılarak kendi önceliği içerisinde sona eklenir. Örneğin bazı çok prosesli işletim sistemlerinde bir proses işleme kuyruğu vardır ve yürütülme için hazır olan proseslerin listesi bir kuyrukta tutulur. Eğer proseslerin birbirine göre herhangi bir önceliği yoksa prosesler kuyruğa ekleniş sırasına göre işlemci üzerinde yürütülürler[2].
Yukarıdaki yazının word dosyası halini ön izlemesi aşağıdaki gibidir. Ön izlemenin altında da dosyayı bilgisayarınıza indirebilirsiniz.
Kuyruklar hakkında ahzırlanmış ppt Sunum dosyasına yani slaytınada bu linkten ulaşabilirsiniz.