Bilgisayar Mühendisliği Bölümü

BIMU2057 Veri Yapıları

Dr. Öğr. Üyesi Nihal ALTUNTAŞ
[Link]@[Link]
Kuyruk (Queue)
• Temel veri yapılarından bir diğeri kuyruktur.
• Yığının aksine, kuyruğa ilk giren eleman kuyruktan ilk çıkar
• Bu özellik FIFO (First In First Out) olarak bilinir.

y = cikar() ekle(x)

10 20 40 60

Dr. Öğretim Üyesi Nihal ALTUNTAŞ – Veri Yapıları 2

Kuyruk (Queue)
• Kuyruğa ekleme ve kuyruktan çıkarma işlemleri farklı uçlardan
yapıldığı için kuyruk yapısının başı ve sonu tutulur.
• Yeni eklenen veriler kuyruğun sonuna eklenir.
• Çıkarma işlemi kuyruğun başından yapılır.

10 20 40 60

bas son

Dr. Öğretim Üyesi Nihal ALTUNTAŞ – Veri Yapıları 3

Kuyruk Uygulama Alanları
• Kuyruk bir bekleme dizisidir. Belirli bir servis için girdilere bekleme
işlemi uygulamak için kullanılır.
• CPU Scheduling: Bilgisayar işlemcisinin tek çekirdeği bir anda sadece tek
bir işlem gerçekleştirebilir. İşlemcinin çalıştıracağı programlar bir kuyrukta
tutulur.
• Farklı hıza sahip sistemlerin iletişiminde arabellek (buffer) olarak
kullanılır.
• Gerçek dünya uygulamaları

Dr. Öğretim Üyesi Nihal ALTUNTAŞ – Veri Yapıları 4

Genel Kuyruk İşlemleri
• Ekleme: Kuyruğun en sonuna yeni bir eleman ekleme işlemidir. Eklenen
eleman kuyrukta en sondaki eleman haline gelir.
ekle(eleman) - enqueue(eleman)

• Çıkarma: Kuyrukta en ön sırada yer alan elemanı, kuyruktan çıkarma

işlemidir. Bu elemanın arkasında bekleyen eleman, kuyrukta en ön
sıraya yerleşir.
eleman = cikar() - dequeue()

• Boş olma durumunu kontrol etme.

bool bosMu() - isEmpty()

Dr. Öğretim Üyesi Nihal ALTUNTAŞ – Veri Yapıları 5

Array ile Kuyruk Kullanımı
• Boyutu sabit olan ve verileri bir array içerisinde tutan yapıya sahip
kuyruktur.
• Temel olarak iki faklı uygulaması yaygındır
• Lineer kuyruk dizisi
• Döngüsel kuyruk dizisi
• Array için ayrılmış olan hafızanın verimli kullanılabilmesini sağlar

Dr. Öğretim Üyesi Nihal ALTUNTAŞ – Veri Yapıları 6

Lineer Kuyruk Dizisi
• Kuyruğun başı olarak her zaman dizinin başı kabul edilir.
• Eklemeler sona yapılır.
• Kuyruğun başından çıkarma işlemi sonrası diğer tüm veriler bir
kaydırılır.
• Dezavantaj: Kuyruk boyu uzadıkça işlem maliyeti artar
0 1 2 3 4 0 1 2 3 4

10 20 40 20 40

bas son bas son

Dr. Öğretim Üyesi Nihal ALTUNTAŞ – Veri Yapıları 7
Döngüsel Kuyruk Dizisi
• Dizi doğrusal değil döngüsel olarak kabul edilir.
• Farklı zamanlarda dizinin farklı bölümlerinde elemanlar
bulunacaktır.
• bas: İlk elemanı gösterir. son
bas
• son: Son elemanı gösterir 1 2
20 40
0 3
0 1 2 3 4 5 6 7 10

10 20 40 4
7

6 5

bas son
Dr. Öğretim Üyesi Nihal ALTUNTAŞ – Veri Yapıları 8
Döngüsel Kuyruk Dizisi Sınır Durumlar
• Kuyrukta tek eleman varsa; • Kuyruktan son eleman çıkarılırsa;
i-1 i i+1 i-1 i i+1

bas son son bas

• Kuyruğun boş olma durumu:

• bas = son + 1

Dr. Öğretim Üyesi Nihal ALTUNTAŞ – Veri Yapıları 9

Döngüsel Kuyruk Dizisi Sınır Durumlar
• Kuyrukta tek boş yer varsa; • Kuyruktaki tek boş yere yeni bir
eleman eklenirse;
1
1 son
X …
… 0 i-1
X X X
0 i-1 son
X X
X
N-1 i
X … X
N-1 i
… X bas
i+1
i+1
bas • Kuyruğun dolu olma durumu:
• bas = son + 1
Dr. Öğretim Üyesi Nihal ALTUNTAŞ – Veri Yapıları 10
Döngüsel Kuyruk Dizisi Sınır Durumlar
• Kuyruğun boş mu yoksa dolu mu olduğunun kontrolü için başka
bir yol bulmak gerekiyor
• Kuyruktaki eleman sayısını içeren bir değişken
• Kuyruk boş → elemanSayisi == 0
• Kuyruk dolu → elemanSayisi == kapasite
• Özel indis değerleri: Boş olma durumunu için işaretçilere özel değer ata.
• İlk durumda kuyruk boş → bas = - 1, son = -1
• Kuyruk tekrar boşalınca ilk durum değerlerini geri ata
• Kuyruk dolu durumu → bas == (son + 1) mod kapasite

Dr. Öğretim Üyesi Nihal ALTUNTAŞ – Veri Yapıları 11

Linked List ile Kuyruk Kullanımı
• Dizi kullanarak gerçeklemenin getirdiği kısıtlamalar, bağlı listeler
kullanılarak ortadan kaldırılabilir.
• Kuyruğun başı listenin ilk elemanı, kuyruğun sonu ise listenin son
elemanı olacak şekilde tasarım yapılır.
• Kuyruğa ekleme işlemi – listenin sonuna bir eleman ekleme
• Kuyruktan çıkarma işlemi – listenin başından bir eleman çıkarma
• bas pointerı kuyruğun ilk düğümüne işaret eder. Çıkarma işlemi
daima bas pointerı ile gösterilen düğümden yapılır.
• son pointerı kuyruğun son düğümüne işaret eder. Ekleme işlemi
daima son pointerı ile gösterilen düğümün arkasına yapılır.
Dr. Öğretim Üyesi Nihal ALTUNTAŞ – Veri Yapıları 12
Referanslar
• Data Structures and Algorithms in C++, Third Edition, Adam
Drozden, 2005
• Introduction to Algorithms, Third Edition, Thomas H. Cormen,
Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, The MIT
Press, 2009
• Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne,
Addison-Wesley Professional, 2011
• Principles of Data Structures Using C and C++, Vinu V Das, New
Age International

Dr. Öğretim Üyesi Nihal ALTUNTAŞ – Veri Yapıları 13