Antrean (queue)

Mengambil nilai pertama dari 1000 nilai dalam array JavaScript dengan shift memindahkan 999 nilai lainnya; ring buffer mengerjakan tugas yang sama dalam satu langkah.

Masuk pertama, keluar pertama

Antrean itu seperti barisan di depan kasir toko. Orang bergabung di belakang dan dilayani dari depan, jadi siapa yang datang pertama pergi pertama. Aturannya masuk pertama, keluar pertama (FIFO). Dua operasinya adalah enqueue, yang menambahkan nilai di belakang, dan dequeue, yang mengambil nilai di depan. Dalam catatan 6.006 MIT, antrean adalah antarmuka barisan yang dibatasi pada insert last(x) dan delete first().

Antrean ada di mana pun pekerjaan harus ditangani sesuai urutan kedatangan: dokumen yang menunggu printer, tekanan tombol yang menunggu program, pesan yang menunggu server. Pencarian melebar dari kursus algoritma menyimpan petak-petak yang masih harus dikunjungi dalam antrean, dan karena itulah ia menjelajah berlapis-lapis dengan jarak yang sama.

Cara mudah dan biaya tersembunyinya

Di JavaScript, antrean yang paling jelas adalah array: push untuk enqueue di belakang dan shift untuk dequeue dari depan. Cara itu berjalan, dan untuk antrean pendek tidak masalah. Tetapi perhatikan apa yang dilakukan shift. MDN mengatakan shift "menggeser semua nilai ke kiri sebanyak 1", dan spesifikasi ECMAScript menuliskannya sebagai perulangan yang menyalin elemen k ke posisi k − 1 untuk setiap k. Bagian depan array adalah ujung yang mahal, seperti yang ditunjukkan unit pertama. Dequeue dari antrean berisi n nilai memakan 1 pembacaan ditambah n − 1 pemindahan, jadi antrean berisi 1000 nilai memakan 1000 langkah per dequeue. (Mesin JavaScript mungkin memakai jalan pintas di dalamnya, tetapi spesifikasinya tidak menjanjikan apa pun.)

Kalau kamu melakukan enqueue 5 nilai ke array kosong lalu dequeue kelimanya, enqueue memakan 5 langkah dan dequeue memakan 5 + 4 + 3 + 2 + 1 = 15, total 20. Sebagian besarnya adalah memindahkan nilai yang bahkan tidak sedang diambil.

Jangan pindahkan nilainya, pindahkan bagian depannya

Perbaikannya adalah berhenti memindahkan nilai dan sebagai gantinya mengingat di mana bagian depannya. Simpan indeks bernama head. Dequeue membaca nilai di head dan menambah head dengan 1; tidak ada yang lain yang bergeser. Masalahnya, sel-sel sebelum head jadi terbuang. Ring buffer (buffer melingkar) memakainya kembali: array punya jumlah sel tetap, misalnya 8, dan posisinya melingkar, jadi sel sesudah 7 adalah 0. Simpan head dan size. Enqueue berikutnya masuk ke sel (head + size) mod 8, dan dequeue mengambil sel head lalu memindahkan head ke (head + 1) mod 8. Kedua operasi itu 1 langkah. Harganya adalah kapasitas yang tetap: saat size mencapai 8, antreannya penuh, kecuali kamu menyalin semuanya ke cincin yang lebih besar seperti yang dilakukan array dinamis.

Memuat

Seret untuk memutar. Gulir atau cubit untuk memperbesar.

Antrean berisi empat nilai. Dengan "Array dengan shift", setiap dequeue memindahkan sisa barisan. Ganti jenisnya ke "Ring buffer", maka nilai-nilainya tetap di tempat sementara head dan tail bergerak mengelilingi cincin.

Coba ini di laboratorium: ganti ke ring buffer, lakukan enqueue empat kali untuk mengisi ke-8 sel, lalu enqueue sekali lagi. Laboratorium menolaknya, karena cincin berukuran tetap tidak punya sel kesembilan. Lalu dequeue dua kali dan enqueue lagi: nilai baru masuk ke sel 0, melingkar kembali.

Antrean pada n nilai	Enqueue	Dequeue
Array dengan push dan shift	1 (teramortisasi)	1 pembacaan + (n − 1) pemindahan
Array dengan indeks head	1 (teramortisasi)	1, tetapi sel depan terbuang
Ring buffer berukuran tetap	1, atau penuh	1

Mana yang sebaiknya dipakai? Untuk antrean yang tidak pernah berisi lebih dari beberapa puluh nilai, push dan shift itu singkat dan jelas, dan biaya pemindahannya hampir tidak terasa. Untuk antrean yang dilewati ribuan butir, seperti petak-petak pada pencarian melebar yang besar, indeks head atau ring buffer membuat setiap dequeue tetap satu langkah, dan selisihnya makin besar seiring panjang barisan.

FIFO	Masuk pertama, keluar pertama: nilai keluar sesuai urutan kedatangannya.
Enqueue / dequeue	Tambah di belakang / ambil dari depan.
shift	Mengambil nilai pertama array dan menggeser semua nilai lain satu sel ke kiri.
Ring buffer	Array berukuran tetap yang dipakai melingkar: sel kosong berikutnya adalah (head + size) mod kapasitas.

Antrean mengembalikan nilai dengan urutan apa?
- Masuk pertama, keluar pertama
- Masuk terakhir, keluar pertama
- Yang terbesar dulu
- Urutan acak
Enqueue A, B, C. Dequeue sekali. Enqueue D. Sekarang dequeue sampai kosong. Susun nilai-nilai itu sesuai urutannya.
Dengan push dan shift, berapa langkah yang dibutuhkan satu dequeue pada antrean berisi 4 nilai (1 pembacaan ditambah pemindahan)?
Cara yang sama, antrean berisi 1000 nilai: berapa langkah untuk satu dequeue?
Mulai dari array kosong. Enqueue 5 nilai dengan push, lalu dequeue kelimanya dengan shift. Berapa langkah seluruhnya?
Sebuah ring buffer punya 8 sel (0 sampai 7), head = 6 dan size = 3. Sel mana yang dipakai enqueue berikutnya?
Berapa langkah yang dibutuhkan dequeue dari ring buffer, berapa pun banyak nilai di dalamnya?
Cincin tetap berisi 8 sel memuat 8 nilai. Apa yang terjadi saat enqueue?
- Nilai paling depan ditimpa
- Antreannya penuh dan nilai itu ditolak
- Semua nilai digeser ke kiri
- Nilai-nilainya diurutkan
Pencarian mana dari kursus algoritma yang menyimpan petak-petak yang menunggu dalam antrean?
- Pencarian biner
- Pencarian melebar
- Pencarian mendalam
- Pencarian linear
Dalam istilah MIT 6.006, antrean memakai dua operasi barisan yang mana?
- insert last dan delete last
- insert last dan delete first
- insert first dan delete first
- get at dan set at

Poin penting

Antrean itu masuk pertama, keluar pertama: enqueue di belakang, dequeue dari depan.
shift menggeser setiap nilai yang tersisa, jadi dequeue dari n nilai memakan n langkah.
Indeks head atau ring buffer membuat dequeue menjadi 1 langkah.
Pada cincin berukuran c, sel kosong berikutnya adalah (head + size) mod c.

Sumber kursus ini (11)

MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append)
4 Hashing (chaining, pigeonhole collisions, chain length n/m)
6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
MDN Web Docs, Array.prototype.shift (shifts all values left by 1)
Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
ECMAScript 2025 Language Specification (tc39.es/ecma262)
24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements")
Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
"A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).

Diperiksa: 2026-10-18