Deque Nedir?
Stack tek uçtan çalışır (LIFO), queue iki uçtan çalışır ama ekleme sadece arkadan, çıkarma sadece önden yapılır (FIFO). Deque (okunuşu: "dek") ise her iki uçtan da hem ekleme hem çıkarma yapılmasına izin verir. Bu onu hem stack hem queue olarak kullanılabilen esnek bir yapı yapar.
Deque — Her İki Uçtan Dört Operasyon
insertFront ↓
↑ deleteFront
Ön uçtan: ekleme + silme | Arka uçtan: ekleme + silme → 4 operasyon
Stack gibi kullan
Sadece bir uçtan ekleme + silme yap. Örneğin yalnızca insertFront + deleteFront → LIFO davranışı.
Queue gibi kullan
Bir uçtan ekle, diğer uçtan çıkar. Örneğin insertRear + deleteFront → FIFO davranışı.
Hibrit kullan
Her iki uçtan da özgürce. Palindrom kontrolü, sliding window, work-stealing algoritması gibi senaryolar.
Deque ADT — Arayüz
| Operasyon | Açıklama | Karmaşıklık |
|---|
insertFront(x) | Elemanı kuyruğun önüne ekle | O(1) |
insertRear(x) | Elemanı kuyruğun arkasına ekle | O(1) |
deleteFront() | Öndeki elemanı çıkar ve döndür | O(1) |
deleteRear() | Arkadaki elemanı çıkar ve döndür | O(1) |
getFront() | Öndeki elemana bak (çıkarmadan) | O(1) |
getRear() | Arkadaki elemana bak (çıkarmadan) | O(1) |
isEmpty() / isFull() | Boş/dolu kontrolü | O(1) |
Dairesel Dizi ile Gerçekleme
Deque'yi doğrusal dizi ile gerçeklemek aynı phantom fullness problemine yol açar. Bu yüzden dairesel kuyrukta öğrendiğimiz % MAX tekniğini kullanıyoruz. Tek fark: front artık hem ileri hem geri gidebilir.
Yön formülleri:
• İleri (sağa): (indeks + 1) % MAX — rear ekleme, front silme
• Geri (sola): (indeks - 1 + MAX) % MAX — front ekleme, rear silme
Geri yönde + MAX ekliyoruz çünkü C dilinde negatif mod sonucu vereblir: (0 - 1) % 6 = -1 (hatalı!) ama (0 - 1 + 6) % 6 = 5 (doğru wrap).
Yapı ve Oluşturma
#include <stdio.h>
#define MAX 6
typedef struct {
int items[MAX];
int front;
int rear;
int count;
} Deque;
void dequeOlustur(Deque* d) {
d->front = 0;
d->rear = -1;
d->count = 0;
}
int isEmpty(Deque* d) { return d->count == 0; }
int isFull(Deque* d) { return d->count == MAX; }insertFront — Baştan Ekleme
Yeni elemanı front'un bir soluna ekler. front geri (sola) kayar: front = (front - 1 + MAX) % MAX. Bu, front 0'dayken dizinin sonuna (MAX-1) wrap yapmasını sağlar.
Algoritma
insertFront Adımları:
1. Dolu mu? count == MAX → Overflow.
2. front'u geri al: front = (front - 1 + MAX) % MAX
3. items[front] = yeni değer.
4. İlk eleman ise rear'ı da güncelle: rear = front
5. count++
Görsel — insertFront ile Wrap-Around
front Geri Gidince Sona Sarılır
Mevcut: f=1, r=3, count=3 → [1]=20, [2]=30, [3]=40
① insertFront(10) → f = (1-1+6)%6 = 0
front 1'den 0'a geri gitti — normal sol hareket
② insertFront(5) → f = (0-1+6)%6 = 5 ← WRAP!
✨ front 0'dan 5'e sarıldı! Sıra: 5→10→20→30→40 (f=5 → 0 → 1 → 2 → 3)
insertFront Kodu
void insertFront(Deque* d, int deger) {
if (isFull(d)) {
fprintf(stderr, "Deque Overflow!\n");
return;
}
// İlk eleman → rear'ı da ayarla
if (isEmpty(d)) {
d->front = 0;
d->rear = 0;
} else {
d->front = (d->front - 1 + MAX) % MAX; // geri sar
}
d->items[d->front] = deger;
d->count++;
}insertRear — Sondan Ekleme
Circular queue'daki enqueue ile aynıdır: rear ileri (sağa) kayar. rear = (rear + 1) % MAX.
Algoritma
insertRear Adımları:
1. Dolu mu? count == MAX → Overflow.
2. İlk eleman ise front ve rear'ı 0'a ayarla. Değilse rear'ı ileri al: rear = (rear + 1) % MAX
3. items[rear] = yeni değer.
4. count++
Görsel — insertRear
rear İleri Gidince Başa Sarılır (Circular Queue ile Aynı)
Mevcut: f=3, r=5, count=3
① insertRear(70) → r = (5+1)%6 = 0 ← WRAP!
rear 5'ten 0'a wrap yaptı — sıra: 40→50→60→70
insertRear Kodu
void insertRear(Deque* d, int deger) {
if (isFull(d)) {
fprintf(stderr, "Deque Overflow!\n");
return;
}
if (isEmpty(d)) {
d->front = 0;
d->rear = 0;
} else {
d->rear = (d->rear + 1) % MAX; // ileri sar
}
d->items[d->rear] = deger;
d->count++;
}deleteFront — Baştan Silme
Circular queue'daki dequeue ile aynıdır: öndeki elemanı döndür ve front'u ileri al. front = (front + 1) % MAX.
Algoritma
deleteFront Adımları:
1. Boş mu? count == 0 → Underflow.
2. items[front] değerini kaydet.
3. front'u ileri al: front = (front + 1) % MAX
4. count--
5. Kaydedilen değeri döndür.
Görsel
deleteFront — Öndeki Eleman Çıkar, front İlerler
Mevcut: f=5, r=2, count=4 → [5]=5, [0]=10, [1]=20, [2]=30 (sarılmış)
① deleteFront() → 5 döndü, f = (5+1)%6 = 0 ↻
count: 4→3 | front wrap yaptı (5→0)
deleteFront Kodu
int deleteFront(Deque* d) {
if (isEmpty(d)) {
fprintf(stderr, "Deque Underflow!\n");
return -1;
}
int deger = d->items[d->front];
d->front = (d->front + 1) % MAX; // ileri sar
d->count--;
return deger;
}deleteRear — Sondan Silme
Bu operasyon deque'yi stack'ten ayıran kritik özelliktir. rear geri (sola) kayar: rear = (rear - 1 + MAX) % MAX. Normal kuyrukta sondan silme yoktur — deque bunu mümkün kılar.
Algoritma
deleteRear Adımları:
1. Boş mu? count == 0 → Underflow.
2. items[rear] değerini kaydet.
3. rear'ı geri al: rear = (rear - 1 + MAX) % MAX
4. count--
5. Kaydedilen değeri döndür.
Görsel — deleteRear ile Ters Wrap
rear Geri Gidince Sona Sarılır
Mevcut: f=4, r=1, count=4 → [4]=50, [5]=60, [0]=70, [1]=80
① deleteRear() → 80 döndü, r = (1-1+6)%6 = 0
count: 4→3 | rear 1'den 0'a geri gitti
② deleteRear() → 70 döndü, r = (0-1+6)%6 = 5 ← WRAP!
✨ rear 0'dan 5'e ters sarıldı! Kalan: 50→60
deleteRear Kodu
int deleteRear(Deque* d) {
if (isEmpty(d)) {
fprintf(stderr, "Deque Underflow!\n");
return -1;
}
int deger = d->items[d->rear];
d->rear = (d->rear - 1 + MAX) % MAX; // geri sar
d->count--;
return deger;
}Yardımcı Fonksiyonlar
int getFront(Deque* d) {
if (isEmpty(d)) { fprintf(stderr, "Boş!\n"); return -1; }
return d->items[d->front];
}
int getRear(Deque* d) {
if (isEmpty(d)) { fprintf(stderr, "Boş!\n"); return -1; }
return d->items[d->rear];
}
void dequeYazdir(Deque* d) {
if (isEmpty(d)) { printf(" [Boş]\n"); return; }
printf(" front=[");
int idx = d->front;
for (int i = 0; i < d->count; i++) {
printf("%d%s", d->items[idx],
i < d->count - 1 ? ", " : "");
idx = (idx + 1) % MAX;
}
printf("]=rear (cnt=%d, f=%d, r=%d)\n",
d->count, d->front, d->rear);
}Adım Adım — Tam Senaryo
MAX = 6 olan bir deque'de dört operasyonun hepsini kullanarak wrap-around dahil tam yaşam döngüsü:
Deque — 10 Adımlık Senaryo (MAX=6)
② insertRear(10), insertRear(20), insertRear(30) → f=0, r=2, cnt=3
③ insertFront(5) → f=(0-1+6)%6=5 ↻, cnt=4
Sıra: 5→10→20→30
④ insertFront(1) → f=(5-1+6)%6=4, cnt=5
Sıra: 1→5→10→20→30
⑤ deleteRear() → 30 döndü, r=(2-1+6)%6=1, cnt=4
Sıra: 1→5→10→20
⑥ deleteFront() → 1 döndü, f=(4+1)%6=5, cnt=3
Sıra: 5→10→20
⑦ insertRear(40), insertRear(50), insertRear(60) → r=4, cnt=6 DOLU
count=6=MAX → dolu! Sıra: 5→10→20→40→50→60
Demo Program
int main() {
Deque d;
dequeOlustur(&d);
printf("=== insertRear ===\n");
insertRear(&d, 10); dequeYazdir(&d);
insertRear(&d, 20); dequeYazdir(&d);
insertRear(&d, 30); dequeYazdir(&d);
printf("\n=== insertFront ===\n");
insertFront(&d, 5); dequeYazdir(&d);
insertFront(&d, 1); dequeYazdir(&d);
printf("\nFront=%d Rear=%d Boyut=%d\n",
getFront(&d), getRear(&d), d.count);
printf("\n=== deleteRear ===\n");
printf(" → %d ", deleteRear(&d)); dequeYazdir(&d);
printf("\n=== deleteFront ===\n");
printf(" → %d ", deleteFront(&d)); dequeYazdir(&d);
printf("\n=== Hepsini deleteFront ile boşalt ===\n");
while (!isEmpty(&d))
printf(" → %d\n", deleteFront(&d));
printf("\n=== Underflow testi ===\n");
deleteFront(&d);
deleteRear(&d);
return 0;
}=== insertRear ===
front=[10]=rear (cnt=1, f=0, r=0)
front=[10, 20]=rear (cnt=2, f=0, r=1)
front=[10, 20, 30]=rear (cnt=3, f=0, r=2)
=== insertFront ===
front=[5, 10, 20, 30]=rear (cnt=4, f=5, r=2)
front=[1, 5, 10, 20, 30]=rear (cnt=5, f=4, r=2)
Front=1 Rear=30 Boyut=5
=== deleteRear ===
→ 30 front=[1, 5, 10, 20]=rear (cnt=4, f=4, r=1)
=== deleteFront ===
→ 1 front=[5, 10, 20]=rear (cnt=3, f=5, r=1)
=== Hepsini deleteFront ile boşalt ===
→ 5
→ 10
→ 20
=== Underflow testi ===
Deque Underflow!
Deque Underflow!
Stack vs Queue vs Deque
| Özellik | Stack | Queue | Deque |
|---|
| Prensip | LIFO | FIFO | Her iki uçtan |
| Ekleme | push (top) | enqueue (rear) | insertFront + insertRear |
| Silme | pop (top) | dequeue (front) | deleteFront + deleteRear |
| Operasyon sayısı | 2 (push/pop) | 2 (enqueue/dequeue) | 4 (iki ekleme + iki silme) |
| Uçlar | Tek (top) | İki (front/rear) ama yönlü | İki (front/rear) simetrik |
| Stack olarak? | Doğal | ❌ | ✅ (tek uçtan) |
| Queue olarak? | ❌ | Doğal | ✅ (iki uçtan yönlü) |
| Karmaşıklık | Tüm O(1) | Tüm O(1) | Tüm O(1) |
Karmaşıklık Analizi
| Operasyon | Zaman | Neden? |
|---|
insertFront | O(1) | Mod + atama + count++ |
insertRear | O(1) | Mod + atama + count++ |
deleteFront | O(1) | Okuma + mod + count-- |
deleteRear | O(1) | Okuma + mod + count-- |
getFront / getRear | O(1) | Doğrudan indeks erişimi |
| Bellek | O(n) | MAX boyutlu dizi + 3 int |
Gerçek Dünya Kullanım Alanları
Sliding Window Maximum
Dizi üzerinde sabit boyutlu bir pencere kaydırılırken her pozisyondaki max/min bulma problemi. Deque ile O(n)'de çözülür — yeni eleman arkadan girer, eski eleman önden çıkar, geçersizler arkadan atılır. LeetCode 239 klasiğidir.
Work-Stealing
Paralel programlamada her thread kendi deque'sinin sonundan iş alır (LIFO — cache dostu). Başka thread'ler boştayken diğerlerinin deque'sinin önünden iş çalar (FIFO). Java ForkJoinPool, Go scheduler buna dayanır.
Palindrom Kontrolü
String'i deque'ye koy, her adımda front ve rear'dan birer karakter çıkar, karşılaştır. Eşit değilse palindrom değildir. İki pointer tekniğinin deque versiyonudur.
Tarayıcı Geçmişi
Tarayıcı geri/ileri butonları bir deque ile modellenebilir. Yeni sayfa arkadan eklenir, geri butonuyla arkadan çıkarılıp "ileri" stack'ine atılır. Geçmiş limiti aşılınca en eski (öndeki) kayıt silinir.
Sonuç
Deque, stack ve queue'nun genelleştirilmiş halidir: her iki uçtan ekleme ve silme yapılabilir. Dairesel dizi üzerine inşa edilir ve dört temel operasyonun hepsi O(1)'dir. İki yön formülü (ileri: (i+1)%MAX, geri: (i-1+MAX)%MAX) tüm sarılma senaryolarını kapsar.
Deque sadece teorik bir genelleme değil, pratikte de çok kullanılır. Sliding window problemleri, work-stealing scheduler'ları ve tarayıcı geçmiş yönetimi deque olmadan verimli çalışamaz. C++ STL'de std::deque, Java'da ArrayDeque, Python'da collections.deque standart kütüphanede yer alır.
Bölüm 5.4 özeti: Deque = çift uçlu kuyruk. 4 operasyon: insertFront, insertRear, deleteFront, deleteRear — hepsi O(1). Dairesel dizi + ileri/geri mod formülleri. Stack gibi, queue gibi veya hibrit kullanılabilir. Kuyruk ailesi tamamlandı: basit kuyruk → dairesel kuyruk → öncelik kuyruğu → deque.