Deque (Double-Ended Queue) — Struktur Data

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

Deque (dibaca "dek", singkatan dari Double-Ended Queue) adalah antrean yang bisa ditambah dan diambil dari dua ujung, depan dan belakang. Jadi satu deque bisa dipakai seperti stack, bisa juga seperti queue. Mirip antrean yang punya pintu di depan dan di belakang: orang bisa masuk atau keluar lewat dua-duanya, tapi gak bisa menyelip di tengah.

🧪 Tebakan cepat: kalau kamu cuma memakai addBack dan removeBack, deque-mu berperilaku seperti stack atau seperti queue? Tebak dulu, jawabannya ada di bagian "Empat operasi di dua ujung".

Empat operasi di dua ujung

Deque punya empat operasi: addFront dan removeFront di depan, addBack dan removeBack di belakang. Dengan array biasa, keempatnya sudah ada. Mulai dari ["B", "C"]:

Langkah Operasi Kode array Hasilnya Isi (depan ke belakang)
1 addFront dq.unshift("A") A masuk di depan A, B, C
2 addBack dq.push("D") D masuk di belakang A, B, C, D
3 removeFront dq.shift() "A" B, C, D
4 removeBack dq.pop() "D" B, C 
const dq = ["B", "C"]; // depan ke belakang

dq.unshift("A");         // addFront: ["A", "B", "C"]
dq.push("D");            // addBack: ["A", "B", "C", "D"]
console.log(dq.shift()); // removeFront: A
console.log(dq.pop());   // removeBack: D
console.log(dq);         // ["B", "C"]

Kalau tambah dan ambil di ujung yang sama (addBack dengan removeBack), yang terakhir masuk keluar pertama: itu stack. Itu jawaban tebakannya. Kalau tambah di belakang dan ambil di depan (addBack dengan removeFront), itu queue. Deque dipakai waktu kamu butuh dua ujung sekaligus, misalnya mengecek palindrom, kata yang sama dibaca dari depan atau belakang seperti "katak": ambil satu huruf dari depan dan satu dari belakang, bandingkan, ulangi.

Semua operasi O(1) dengan head dan tail

Masalahnya, unshift dan shift menggeser semua isi array, jadi O(n): datanya dua kali lipat, kerjanya kira-kira dua kali lipat. Solusinya sama dengan queue: simpan isi di object, dengan penanda head (nomor isi paling depan) dan tail (nomor sesudah isi paling belakang). Bedanya, head boleh turun ke angka minus.

Langkah Kode head tail Isi (nomor: isi)
1 addBack("B") 0 1 0: B
2 addBack("C") 0 2 0: B, 1: C
3 addFront("A") -1 2 -1: A, 0: B, 1: C
4 removeFront() memberi "A" 0 2 0: B, 1: C
5 removeBack() memberi "C" 0 1 0: B 
class Deque {
  constructor() {
    this.items = {};
    this.head = 0; // nomor isi paling depan
    this.tail = 0; // nomor sesudah isi paling belakang
  }

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

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

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

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

Keempat operasi sekarang O(1): tiap operasi cuma mengubah satu kotak dan satu penanda, gak ada yang digeser.

⚠️ Jebakan yang sering ketemu

TL;DR: Deque adalah antrean dua ujung dengan empat operasi: addFront, addBack, removeFront, removeBack. Tambah dan ambil di ujung yang sama berperilaku seperti stack, tambah di belakang dan ambil di depan seperti queue. Dengan array, push dan pop di belakang itu O(1), tapi unshift dan shift di depan O(n). Dengan object plus penanda head dan tail, keempatnya O(1): head boleh minus, jumlah isinya tail - head, dan method remove mengembalikan undefined kalau deque kosong.

Yang akan kamu pelajari