İki Yaklaşım — Bir Arayüz
Stack'te olduğu gibi kuyruk da bir ADT'dir (soyut veri tipi) — hangi operasyonları sunduğunu tanımlar ama nasıl gerçekleneceğini dikte etmez. Aynı enqueue, dequeue, front, isEmpty arayüzü iki farklı şekilde gerçeklenebilir:
Dizi Tabanlı (Circular Array)
Sabit boyutlu dairesel dizi. front ve rear indeksler ile takip.
✓ Cache-friendly, hızlı erişim
✗ Sabit boyut, resize pahalı
Bağlı Liste (Linked List)
Dinamik düğüm zinciri. front ve rear pointer ile takip.
✓ Dinamik boyut, asla overflow yok
✗ Extra bellek (pointer), cache-unfriendly
Aynı Mantıksal Kuyruk — İki Fiziksel Düzen
Aynı FIFO davranışı: enqueue(rear) → dequeue(front)
Gerçekleme 1 — Circular Array Queue
Önceki bölümlerde (5.1–5.2) doğrusal ve dairesel kuyruğu parça parça incelemiştik. Şimdi tüm operasyonları tek bir dosyada, üretim kalitesinde bir implementasyon olarak sunuyoruz. Dairesel dizi + count yaklaşımı kullanılır.
Bellek Düzeni
Circular Array — Struct + Fiziksel Bellek
Tek struct: 3 int + sabit boyutlu dizi → bitişik bellek bloğu
front=2|rear=0|count=5|items:
FIFO sıra: 20→30→40→50→60 (f=2 → 3 → 4 → 5 → 0)
Tam Implementasyon
#include <stdio.h>
#include <stdlib.h>
#define MAX 6
typedef struct {
int items[MAX];
int front;
int rear;
int count;
} ArrayQueue;
/* ── Oluşturma ── */
void aqOlustur(ArrayQueue* q) {
q->front = 0;
q->rear = -1;
q->count = 0;
}
/* ── Durum kontrolleri ── */
int aqIsEmpty(ArrayQueue* q) { return q->count == 0; }
int aqIsFull(ArrayQueue* q) { return q->count == MAX; }
int aqBoyut(ArrayQueue* q) { return q->count; }
/* ── Enqueue — O(1) ── */
void aqEnqueue(ArrayQueue* q, int deger) {
if (aqIsFull(q)) {
fprintf(stderr, "[Array] Overflow!\n");
return;
}
q->rear = (q->rear + 1) % MAX;
q->items[q->rear] = deger;
q->count++;
}
/* ── Dequeue — O(1) ── */
int aqDequeue(ArrayQueue* q) {
if (aqIsEmpty(q)) {
fprintf(stderr, "[Array] Underflow!\n");
return -1;
}
int deger = q->items[q->front];
q->front = (q->front + 1) % MAX;
q->count--;
return deger;
}
/* ── Front / Rear erişimi — O(1) ── */
int aqFront(ArrayQueue* q) {
if (aqIsEmpty(q)) { fprintf(stderr, "Boş!\n"); return -1; }
return q->items[q->front];
}
int aqRear(ArrayQueue* q) {
if (aqIsEmpty(q)) { fprintf(stderr, "Boş!\n"); return -1; }
return q->items[q->rear];
}
/* ── Yazdırma — O(n) ── */
void aqYazdir(ArrayQueue* q) {
if (aqIsEmpty(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 (%d/%d)\n", q->count, MAX);
}Adım Adım — Wrap-Around ile Enqueue/Dequeue
MAX = 6 — Dairesel Kuyruk Yaşam Döngüsü
① enqueue(10,20,30,40) → f=0, r=3, cnt=4
② dequeue()×2 → 10,20 çıktı → f=2, cnt=2
③ enqueue(50,60,70,80) → r: 4→5→0→1 ↻ cnt=6 DOLU
rear wrap yaptı → [0],[1] yeniden kullanıldı!
④ dequeue()×6 → 30,40,50,60,70,80 → f wrap yaptı → cnt=0 BOŞ
FIFO sıra doğru: 30→40→50→60→70→80 ✓
Demo ve Çıktı
int main() {
ArrayQueue q;
aqOlustur(&q);
printf("=== Array Queue Demo ===\n");
for (int i = 1; i <= 4; i++) {
aqEnqueue(&q, i * 10);
aqYazdir(&q);
}
printf("\nDequeue x2:\n");
printf(" → %d\n", aqDequeue(&q));
printf(" → %d\n", aqDequeue(&q));
aqYazdir(&q);
printf("\nEnqueue x4 (wrap):\n");
for (int i = 5; i <= 8; i++) {
aqEnqueue(&q, i * 10);
aqYazdir(&q);
}
printf("\nFront=%d Rear=%d Boyut=%d\n",
aqFront(&q), aqRear(&q), aqBoyut(&q));
return 0;
}=== Array Queue Demo ===
front→[10]←rear (1/6)
front→[10, 20]←rear (2/6)
front→[10, 20, 30]←rear (3/6)
front→[10, 20, 30, 40]←rear (4/6)
Dequeue x2:
→ 10
→ 20
front→[30, 40]←rear (2/6)
Enqueue x4 (wrap):
front→[30, 40, 50]←rear (3/6)
front→[30, 40, 50, 60]←rear (4/6)
front→[30, 40, 50, 60, 70]←rear (5/6)
front→[30, 40, 50, 60, 70, 80]←rear (6/6)
Dizi Tabanlı — Artılar ve Eksiler
✓ Avantajlar
Tüm operasyonlar kesin O(1) — amortize değil, garantili.
Cache-friendly: elemanlar bellekte ardışık, CPU cache satırı boyunca okunur.
Bellek overhead'i sıfır: sadece veri + 3 int.
Implementasyonu basit ve hata yapmak zor.
✗ Dezavantajlar
Sabit boyut: MAX önceden belirlenmeli.
Overflow riski: boyut aşıldığında ya hata ya realloc gerekir.
Resize işlemi O(n): tüm elemanlar yeni diziye kopyalanır.
Kullanılmayan alan israf: MAX=1000 ama sadece 3 eleman varsa 997 hücre boş.
Gerçekleme 2 — Linked List Queue
Bağlı liste kuyruk, her elemanı ayrı bir düğüm (node) olarak heap'te saklar. front pointer ilk düğümü, rear pointer son düğümü gösterir. Enqueue rear'dan yeni düğüm ekler, dequeue front düğümünü serbest bırakır. Boyut sınırı yoktur — bellek yettiği sürece büyür.
Bellek Düzeni
Linked List Queue — Düğüm Zinciri
Her düğüm: data + next pointer (8–16 byte overhead per node)
Neden rear pointer? Tek bağlı listede sondan ekleme normalde O(n)'dir çünkü sona ulaşmak için tüm listeyi gezmek gerekir. rear pointer son düğümü doğrudan göstererek enqueue'yu O(1)'e çeker. front pointer olmadan dequeue zaten O(1) çünkü baştan çıkarma tek pointer güncellemesidir.
Düğüm ve Kuyruk Yapısı
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
typedef struct {
Node* front; // dequeue buradan
Node* rear; // enqueue buradan
int count;
} LinkedQueue;
/* ── Oluşturma ── */
void lqOlustur(LinkedQueue* q) {
q->front = NULL;
q->rear = NULL;
q->count = 0;
}
/* ── Durum kontrolleri ── */
int lqIsEmpty(LinkedQueue* q) { return q->front == NULL; }
int lqBoyut(LinkedQueue* q) { return q->count; }Enqueue — Sondan Ekleme O(1)
Enqueue Adımları:
1. Yeni düğüm oluştur (malloc), data'yı yaz, next = NULL.
2. Kuyruk boşsa → front = rear = yeni düğüm.
3. Değilse → rear->next = yeni düğüm, rear = yeni düğüm.
4. count++.
Enqueue(40) — rear'ın next'ine Bağla + rear'ı Güncelle
Mevcut: front→10→20→30←rear
① Yeni düğüm oluştur → [40|NULL]
rear->next = yeni düğüm (30→40 bağlandı)
② rear = yeni düğüm
rear artık 40'ı gösteriyor ✓ count: 3→4
Dequeue — Baştan Çıkarma O(1)
Dequeue Adımları:
1. Boşsa → Underflow.
2. front düğümünün data'sını kaydet.
3. temp = front, front = front->next.
4. temp'i free et. count--.
5. front NULL olduysa → rear'ı da NULL yap (kuyruk boşaldı).
6. Kaydedilen data'yı döndür.
Dequeue() — front Düğümü Serbest Bırakılır
Mevcut: front→10→20→30→40←rear
① front = front->next, eski front free edilir
Döndürülen: 10 | count: 4→3 | Bellek serbest ✓
Tam Implementasyon
/* ── Yeni düğüm oluştur ── */
Node* yeniDugum(int data) {
Node* n = (Node*)malloc(sizeof(Node));
if (!n) { fprintf(stderr, "Bellek hatası!\n"); exit(1); }
n->data = data;
n->next = NULL;
return n;
}
/* ── Enqueue — O(1) ── */
void lqEnqueue(LinkedQueue* q, int deger) {
Node* n = yeniDugum(deger);
if (lqIsEmpty(q)) {
q->front = n;
q->rear = n;
} else {
q->rear->next = n; // eski rear → yeni düğüm
q->rear = n; // rear güncelle
}
q->count++;
}
/* ── Dequeue — O(1) ── */
int lqDequeue(LinkedQueue* q) {
if (lqIsEmpty(q)) {
fprintf(stderr, "[Linked] Underflow!\n");
return -1;
}
Node* temp = q->front;
int deger = temp->data;
q->front = q->front->next;
if (q->front == NULL) // kuyruk boşaldı
q->rear = NULL;
free(temp);
q->count--;
return deger;
}
/* ── Front / Rear erişimi — O(1) ── */
int lqFront(LinkedQueue* q) {
if (lqIsEmpty(q)) { fprintf(stderr, "Boş!\n"); return -1; }
return q->front->data;
}
int lqRear(LinkedQueue* q) {
if (lqIsEmpty(q)) { fprintf(stderr, "Boş!\n"); return -1; }
return q->rear->data;
}
/* ── Yazdırma — O(n) ── */
void lqYazdir(LinkedQueue* q) {
if (lqIsEmpty(q)) { printf(" [Boş]\n"); return; }
printf(" front→[");
Node* p = q->front;
while (p) {
printf("%d%s", p->data, p->next ? ", " : "");
p = p->next;
}
printf("]←rear (%d eleman)\n", q->count);
}
/* ── Temizleme — tüm düğümleri serbest bırak ── */
void lqTemizle(LinkedQueue* q) {
while (!lqIsEmpty(q))
lqDequeue(q);
}Adım Adım — Enqueue/Dequeue/Son Eleman
Linked List Queue — 6 Adımlık Senaryo
① enqueue(10) → ilk eleman: front = rear = [10]
② enqueue(20), enqueue(30)
③ dequeue() → 10 döndü, free([10])
Bellek geri verildi — dizi versiyonunda bu alan kayıp kalırdı (phantom)
④ enqueue(40), enqueue(50)
⑤ dequeue()×3 → 20, 30, 40
Tek eleman kaldı: front = rear = [50]
⑥ dequeue() → 50 döndü → front = rear = NULL → BOŞ
front → NULL ← rear (count=0)
Tüm düğümler free edildi — bellek sızıntısı yok ✓
Demo ve Çıktı
int main() {
LinkedQueue q;
lqOlustur(&q);
printf("=== Linked List Queue Demo ===\n");
for (int i = 1; i <= 5; i++) {
lqEnqueue(&q, i * 10);
lqYazdir(&q);
}
printf("\nFront=%d Rear=%d Boyut=%d\n",
lqFront(&q), lqRear(&q), lqBoyut(&q));
printf("\nDequeue hepsi:\n");
while (!lqIsEmpty(&q)) {
printf(" → %d ", lqDequeue(&q));
lqYazdir(&q);
}
printf("\nUnderflow testi:\n");
lqDequeue(&q);
return 0;
}=== Linked List Queue Demo ===
front→[10]←rear (1 eleman)
front→[10, 20]←rear (2 eleman)
front→[10, 20, 30]←rear (3 eleman)
front→[10, 20, 30, 40]←rear (4 eleman)
front→[10, 20, 30, 40, 50]←rear (5 eleman)
Front=10 Rear=50 Boyut=5
Dequeue hepsi:
→ 10 front→[20, 30, 40, 50]←rear (4 eleman)
→ 20 front→[30, 40, 50]←rear (3 eleman)
→ 30 front→[40, 50]←rear (2 eleman)
→ 40 front→[50]←rear (1 eleman)
→ 50 [Boş]
Underflow testi:
[Linked] Underflow!
Bağlı Liste — Artılar ve Eksiler
✓ Avantajlar
Dinamik boyut: overflow asla yaşanmaz.
Her enqueue/dequeue tam O(1) — resize yok.
Gerçek bellek kullanımı: sadece gerekli kadar düğüm.
Dequeue edilen düğüm free edilir — bellek geri döner.
✗ Dezavantajlar
Her düğüm extra pointer taşır (8 byte, 64-bit'te).
malloc/free overhead'i: her operasyonda heap çağrısı.
Cache-unfriendly: düğümler bellekte dağınık.
Bellek fragmantasyonu riski (uzun çalışan sistemler).
Random access yok: i. elemana O(n) ile ulaşılır.
Kafa Kafaya Karşılaştırma
| Özellik | Circular Array | Linked List |
|---|
| Enqueue | O(1) | O(1) |
| Dequeue | O(1) | O(1) |
| Front / Rear | O(1) | O(1) |
| Boyut sınırı | Sabit (MAX) | Sınırsız (heap) |
| Overflow | rear = MAX → hata | Yok (bellek bitene kadar) |
| Bellek/eleman | 4 byte (sadece int) | 12–16 byte (int + pointer + padding) |
| Cache performansı | Mükemmel (ardışık bellek) | Zayıf (dağınık düğümler) |
| malloc/free | Yok (stack/static alloc) | Her operasyonda |
| Bellek geri dönüşü | Hayır (sabit dizi) | Evet (free ile) |
| Resize | O(n) — tümünü kopyala | Gerek yok |
| Random access | O(1) — items[i] | O(n) — traverse |
| Implementasyon | Basit (mod aritmetiği) | Orta (pointer yönetimi) |
| Thread-safety | Kolay (lock-free ring buffer) | Daha zor |
Hangisini Seçmeli?
Array Queue kullan:
Maksimum boyut önceden biliniyorsa.
Performans kritikse (gömülü sistem, oyun, ağ).
Bellek overhead'i minimizasyonu gerekiyorsa.
Lock-free/thread-safe kuyruk gerekiyorsa.
Örnekler: ring buffer, OS kernel, real-time audio, network packet buffer.
Linked List Queue kullan:
Boyut önceden bilinemiyorsa veya çok değişkense.
Overflow asla kabul edilemiyorsa.
Enqueue/dequeue paterni düzensizse.
Bellek boyutu dinamik değişmeli (bazen 10, bazen 10.000).
Örnekler: yazıcı kuyruğu, web server request queue, BFS traversal.
Pratikte: Çoğu genel amaçlı kütüphane (Java ArrayDeque, Python collections.deque, C++ std::queue) dizi tabanlı dairesel yapı kullanır. Bağlı liste versiyonu boyutun çok değişken olduğu veya overflow'un kesinlikle kabul edilemediği senaryolarda tercih edilir. Performans açısından array neredeyse her zaman kazanır — cache locality modern CPU'larda belirleyici faktördür.
Sonuç
Kuyruk ADT'si iki temel şekilde gerçeklenebilir: circular array ve linked list. Her ikisi de enqueue ve dequeue operasyonlarını O(1)'de yapar, ancak bellek yönetimi, cache davranışı ve esneklik açısından farklı trade-off'lar sunar. Array versiyonu sabit boyut ve cache-friendly erişim sağlar, linked list versiyonu ise dinamik büyüme ve overflow'suz çalışma garantisi verir.
Stack gerçeklemelerinde olduğu gibi (4.2), aynı soyut arayüzün farklı fiziksel gerçeklemeleri farklı performans profillerine yol açar. Doğru seçim, uygulamanın gereksinimlerine bağlıdır: boyut tahmin edilebiliyorsa array, değilse linked list. Bu bölümle birlikte kuyruk ailesini (basit, dairesel, öncelik, deque) ve gerçeklemelerini (array, linked list) tamamlamış oluyoruz.
Bölüm 5.5 özeti: Aynı Queue ADT → iki implementasyon. Circular Array: sabit boyut, O(1) enqueue/dequeue, cache-friendly, overflow riski. Linked List: dinamik boyut, O(1) enqueue/dequeue, overflow yok, cache-unfriendly, extra bellek. Performans kritik → array. Esneklik kritik → linked list.