VERİ YAPILARI VE
PROGRAMLAMA
(BTP104)
(BIP116)
Yazar:
Doç.Dr.İ.Hakkı.Cedimoğlu
BIP116-H9-1
BTP102-H9-1
SAKARYA ÜNİVERSİTESİ
Adapazarı Meslek Yüksekokulu
Bu ders içeriğinin basım, yayım ve satış hakları
Sakarya Üniversitesi’ne aittir.
"Uzaktan Öğretim" tekniğine uygun olarak hazırlanan bu ders içeriğinin
bütün hakları saklıdır.
İlgili kuruluştan izin almadan ders içeriğinin tümü ya da
bölümleri mekanik, elektronik, fotokopi, manyetik kayıt
veya başka şekillerde çoğaltılamaz,
basılamaz ve dağıtılamaz.
Copyright
© 2004 by Sakarya University
All rights reserved
No part of this course contenet may be reproduced
or stored in a retrieval system, or transmitted
in any form or by any means mechanical, electronic,
photocopy, magnetic, tape or otherwise, without
permission in writing from the University.
Sürüm 1
Sakarya........ 2004
S1
BIP116-H9-1
BTP102-H9-1
KUYRUK (QUEUE) YAPISI
Bu Haftanın Hedefi:
Bu haftaki dersimizde kuyruk (queue) yapısı ve
algoritmik incelenmesi hakkında detaylı bilgi
verilecektir.
Bu Haftanın Materyalleri
Bu haftaki dersimizde kullanacağımız bir materyal
bulunmamaktadır.
Kullanılan semboller
Animasyon
Soru
Veritabanı
Bağlantılı Soru
Simülasyon
Püf Noktası
1
BIP116-H9-1
BTP102-H9-1
Giriş
Kuyruk (queue), eleman eklemelerin sondan (rear) ve eleman çıkarmaların baştan (front) yapıldığı
özel bir dizi yapısıdır. İlk giren - ilk çıkar (First-in-First-out (FIFO)) kuralıyla erişimin yapıldığı, ara
elemanlara erişilemediği veri yapısı olarak da bilinir. Gündelik hayattan örnek olarak bankalarda,
marketlerde, duraklarda oluşan kuyruklar verilebilir. Bunların ortak özelliği, yeni bir eleman
ekleneceği zaman kuyruğun sonuna eklenmesi ve bir eleman çıkarılacağı zaman kuyrukta bulunan ilk
elemanın (kuyruktaki elemanlar içinde ilk eklenen eleman) çıkarılmasıdır. Bu yapının benzer bir
mantıkla
bilgisayar
programlarında
kullanılması
birçok
problemin
çözümünde
kolaylıklar
sağlamaktadır.
Kuyruk (queue) yapısı, yığın (stack) yapısına oldukça benzemektedir. İkisinde de eleman ekleme
işlemi en sondan yapılmaktadır. Aralarındaki fark eleman çıkartmanın yığın yapısında en sondan,
kuyruk yapısında ise en baştan yapılmasıdır.
Kuyruk (queue) yapısının bilgisayar programlarında kullanımı daha çok işletim sistemlerinde ve çoklu
ortamlarda görülmektedir. Örneğin, yazıcı kuyruk yapısıyla işlemleri gerçekleştirmektedir. İlk olarak
yazdır komutu verilen belge yazdırılmakta, diğerleri ise kuyrukta bekletilmekte, sırası geldiğinde
yazdırılmaktadır. Aynı anda birden fazla işlemi gerçekleştirmeyi sağlayan işletim sistemleri aslında
kuyruk yapısı kullanarak bunu gerçekleştirmektedir. İşlemcinin aynı anda 1'den fazla işlem yapması
(paralel işlem yapması) mümkün değildir. Bu yüzden, yapılmakta olan her işten küçük bir kısmı
işlemciye gönderilmekte, bu iş kuyruğa eklenmekte, kuyrukta sırası geldiğinde işlem görmekte, bu iş
bitmediyse kalan kısmı benzer bir mantıkla tekrar kuyruğa gönderilmektedir. Bu işlemler çok hızlı
gerçekleştiğinden aynı anda işlem yapılıyormuş gibi algılanır. Ayrıca disk işlemlerinde, bilgisayar
ağlarında da kuyruklardan faydalanılmaktadır.
Kuyruk yapısında kullanılan dizilerin belli bir dizi boyutu kısıtlaması vardır. Bu yüzden dizinin son
elemanı, dizinin ilk elemanı ile bitişikmiş, peş peşeymiş gibi düşünülerek işlem yapılır. Yani diziyi
düz bir masa yerine yuvarlak bir masa gibi düşünmek gerekir.
Kuyruk (queue) yapısında eleman ekleme ve çıkarma işlemlerini gerçekleştirmek için enqueue(ekle)
ve dequeue(çıkar) işlemleri tanımlanır. Yani kuyruk yapısına bir eleman eklemek için enqueue(ekle)
işlemini, çıkarmak için dequeue(çıkar) işlemini gerçekleştirmek gerekir. Bu iki işlemin paralelinde,
kullanılan kuyruğun dolu yada boş olduğu bilgisini verecek full ve empty adında iki ayrı işlemden
faydalanılır, bu işlemlerin tanımlı olması gereklidir. Ayrıca kuyruğun eleman eklemenin ve
çıkarmanın nereden yapılacağını işaretleyen front(ön) ve rear(arka) değişkenlerinden faydalanılır.
2
BTP104-H9-1
3
BIP116-H9-1
BTP102-H9-1
Kuyruk (queue) yapısı bir dizi üzerinde gerçekleştirilir. Kuyruk yapısından bir eleman çıkarmak için
dequeue(çıkar) işlemini gerçekleştirildiğinde ya herbir kuyruk elemanını bir öndeki yere kaydırmak
yada kuyruk önünü (front) işaretleyen değişkeni bir ileriye kaydırmak gerekir. Kuyruktaki herbir
elemanı bir öne kaydırmak yaklaşık kuyruk dizisinin boyutu, O(n) kadar işlem yapılmasına yol açar.
front (kuyruk önü) değişkeninin değerini bir arttırmak ise O(1) zamanı yani sadece 1 işlem
yapılmasına yol açar. Bu yüzden ikinci seçenek (kuyruk önünü (front) işaretleyen değişkeni bir ileri
kaydırmak) kuyruk yapılarında tercih edilir.
Kuyruk (queue) yapısında kullanılan elemanların tipinin bir kısıtlaması yoktur. Programların çoğunda
tamsayılar ve karakterler üzerinde işlem yapıldığından genelde integer veya char tipinde bir dizi
tanımlanarak, kuyruk (queue) tanımlanmış olur.
Bazı kuyruk işlemlerinde çok kısa sürecek işlemleri olanlara öncelik tanınması gibi durumlar da
mevcuttur. Örneğin fotokopi sırasında sadece 1 sayfa fotokopi çektirme işine verilen öncelik,
yazıcılarda da uygulanmaktadır.
Örnek olarak dizi boyutu 5 olan bir kuyruk yapısına sırasıyla,
biçiminde kuyruk yapısında yer alır.
3
BIP116-H9-1
BTP102-H9-1
KUYRUK YAPISININ ALGORİTMİK İNCELENMESİ
Aşağıda kuyruk (queue) yapısı ile ilgili kaba-kod'lar verilmiştir. Bu kodlardan sınavlarda sorumlu
değilsiniz, kendini veri yapılarını uygulama bazında geliştirmek isteyen arkadaşlara yol göstermesi ve
gerekirse ödevlerinize yardımcı olması amacıyla konulmuştur.
4
BIP116-H9-1
BTP102-H9-1
5
Download

h09 - Engin Dutar