Contoh detail dengan gambar dan teks untuk mengimplementasikan antrian di JavaScript

Rekomendasi terkait: tutorial javascript

1. Struktur data antrian

• Antrian merupakan jenis struktur data “first in, first out” (FIFO). Item enqueued pertama (input) adalah item dequeued pertama (output).
• Antrian memiliki 2 petunjuk: kepala dan ekor. Item antrian terlama dalam antrian ada di kepala, dan item antrian terbaru ada di bagian belakang.
• Antriannya seperti mengantri di kereta bawah tanah, penumpang yang dekat pintu berada di barisan terdepan, dan penumpang yang baru masuk antrian berada di barisan paling belakang.

Dari perspektif tingkat tinggi, antrian adalah struktur data yang memungkinkan kita memproses setiap item data sesuai urutan penyimpanannya dalam database.

2. Operasi pada antrian

Antrian mendukung 2 operasi utama: enqueue dan dequeue. Selain itu, Anda mungkin merasa berguna untuk melakukan operasi mengintip dan memanjangkan antrean.

• Operasi enqueue <br/>Operasi enqueue adalah menyisipkan item di akhir antrian, dan item yang disisipkan menjadi akhir antrian.

Operasi enqueue pada gambar di atas memasukkan item 8 ke akhir, dan 8 menjadi akhir antrian.

queue.enqueue(8);

• Operasi dequeue <br/> Operasi dequeue adalah mengekstrak item di awal antrian, dan item berikutnya dalam antrian menjadi item utama.

Pada gambar di atas, operasi dequeue mengembalikan dan menghapus item 7 dari antrian, setelah dequeue, item 2 menjadi item utama yang baru.

queue.dequeue(); // => 7

• operasi inspeksi <br/> Operasi inspeksi membaca awal antrian tanpa mengubah antrian.

Item 7 adalah awal antrian pada gambar di atas, dan operasi inspeksi hanya mengembalikan header (item) 7 tanpa mengubah antrian.

queue.peek(); // => 7

• panjang antrian Operasi panjang menghitung berapa banyak item yang terdapat dalam antrian.

Ada 4 item antrian pada gambar: 4, 6, 2, dan 7. Hasilnya, panjang antrian adalah 4.

queue.length; // => 4

• Kompleksitas Waktu Operasi Antrian Yang penting untuk semua operasi antrian (enqueue, dequeue, view dan length) adalah bahwa semua operasi ini harus dijalankan dalam waktu tetap O(1).

Waktu konstan O(1) berarti berapa pun ukuran antreannya (dapat berisi 10 atau 1 juta item): operasi enqueue, dequeue, peek, dan length harus dilakukan secara bersamaan.

3. Mengimplementasikan Antrian di JavaScript

Mari kita lihat kemungkinan penerapan struktur data antrian dengan tetap mempertahankan persyaratan bahwa semua operasi harus dilakukan dalam waktu konstan O(1).

Antrian kelas {
  konstruktor() {
    this.item = {};
    ini.headIndex = 0;
    ini.tailIndex = 0;
  }

  enqueue(barang) {
    this.item[ini.tailIndex] = item;
    ini.tailIndex++;
  }

  dequeue() {
    const item = ini.item[ini.headIndex];
    hapus this.items[this.headIndex];
    ini.headIndex++;
    barang kembali;
  }

  mengintip() {
    kembalikan ini.item[ini.headIndex];
  }

  dapatkan panjang() {
    kembalikan this.tailIndex - this.headIndex;
  }
}

const antrian = Antrian baru();

antrian.enqueue(7);
antrian.enqueue(2);
antrian.enqueue(6);
antrian.enqueue(4);

antrian.dequeue(); // => 7

antrian.mengintip(); // => 2

queue.length; // => 3

const queue = new Queue() adalah cara membuat instance antrian.

Panggil metode queue.enqueue(7) untuk memasukkan item 7 ke dalam antrian.

queue.dequeue() menghapus item utama dari antrian, sedangkan queue.peek() hanya mengintip dari awal.

Terakhir, queue.length menunjukkan berapa banyak item yang tersisa dalam antrian.

Mengenai implementasinya: Di dalam kelas Queue, objek biasa this.items menyimpan item dalam antrian berdasarkan indeks numerik. Indeks item kepala dilacak oleh this.headIndex, dan indeks item ekor dilacak oleh this.tailIndex.

• Kompleksitas metode antrian

Metode queue(), dequeue(), peek() dan length() dari kelas Queue hanya menggunakan:

akses atribut (seperti this.items[this.headIndex]),

atau melakukan operasi aritmatika (seperti this.headIndex++)

Oleh karena itu, kompleksitas waktu dari metode ini adalah waktu konstan O(1).

4. Ringkasan

Struktur data antrian adalah jenis "masuk pertama, keluar pertama" (FIFO): item paling awal yang dimasukkan dalam antrean adalah item paling awal yang dikeluarkan dari antrean.

Antrian memiliki 2 operasi utama: enqueue dan dequeue. Selain itu, antrian dapat memiliki operasi tambahan seperti tampilan dan panjang.

Semua operasi antrian harus dilakukan O(1) dalam waktu yang konstan.

Rekomendasi terkait: Tutorial pembelajaran JavaScript

Di atas adalah penjelasan detail implementasi antrian di JavaScript beserta contoh dan gambarnya.