Kuyruk (Queue) Nedir?
Kuyruk, stack'in kardeş veri yapısıdır. Stack'in LIFO (Last In, First Out) prensibine karşılık, kuyruk FIFO (First In, First Out) prensibini uygular: ilk eklenen eleman ilk çıkar. Günlük hayattaki market kasası kuyruğu, trafik lambası bekleme sırası veya yazıcı iş kuyruğu bu prensibin doğal örnekleridir.
Kuyruk iki uçlu bir yapıdır: elemanlar arka (rear) uçtan eklenir ve ön (front) uçtan çıkarılır. Stack'te her iki işlem de aynı uçta (top) yapılırken, kuyrukta ekleme ve çıkarma farklı uçlarda gerçekleşir.
FIFO — İlk Giren İlk Çıkar
Ekleme (enqueue) rear'dan → Çıkarma (dequeue) front'tan
Stack (LIFO)
Son giren ilk çıkar. Tek uçlu: push ve pop aynı uçta (top). Tabak yığını gibi.
Queue (FIFO)
İlk giren ilk çıkar. Çift uçlu: enqueue arkadan, dequeue önden. Market kuyruğu gibi.
Queue ADT — Arayüz
Queue soyut veri tipi (ADT) beş temel operasyon tanımlar. Bu operasyonlar implementasyondan (dizi, bağlı liste, circular buffer) bağımsızdır:
| Operasyon | Açıklama | Karmaşıklık |
|---|
enqueue(x) | Elemanı kuyruğun arkasına (rear) ekle | O(1) |
dequeue() | Kuyruğun önündeki (front) elemanı çıkar ve döndür | O(1) |
front() | Öndeki elemana bak (çıkarmadan) — peek gibi | O(1) |
isEmpty() | Kuyruk boş mu? | O(1) |
isFull() | Kuyruk dolu mu? (dizi tabanlıda) | O(1) |
Bellek Düzeni — Doğrusal Dizi
Basit kuyruk, sabit boyutlu bir dizi üzerine inşa edilir. İki indeks kuyruğun durumunu takip eder: front öndeki elemanın indeksi, rear arkadaki elemanın indeksi. Boş kuyrukta her ikisi de -1'dir.
Doğrusal Dizi Tabanlı Kuyruk — Struct Yapısı
front = 0
rear = 3
items[MAX]
4 eleman dolu, 2 boş | Enqueue → rear ilerler | Dequeue → front ilerler
Kuyruk Yapısı ve Oluşturma
#include <stdio.h>
#define MAX 6
typedef struct {
int items[MAX];
int front; // öndeki elemanın indeksi
int rear; // arkadaki elemanın indeksi
} Queue;
/* ── Kuyruk oluşturma ── */
void queueOlustur(Queue* q) {
q->front = -1;
q->rear = -1;
}
/*
* front = -1, rear = -1 → kuyruk boş
* İlk enqueue'da her ikisi de 0 olur.
* front her zaman rear'dan küçük veya eşittir.
*/Neden front = -1? Stack'teki top = -1 mantığıyla aynıdır. -1 değeri "henüz hiçbir eleman yok" anlamına gelir. İlk enqueue'da front ve rear birlikte 0'a çekilir. Bazı implementasyonlar front = 0, rear = -1 ile başlar — davranış aynıdır, sadece kontrol koşulları değişir.
Enqueue — Kuyruğa Ekleme
Enqueue, yeni elemanı kuyruğun arkasına (rear) ekler. rear indeksini bir artırır ve yeni elemanı o pozisyona yazar. Kuyruk doluysa overflow hatası verir.
Algoritma
Enqueue Adımları:
1. Kuyruk dolu mu kontrol et (rear == MAX - 1). Doluysa → Overflow.
2. Kuyruk boşsa (front == -1) → front'u 0 yap (ilk eleman).
3. rear'ı bir artır: rear++
4. Yeni elemanı items[rear] pozisyonuna yaz.
Enqueue Görseli
Boş Kuyruğa Üç Eleman Eklenmesi
① Boş kuyruk — front = -1, rear = -1
② enqueue(10) → front = 0, rear = 0
İlk eleman: front ve rear aynı hücreyi gösteriyor
Her enqueue'da rear bir sağa kayar → O(1)
Enqueue Kodu
void enqueue(Queue* q, int deger) {
// Dolu mu?
if (q->rear == MAX - 1) {
fprintf(stderr, "Queue Overflow!\n");
return;
}
// İlk eleman → front'u başlat
if (q->front == -1)
q->front = 0;
// rear'ı ilerlet ve elemanı yaz
q->rear++;
q->items[q->rear] = deger;
}Dequeue — Kuyruktan Çıkarma
Dequeue, kuyruğun önündeki (front) elemanı çıkarır ve döndürür. front indeksini bir artırır. Kuyruk boşsa underflow hatası verir. Eğer son eleman da çıkarılıyorsa (front > rear), front ve rear sıfırlanır.
Algoritma
Dequeue Adımları:
1. Kuyruk boş mu kontrol et (front == -1). Boşsa → Underflow.
2. items[front] değerini kaydet.
3. Eğer front == rear ise → son eleman çıkıyor, ikisini de -1 yap (kuyruk boşaldı).
4. Değilse → front'u bir artır: front++
5. Kaydedilen değeri döndür.
Dequeue Görseli
Kuyruktan İki Eleman Çıkarılması
Mevcut: front = 0, rear = 2 → [10, 20, 30]
① dequeue() → 10 döndü, front = 1
[0] artık kuyruk dışı ama bellekte duruyor (gri)
② dequeue() → 20 döndü, front = 2
front = rear = 2 → kuyrukta tek eleman kaldı (30)
Her dequeue'da front bir sağa kayar → O(1)
Kayıp alan problemi: Dikkat edin: [0] ve [1] hücreleri dequeue sonrası kullanılamaz hale geldi. rear = 5'e ulaştığında kuyruk "dolu" bildirilecek, oysa [0] ve [1] aslında boştur. Bu doğrusal kuyruğun en büyük zayıflığıdır — bir sonraki bölümde (5.2 Circular Queue) çözülecek.
Dequeue Kodu
int dequeue(Queue* q) {
// Boş mu?
if (q->front == -1) {
fprintf(stderr, "Queue Underflow!\n");
return -1;
}
int deger = q->items[q->front];
// Son eleman mıydı?
if (q->front == q->rear) {
// Kuyruk boşaldı → sıfırla
q->front = -1;
q->rear = -1;
} else {
q->front++;
}
return deger;
}Son eleman kontrolü: front == rear olduğunda kuyrukta tek eleman kalmıştır. Bu elemanı da çıkardığımızda front ve rear'ı -1'e sıfırlıyoruz. Bunu yapmazsak front > rear olur ve isEmpty kontrolü karışır. Sıfırlama aynı zamanda dizinin başından yeniden kullanılmasına izin verir — en azından kuyruk tamamen boşalana kadar.
Front ve Rear Erişimi
Stack'teki peek gibi, kuyrukta da elemanı çıkarmadan ön veya arka elemana bakabilmek isteyebiliriz. front() kuyruğun önündeki elemanı, rear() ise arkadaki elemanı döndürür — her ikisi de O(1)'dir.
/* ── Öndeki elemana bak ── */
int frontEleman(Queue* q) {
if (q->front == -1) {
fprintf(stderr, "Kuyruk boş!\n");
return -1;
}
return q->items[q->front];
}
/* ── Arkadaki elemana bak ── */
int rearEleman(Queue* q) {
if (q->rear == -1) {
fprintf(stderr, "Kuyruk boş!\n");
return -1;
}
return q->items[q->rear];
}isEmpty ve isFull Kontrolü
Kuyruk Durumları
Dolu (full)
rear = MAX - 1
Tek eleman
front = rear = 1
/* ── Boş mu? ── */
int isEmpty(Queue* q) {
return q->front == -1;
}
/* ── Dolu mu? ── */
int isFull(Queue* q) {
return q->rear == MAX - 1;
}
/* ── Eleman sayısı ── */
int boyut(Queue* q) {
if (isEmpty(q)) return 0;
return q->rear - q->front + 1;
}
/* ── Yazdırma ── */
void queueYazdir(Queue* q) {
if (isEmpty(q)) {
printf(" [Boş]\n");
return;
}
printf(" front=[");
for (int i = q->front; i <= q->rear; i++)
printf("%d%s", q->items[i], i < q->rear ? ", " : "");
printf("]=rear (boyut=%d)\n", boyut(q));
}Adım Adım — Tam Senaryo
MAX = 6 olan bir kuyrukta enqueue ve dequeue işlemlerini birlikte takip edelim. Bu görsel, kuyruğun yaşam döngüsünü ve doğrusal yapının sınırlarını net bir şekilde ortaya koyar.
MAX = 6 — Enqueue + Dequeue + Overflow Senaryosu
① Boş → front = -1, rear = -1
② enqueue(10), enqueue(20), enqueue(30) → f=0, r=2
③ dequeue() → 10 döndü, f=1
[0] artık kullanılamaz — kayıp alan!
④ enqueue(40), enqueue(50), enqueue(60) → f=1, r=5
rear = MAX-1 = 5 → isFull() = true
⑤ enqueue(70) → ⚠ OVERFLOW!
⛔ rear = 5 = MAX-1 → kuyruk "dolu" ama [0] boş! Phantom Fullness!
⑥ dequeue() → 20, dequeue() → 30 → f=3
[0], [1], [2] hepsi boş ama kullanılamıyor — 3 hücre israf!
⑦ dequeue()×3 → 40, 50, 60 → kuyruk tamamen boşaldı → f=-1, r=-1
Tamamen boşalınca front = rear = -1 → dizi baştan kullanılabilir
Tam Demo Program
int main() {
Queue q;
queueOlustur(&q);
printf("=== Enqueue ===\n");
for (int i = 1; i <= 7; i++) { // 7. → overflow
printf(" enqueue(%d): ", i * 10);
enqueue(&q, i * 10);
queueYazdir(&q);
}
printf("\nFront: %d\n", frontEleman(&q));
printf("Rear : %d\n", rearEleman(&q));
printf("Boyut: %d\n", boyut(&q));
printf("\n=== Dequeue ===\n");
while (!isEmpty(&q)) {
printf(" dequeue() → %d ", dequeue(&q));
queueYazdir(&q);
}
printf("\nBoş mu: %d\n", isEmpty(&q));
dequeue(&q); // underflow testi
return 0;
}=== Enqueue ===
enqueue(10): front=[10]=rear (boyut=1)
enqueue(20): front=[10, 20]=rear (boyut=2)
enqueue(30): front=[10, 20, 30]=rear (boyut=3)
enqueue(40): front=[10, 20, 30, 40]=rear (boyut=4)
enqueue(50): front=[10, 20, 30, 40, 50]=rear (boyut=5)
enqueue(60): front=[10, 20, 30, 40, 50, 60]=rear (boyut=6)
enqueue(70): Queue Overflow!
front=[10, 20, 30, 40, 50, 60]=rear (boyut=6)
Front: 10
Rear : 60
Boyut: 6
=== Dequeue ===
dequeue() → 10 front=[20, 30, 40, 50, 60]=rear (boyut=5)
dequeue() → 20 front=[30, 40, 50, 60]=rear (boyut=4)
dequeue() → 30 front=[40, 50, 60]=rear (boyut=3)
dequeue() → 40 front=[50, 60]=rear (boyut=2)
dequeue() → 50 front=[60]=rear (boyut=1)
dequeue() → 60 [Boş]
Boş mu: 1
Queue Underflow!
Doğrusal Kuyruğun Zayıflığı — Phantom Fullness
Doğrusal kuyruk bir tasarım hatası taşır: dequeue edilen hücreler bir daha kullanılamaz. rear dizinin sonuna (MAX-1) ulaştığında kuyruk "dolu" olarak bildirilir, oysa front'un solundaki hücreler aslında boştur. Buna phantom fullness (hayalet doluluk) denir.
Phantom Fullness — Dolu Değil Ama Overflow!
3 hücre boş ama rear = MAX-1 → isFull() = true → enqueue reddedilir!
Gerçek doluluk: 3/6 = %50 | Algılanan doluluk: %100
Problem
Doğrusal dizide front sağa kaydıkça sol tarafta boş hücreler birikir. rear sona ulaştığında bu hücreler kullanılamaz. Her dequeue kayıp alan üretir.
Çözüm → Circular Queue
Dizinin sonuna ulaşan rear, mod işlemiyle başa döner: rear = (rear + 1) % MAX. Bu şekilde dequeue edilen hücreler yeniden kullanılır. Bir sonraki bölümün (5.2) konusu.
Kaydırma çözümü neden kötü? "Her dequeue'dan sonra tüm elemanları bir sola kaydır" diye düşünülebilir ama bu O(n) maliyetli bir işlemdir ve O(1) dequeue avantajını yok eder. 10.000 elemanlı bir kuyrukta her dequeue'da 9.999 eleman kopyalamak pratikte kabul edilemez. Circular queue aynı problemi O(1) ile çözer.
Karmaşıklık Analizi
| Operasyon | Zaman | Neden? |
|---|
enqueue | O(1) | rear++ ve tek atama |
dequeue | O(1) | front++ ve tek okuma |
front / rear | O(1) | Doğrudan indeks erişimi |
isEmpty / isFull | O(1) | Tek karşılaştırma |
boyut | O(1) | rear - front + 1 |
| Bellek | O(n) | MAX boyutlu sabit dizi |
Stack vs Queue — Hızlı Karşılaştırma
| Özellik | Stack | Queue |
|---|
| Prensip | LIFO — Son giren ilk çıkar | FIFO — İlk giren ilk çıkar |
| Uçlar | Tek uç (top) | İki uç (front + rear) |
| Ekleme | push → top'a | enqueue → rear'a |
| Çıkarma | pop → top'tan | dequeue → front'tan |
| Bakma | peek → top | front() → front |
| Kullanım | Undo, parantez, DFS, recursion | BFS, yazıcı kuyruğu, scheduling |
| Benzetme | Tabak yığını | Market kasası sırası |
Gerçek Dünya Kullanım Alanları
İşletim Sistemi
CPU scheduling: hazır süreçler kuyruğa alınır, FIFO sırasıyla işlenir. Disk I/O istekleri de kuyrukta bekler. Her modern OS bu temel yapıyı kullanır.
Yazıcı Kuyruğu
Birden fazla kullanıcı aynı yazıcıya iş gönderdiğinde ilk gönderen ilk basılır. Print spooler tam bir FIFO uygulamasıdır.
BFS (Genişlik Öncelikli Arama)
Graf ve ağaç traversal'da BFS bir kuyruk kullanır: bir düğümün tüm komşuları kuyruğa eklenir, sonra sırayla ziyaret edilir. GPS navigasyon ve sosyal ağ "arkadaş önerisi" bu algoritmaya dayanır.
Mesaj Kuyruğu
RabbitMQ, Apache Kafka gibi mesaj kuyruğu sistemleri üretici-tüketici modeliyle çalışır: üretici mesaj ekler, tüketici FIFO sırasıyla işler. Mikroservis mimarisinin temel bileşenidir.
Sonuç
Basit kuyruk (simple queue), FIFO prensibini en yalın biçimde uygular. Enqueue rear'dan, dequeue front'tan yapılır ve her iki operasyon O(1) karmaşıklığındadır. Dizi tabanlı implementasyonu anlaşılması kolaydır ancak ciddi bir zayıflık taşır: dequeue edilen hücreler yeniden kullanılamaz (phantom fullness). Bu problem pratikte doğrusal kuyruğu yetersiz kılar.
Bir sonraki bölümde bu problemi çözen dairesel kuyruk (circular queue) yapısını inceleyeceğiz. Dairesel kuyrukta dizinin sonuna ulaşan rear başa döner ve boş hücreleri tekrar kullanır — aynı bellek alanıyla çok daha verimli bir kuyruk elde edilir.
Bölüm 5.1 özeti: Queue = FIFO. Enqueue arkadan, dequeue önden. front ve rear iki indeks ile takip edilir. Tüm operasyonlar O(1). Zayıflık: doğrusal dizide phantom fullness → çözüm: circular queue (5.2).