Neden Dairesel Kuyruk?
Önceki bölümde doğrusal kuyruğun ciddi bir zayıflığını gördük: dequeue edilen hücreler bir daha kullanılamıyor. rear dizinin sonuna ulaştığında kuyruk "dolu" olarak bildiriliyordu, oysa front'un solundaki hücreler aslında boştu. Buna phantom fullness (hayalet doluluk) demiştik.
Doğrusal Kuyruk — Problem Hatırlatma
3 hücre boş ama rear = MAX-1 → isFull() = true ⚠
Çözüm şaşırtıcı derecede basittir: dizinin sonuna ulaşan pointer başa dönsün. Bu "wrap-around" (sarmal dönüş) mantığı, doğrusal diziyi kavramsal olarak bir halka (ring) gibi kullanmamızı sağlar. Bunu sağlayan tek araç: mod (%) operatörü.
Anahtar Fikir — Mod Aritmetiği
Dairesel kuyruğun tüm sihri tek bir formüle dayanır:
Wrap-Around Formülü
yeniİndeks = (mevcutİndeks + 1) % MAX
MAX = 6 için: 0→1→2→3→4→5→0→1→2→... sonsuz döngü
| mevcutİndeks | (mevcut + 1) | % MAX (6) | Sonuç |
|---|
| 0 | 1 | 1 % 6 | 1 |
| 1 | 2 | 2 % 6 | 2 |
| 4 | 5 | 5 % 6 | 5 |
| 5 | 6 | 6 % 6 | 0 ← wrap! |
İndeks 5'ten sonra 6 olması gerekirken, mod 6 işlemi onu 0'a çevirir. Bu tek satırlık değişiklik, doğrusal kuyruğun tüm sorunlarını ortadan kaldırır. Artık dizinin başındaki boş hücreler yeniden kullanılabilir.
Kavramsal Model — Halka (Ring Buffer)
Doğrusal Dizi → Dairesel Kullanım
Aynı dizi, aynı bellek — fark sadece indeks hesaplama mantığında
Ring buffer: Dairesel kuyruk aslında bir "ring buffer" veya "circular buffer" olarak da bilinir. İşletim sistemlerinde (keyboard buffer, network packet buffer), ses/video streaming'de ve gömülü sistemlerde yaygın kullanılır. Fiziksel yapı doğrusal bir dizidir — dairesellik tamamen mod aritmetiği ile sağlanır.
Yapı ve Oluşturma
Dairesel kuyruğun struct'ı doğrusal kuyrukla neredeyse aynıdır. Tek fark: eleman sayısını (count) ayrı bir değişkende tutmak, boş-dolu ayrımını kolaylaştırır. Bu yaklaşım "count-based" stratejisidir — alternatif olan "bir hücre boş bırak" stratejisini de inceleyeceğiz.
#include <stdio.h>
#define MAX 6
typedef struct {
int items[MAX];
int front; // öndeki elemanın indeksi
int rear; // arkadaki elemanın indeksi
int count; // mevcut eleman sayısı
} CQueue;
/* ── Oluşturma ── */
void cqOlustur(CQueue* q) {
q->front = 0;
q->rear = -1;
q->count = 0;
}
/*
* front = 0 → ilk eleman indeks 0'dan başlar
* rear = -1 → henüz eleman yok (ilk enqueue'da 0 olacak)
* count = 0 → boş-dolu ayrımının anahtarı
*/front = 0 mı, -1 mi? Doğrusal kuyrukta front = -1 ile başlamıştık. Dairesel kuyrukta front = 0 tercih ediyoruz çünkü mod aritmetiği front'un -1 olmasıyla uyumsuz çalışır. Boşluk kontrolü artık front == -1 yerine count == 0 ile yapılır — daha temiz ve hatasız.
Enqueue — Dairesel Ekleme
Doğrusal kuyrukta rear++ yapıyorduk. Dairesel kuyrukta ise rear = (rear + 1) % MAX kullanıyoruz. Bu tek değişiklik, rear dizinin sonundan başa dönmesini sağlar.
Algoritma
Enqueue Adımları:
1. Kuyruk dolu mu? count == MAX → Overflow.
2. rear'ı dairesel olarak ilerlet: rear = (rear + 1) % MAX
3. Yeni elemanı items[rear] pozisyonuna yaz.
4. count'u artır: count++
Wrap-Around Görseli
MAX = 6 — rear Sondan Başa Dönüyor
Mevcut: front=2, rear=4, count=3 — [2]=30, [3]=40, [4]=50
[0] ve [1] daha önce dequeue edilmiş — dairesel kuyrukta yeniden kullanılabilir!
① enqueue(60) → rear = (4+1) % 6 = 5
count = 4 — doğrusal kuyrukta burası "dolu" olurdu!
② enqueue(70) → rear = (5+1) % 6 = 0 ← WRAP!
✨ rear başa döndü! [0] yeniden kullanıldı — phantom fullness yok!
③ enqueue(80) → rear = (0+1) % 6 = 1 → count=6 → DOLU
count = MAX = 6 → gerçekten dolu! Sonraki enqueue → overflow
rear: 4 → 5 →0→ 1 — mod ile sorunsuz wrap-around
Enqueue Kodu
void enqueue(CQueue* q, int deger) {
if (q->count == MAX) {
fprintf(stderr, "Queue Overflow!\n");
return;
}
q->rear = (q->rear + 1) % MAX; // dairesel ilerle
q->items[q->rear] = deger;
q->count++;
}Dequeue — Dairesel Çıkarma
Dequeue'da da aynı prensip uygulanır: front = (front + 1) % MAX. front dizinin sonundan başa döner ve wrap-around tamamlanır.
Algoritma
Dequeue Adımları:
1. Kuyruk boş mu? count == 0 → Underflow.
2. items[front] değerini kaydet.
3. front'u dairesel olarak ilerlet: front = (front + 1) % MAX
4. count'u azalt: count--
5. Kaydedilen değeri döndür.
Dequeue Görseli
Dolu Kuyruktan Çıkarma — front Wrap-Around
Mevcut: f=4, r=3, count=6 (dolu, wrap olmuş)
① dequeue() → 50 döndü, front = (4+1)%6 = 5, count=5
② dequeue() → 60 döndü, front = (5+1)%6 = 0 ← WRAP!, count=4
✨ front da başa döndü! Elemanlar: [0]=70, [1]=80, [2]=90, [3]=100
Dequeue Kodu
int dequeue(CQueue* q) {
if (q->count == 0) {
fprintf(stderr, "Queue Underflow!\n");
return -1;
}
int deger = q->items[q->front];
q->front = (q->front + 1) % MAX; // dairesel ilerle
q->count--;
return deger;
}Doğrusal vs dairesel — kod farkı: Enqueue'da rear++ yerine rear = (rear+1) % MAX, dequeue'da front++ yerine front = (front+1) % MAX. Sadece iki satır değişti, ama phantom fullness tamamen ortadan kalktı. Bu bilgisayar biliminde zarif bir çözümün güzel bir örneğidir.
Boş ve Dolu Kontrolü
Dairesel kuyrukta boş ve dolu ayrımı doğrusal kuyruktan daha karmaşıktır. Çünkü her iki durumda da front ve rear aynı konumda olabilir. Bu sorunu çözmek için iki strateji vardır:
Strateji 1: count Değişkeni ✓
Ayrı bir count değişkeni eleman sayısını tutar. Boş: count == 0. Dolu: count == MAX. Tüm MAX hücre kullanılır. Bu bölümde bu stratejiyi kullanıyoruz.
Strateji 2: Bir Hücre Boş Bırak
count tutulmaz. Dolu koşulu: (rear+1) % MAX == front. Ama en fazla MAX-1 eleman saklanır — bir hücre hep boş kalır. Bazı OS kernel'larında tercih edilir çünkü atomik operasyonlarla thread-safe yapılması daha kolaydır.
Boş vs Dolu — Görsel Karşılaştırma
Boş: count = 0
f=0, r=-1, count=0
Dolu: count = MAX
f=2, r=1, count=6=MAX
count olmadan bu iki durumu ayırt etmek zordur — her ikisinde de front ve rear "yanyana" olabilir
int isEmpty(CQueue* q) { return q->count == 0; }
int isFull(CQueue* q) { return q->count == MAX; }
int boyut(CQueue* q) { return q->count; }
/* ── Öndeki elemana bak ── */
int frontEleman(CQueue* q) {
if (isEmpty(q)) { fprintf(stderr, "Boş!\n"); return -1; }
return q->items[q->front];
}
/* ── Arkadaki elemana bak ── */
int rearEleman(CQueue* q) {
if (isEmpty(q)) { fprintf(stderr, "Boş!\n"); return -1; }
return q->items[q->rear];
}
/* ── Yazdırma (dairesel sırada) ── */
void cqYazdir(CQueue* q) {
if (isEmpty(q)) { printf(" [Boş]\n"); return; }
printf(" front=[");
int idx = q->front;
for (int i = 0; i < q->count; i++) {
printf("%d%s", q->items[idx],
i < q->count - 1 ? ", " : "");
idx = (idx + 1) % MAX;
}
printf("]=rear (boyut=%d, f=%d, r=%d)\n",
q->count, q->front, q->rear);
}cqYazdir dikkat: Dairesel kuyrukta elemanları yazdırırken basit bir for(i=front; i<=rear; i++) döngüsü çalışmaz — çünkü front > rear olabilir (wrap sonrası). Bunun yerine front'tan başlayıp count kadar eleman yazdırıyoruz ve her adımda idx = (idx+1) % MAX ile dairesel ilerliyoruz.
Adım Adım — Tam Senaryo
MAX = 6 olan bir dairesel kuyrukta ekle, çıkar, tekrar ekle ve wrap-around'u canlı takip edelim:
Dairesel Kuyruk — 10 Adımlık Yaşam Döngüsü (MAX=6)
① Boş → f=0, r=-1, count=0
② enqueue(10,20,30,40) → f=0, r=3, count=4
③ dequeue()×2 → 10, 20 çıktı → f=2, r=3, count=2
[0],[1] boşaldı — doğrusal kuyrukta kayıp olurdu, burada yeniden kullanılacak
④ enqueue(50,60,70,80) → r: 4→5→0→1 ↻ count=6 DOLU
✨ rear iki kez wrap yaptı (5→0, 0→1) — [0] ve [1] yeniden dolu!
⑤ enqueue(90) → ⚠ Overflow! count=6=MAX
Bu kez gerçek overflow — tüm 6 hücre gerçekten dolu
⑥ dequeue()×3 → 30, 40, 50 çıktı → f: 2→3→4→5, count=3
front > rear (f=5, r=1) → doğrusal düşüncede kafa karıştırır ama dairesel mantıkta normal: 60→70→80
⑦ enqueue(90) → r = (1+1)%6 = 2, count=4
Sıra: 60 → 70 → 80 → 90 (dairesel okuma: f=5 → 0 → 1 → 2)
⑧ dequeue()×4 → 60, 70, 80, 90 → f: 5→0→1→2→3, count=0 BOŞ
count=0 → boş | front wrap yaptı (5→0) ve devam etti | f=3, r=2
Dizi asla "tükenmiyor" — front ve rear sonsuza kadar döner ↻
Tam Demo Program
int main() {
CQueue q;
cqOlustur(&q);
printf("=== Enqueue 4 eleman ===\n");
for (int i = 1; i <= 4; i++) {
enqueue(&q, i * 10);
cqYazdir(&q);
}
printf("\n=== Dequeue 2 eleman ===\n");
printf(" → %d\n", dequeue(&q));
printf(" → %d\n", dequeue(&q));
cqYazdir(&q);
printf("\n=== Enqueue 4 eleman (wrap olacak) ===\n");
for (int i = 5; i <= 8; i++) {
enqueue(&q, i * 10);
cqYazdir(&q);
}
printf("\n=== Overflow testi ===\n");
enqueue(&q, 999);
printf("\nFront: %d | Rear: %d | Boyut: %d\n",
frontEleman(&q), rearEleman(&q), boyut(&q));
printf("\n=== Hepsini dequeue et ===\n");
while (!isEmpty(&q))
printf(" → %d\n", dequeue(&q));
printf("\n=== Underflow testi ===\n");
dequeue(&q);
return 0;
}=== Enqueue 4 eleman ===
front=[10]=rear (boyut=1, f=0, r=0)
front=[10, 20]=rear (boyut=2, f=0, r=1)
front=[10, 20, 30]=rear (boyut=3, f=0, r=2)
front=[10, 20, 30, 40]=rear (boyut=4, f=0, r=3)
=== Dequeue 2 eleman ===
→ 10
→ 20
front=[30, 40]=rear (boyut=2, f=2, r=3)
=== Enqueue 4 eleman (wrap olacak) ===
front=[30, 40, 50]=rear (boyut=3, f=2, r=4)
front=[30, 40, 50, 60]=rear (boyut=4, f=2, r=5)
front=[30, 40, 50, 60, 70]=rear (boyut=5, f=2, r=0)
front=[30, 40, 50, 60, 70, 80]=rear (boyut=6, f=2, r=1)
=== Overflow testi ===
Queue Overflow!
Front: 30 | Rear: 80 | Boyut: 6
=== Hepsini dequeue et ===
→ 30
→ 40
→ 50
→ 60
→ 70
→ 80
=== Underflow testi ===
Queue Underflow!
Doğrusal vs Dairesel Kuyruk
| Özellik | Doğrusal Kuyruk | Dairesel Kuyruk |
|---|
| Alan kullanımı | Dequeue edilen hücreler kayıp | Tüm hücreler yeniden kullanılır |
| Phantom fullness | Evet — rear sona ulaşınca sahte "dolu" | Yok — mod ile wrap-around |
| Enqueue | rear++ | rear = (rear+1) % MAX |
| Dequeue | front++ | front = (front+1) % MAX |
| Boş kontrolü | front == -1 | count == 0 |
| Dolu kontrolü | rear == MAX-1 | count == MAX |
| Max eleman | MAX (ama pratikte daha az) | MAX (tamamı kullanılır) |
| Kod karmaşıklığı | Basit | Biraz daha karmaşık (mod) |
| Tercih | Sadece eğitim amaçlı | Her zaman bu tercih edilmeli |
Karmaşıklık Analizi
| Operasyon | Zaman | Neden? |
|---|
enqueue | O(1) | Mod + atama + count++ |
dequeue | O(1) | Okuma + mod + count-- |
front / rear | O(1) | Doğrudan indeks erişimi |
isEmpty / isFull | O(1) | Tek karşılaştırma (count) |
| Bellek | O(n) | MAX boyutlu dizi + 3 int (front, rear, count) |
Mod operatörünün maliyeti: % operatörü modern CPU'larda tek bir clock cycle'da hesaplanır. Doğrusal kuyruğa göre eklenen maliyet ihmal edilebilir düzeydedir. Bazı uygulamalarda MAX'ı 2'nin kuvveti (64, 128, 256...) seçerek % MAX yerine & (MAX-1) bitwise AND kullanılır — bu daha da hızlıdır.
Gerçek Dünya Kullanım Alanları
OS Keyboard Buffer
Klavye tuşlarını işletim sistemi bir ring buffer'da saklar. Kullanıcı hızlı yazarken tuşlar kuyruğa girer, OS uygun hızda okur. Buffer doluysa yeni tuşlar kaybolur (overflow beep).
Network Packet Buffer
Ağ kartları gelen paketleri circular buffer'da saklar. Paketler geldiği sırayla (FIFO) işlenir. TCP/IP stack'inin temel bileşenidir.
Audio/Video Streaming
Müzik ve video oynatıcılar, ağdan gelen veriyi ring buffer'a yazar, oynatma birimi buradan okur. Buffer boyutu "buffering" süresini belirler. Spotify, YouTube hep bu yapıyı kullanır.
Üretici-Tüketici (Producer-Consumer)
Birden fazla thread'in aynı anda veri üretip tükettiği senaryolarda bounded buffer olarak circular queue kullanılır. Mutex veya semaphore ile eşzamanlılık sağlanır. Java'da ArrayBlockingQueue tam olarak budur.
Sonuç
Dairesel kuyruk, doğrusal kuyruğun phantom fullness problemini tek bir formülle çözer: (indeks + 1) % MAX. Bu basit mod operatörü, dizinin sonundan başa dönülmesini sağlayarak dequeue edilen hücrelerin yeniden kullanılmasına izin verir. Fiziksel yapı doğrusal bir dizidir ama mantıksal olarak bir halka gibi çalışır.
Pratikte "kuyruk" denildiğinde kastedilen hemen her zaman dairesel kuyruktur. Doğrusal kuyruk yalnızca kavramsal giriş olarak öğretilir — üretim kodunda kullanılmaz. OS kernel'ları, ağ stack'leri, ses/video pipeline'ları ve üretici-tüketici modelleri hep ring buffer kullanır.
Bir sonraki bölümde kuyruk ailesinin bir diğer önemli üyesini inceleyeceğiz: Öncelikli Kuyruk (Priority Queue) — elemanların ekleme sırasıyla değil öncelik değerine göre çıkarıldığı yapı.
Bölüm 5.2 özeti: Dairesel kuyruk = doğrusal kuyruk + mod aritmetiği. Phantom fullness yok, tüm hücreler kullanılır. count ile boş-dolu ayrımı. Tüm operasyonlar O(1). Ring buffer olarak her yerde kullanılır.