Queue (FIFO) — Struktur Data

Queue adalah struktur data yang mengikuti prinsip FIFO — First In, First Out. Elemen pertama masuk adalah yang pertama keluar. Analogi: Antrian di kasir —…

Queue (antrean) adalah struktur data yang diisi dari belakang dan diambil dari depan. Aturannya disebut FIFO, First In, First Out: yang pertama masuk, pertama keluar. Persis antrean di kasir: yang datang duluan dilayani duluan.

🧪 Tebakan cepat: ada 1.000 orang di antrean yang disimpan di array, lalu orang paling depan dilayani dengan shift(). Berapa orang yang ikut geser: 0, 1, atau 999? Tebak dulu, jawabannya ada di bagian "Kenapa bukan shift()".

Queue dari array biasa

Index 0 adalah bagian depan, akhir array bagian belakang. Masuk antrean disebut enqueue, keluar antrean disebut dequeue. Mulai dari ["A", "B", "C"]:

Langkah Kode Hasilnya Isi queue (depan ke belakang)
1 queue.push("D") D masuk di belakang A, B, C, D
2 queue[0] "A", cuma dilihat A, B, C, D
3 queue.shift() "A" B, C, D
4 queue.shift() "B" C, D 
const queue = ["A", "B", "C"]; // depan ke belakang

queue.push("D");            // enqueue: ["A", "B", "C", "D"]
console.log(queue[0]);      // A (front: cuma dilihat)
console.log(queue.shift()); // A (dequeue)
console.log(queue.shift()); // B
console.log(queue);         // ["C", "D"]

Yang masuk duluan keluar duluan: A, lalu B. Urutannya sama dengan urutan masuk.

Kenapa bukan shift()

Array gak boleh punya celah. Waktu isi di index 0 diambil, semua isi lain maju satu index. Dengan 1.000 orang, 999 orang ikut geser. Itu jawaban tebakannya. Jadi shift() itu O(n): langkahnya ikut bertambah sesuai jumlah isi, datanya dua kali lipat, kerjanya kira-kira dua kali lipat.

Solusinya: jangan geser orangnya, geser penandanya. Simpan isinya di object dengan nomor sebagai kunci, plus dua penanda: head adalah nomor isi paling depan, tail adalah nomor tempat isi berikutnya masuk.

Langkah Kode items head tail
1 enqueue("A") {0: "A"} 0 1
2 enqueue("B") {0: "A", 1: "B"} 0 2
3 enqueue("C") {0: "A", 1: "B", 2: "C"} 0 3
4 dequeue() memberi "A" {1: "B", 2: "C"} 1 3 
class Queue {
  constructor() {
    this.items = {};
    this.head = 0; // nomor isi paling depan
    this.tail = 0; // nomor tempat isi berikutnya
  }

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

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

  front() {
    return this.items[this.head];
  }
}

Enqueue, dequeue, dan front sekarang semuanya O(1): langkahnya tetap berapa pun panjang antreannya, karena cuma satu kotak dan satu penanda yang berubah. Queue dipakai untuk antrean print, pesan yang diproses sesuai urutan datang, dan tugas yang dikerjakan satu per satu.

⚠️ Jebakan yang sering ketemu

TL;DR: Queue itu FIFO: yang pertama masuk, pertama keluar, kayak antrean kasir. Enqueue menaruh di belakang, dequeue mengambil dari depan, dan front melihat yang paling depan tanpa mengambil. Dengan array, shift() menggeser semua isi, jadi O(n). Simpan isinya di object dengan penanda head dan tail: enqueue mengisi tail lalu memajukannya, dequeue mengambil isi di head, menghapusnya, lalu memajukan head. Jumlah isinya tail - head, dan semua operasinya jadi O(1).

Yang akan kamu pelajari