Deque (Double-Ended Queue) adalah antrian yang bisa menambah dan menghapus elemen dari kedua ujung — depan dan belakang.

Deque menggabungkan kemampuan Stack dan Queue dalam satu struktur.

Operasi utama:

class Deque {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }

  addBack(item) {
    this.items[this.tail] = item;
    this.tail++;
  }

  addFront(item) {
    this.head--;
    this.items[this.head] = item;
  }

  removeFront() {
    if (this.isEmpty()) return undefined;
    const item = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return item;
  }

  removeBack() {
    if (this.isEmpty()) return undefined;
    this.tail--;
    const item = this.items[this.tail];
    delete this.items[this.tail];
    return item;
  }

  isEmpty() {
    return this.tail - this.head === 0;
  }
}

Kegunaan nyata:

• Sliding window — teknik algoritma yang efisien
• Browser history — navigasi maju/mundur
• Palindrome checker — bandingkan dari dua ujung

🎭 Analogi sehari-hari: Deque = pintu masuk DAN pintu keluar di mall yang ada di dua sisi (depan & belakang). Orang bisa masuk dari mana saja, keluar dari mana saja. Lebih fleksibel dari Stack atau Queue yang cuma punya satu pintu.

💡 Kapan Deque > Stack/Queue? Saat butuh dua arah:

• Sliding window maximum — buang dari depan (out-of-window) DAN dari belakang (lebih kecil)
• Palindrome check — bandingkan front vs back, lalu remove dari kedua sisi
• Undo + Redo bareng — Stack undo + Stack redo bisa jadi 1 Deque

⚠️ Jebakan umum:

• Implementasi pakai array biasa = arr.unshift() & arr.shift() itu O(n). Pakai pointer head/tail seperti contoh
• Bingung Stack vs Queue vs Deque: kalau cuma butuh 1 ujung pakai Stack/Queue (lebih simpel)
• Index negative bisa bingung saat debug — head bisa minus karena addFront decrement

🎯 Decision tree:

• Cuma push/pop di 1 ujung → Stack
• Push 1 ujung, pop ujung lain → Queue
• Butuh keduanya → Deque

TL;DR: Deque = Queue dua sisi. Tambah/hapus front & back semuanya O(1). Pakai untuk sliding window, undo+redo, dan algoritma yang butuh akses dua ujung.