Ilustrasi terperinci dan contoh pelaksanaan baris gilir dalam JavaScript

Artikel ini membawa anda pengetahuan yang berkaitan tentang javascript terutamanya isu yang berkaitan dengan pelaksanaan baris gilir dalam JavaScript, menerangkan struktur data baris gilir, operasinya dan menunjukkan pelaksanaan baris gilir dalam JavaScript ia membantu semua orang.

Cadangan berkaitan: Tutorial javascript

1. Struktur data baris gilir

• Baris gilir Merupakan jenis struktur data "masuk dahulu, keluar dahulu" (FIFO). Item yang di-queued pertama (input) ialah yang pertama di-queued (output).
• Barisan mempunyai 2 penunjuk: kepala dan ekor. Item baris gilir tertua dalam baris gilir berada di kepala, dan item baris gilir terbaharu berada di ekor.
• Barisan seperti beratur di kereta bawah tanah Penumpang berhampiran pintu berada di kepala barisan, dan penumpang yang baru masuk barisan berada di belakang barisan.

Dari perspektif peringkat tinggi, baris gilir ialah struktur data yang membolehkan kami memproses setiap item data mengikut turutan dalam susunan ia disimpan .

2. Operasi pada baris gilir

Baris gilir menyokong 2 operasi utama: baris gilir dan dequeue. Selain itu, anda mungkin mendapati ia berguna untuk melakukan operasi mengintip dan panjang pada baris gilir.

• Operasi enqueue
  Operasi enqueue adalah untuk memasukkan item pada penghujung baris gilir, dan item yang dimasukkan menjadi penghujung baris gilir.

Operasi baris gilir dalam rajah di atas memasukkan item 8 ke ekor, dan 8 menjadi ekor baris gilir.

queue.enqueue(8);

• Operasi dequeue
  Operasi dequeue adalah untuk mengekstrak item pada permulaan baris gilir, dan item seterusnya dalam baris gilir menjadi barang kepala.

Dalam gambar di atas, operasi dequeue kembali dan mengeluarkan item 7 daripada barisan Selepas nyah gilir, item 2 menjadi item kepala yang baharu.

queue.dequeue(); // => 7

• Operasi pemeriksaan
  Operasi pemeriksaan membaca permulaan baris gilir tanpa mengubah baris gilir.

Item 7 ialah permulaan baris gilir dalam gambar di atas, dan operasi pemeriksaan hanya mengembalikan pengepala (item) 7 tanpa mengubah suai baris gilir.

queue.peek(); // => 7

• Panjang Giliran
  Operasi panjang mengira berapa banyak item yang terkandung dalam baris gilir.

Terdapat 4 item dalam baris gilir dalam gambar: 4, 6, 2, dan 7. Akibatnya, panjang baris gilir ialah 4.

queue.length; // => 4

• Kerumitan Masa Operasi Baris
  Untuk semua operasi baris gilir (enqueue, dequeue, view dan length) adalah penting bahawa semua operasi ini mesti dilakukan dalam masa yang tetap Pelaksanaan ialah O(1).

Masa malar O(1) bermakna tidak kira saiz baris gilir (ia boleh mempunyai 10 atau 1 juta item): operasi enqueue, dequeue, peek dan panjang semuanya mesti dilakukan serentak.

3. Melaksanakan Baris Gilir dalam JavaScript

Mari kita lihat kemungkinan pelaksanaan struktur data baris gilir sambil mengekalkan keperluan bahawa semua operasi mesti dilakukan dalam masa tetap O(1).

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }

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

  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }

  peek() {
    return this.items[this.headIndex];
  }

  get length() {
    return this.tailIndex - this.headIndex;
  }
}

const queue = new Queue();

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

queue.dequeue(); // => 7

queue.peek();    // => 2

queue.length;    // => 3

const queue = new Queue() ialah contoh cara membuat baris gilir.

Panggil kaedah queue.enqueue(7) untuk meletakkan item 7 ke dalam baris gilir.

queue.dequeue() mengeluarkan item kepala daripada baris gilir, manakala queue.peek() hanya menyemaknya dari awal.

Akhir sekali, queue.length menunjukkan bilangan item yang tinggal dalam baris gilir.

Mengenai pelaksanaan: Di dalam kelas Queue, objek biasa this.items memegang item dalam baris gilir mengikut indeks berangka. Indeks item kepala dijejaki oleh this.headIndex dan indeks item ekor dijejaki oleh this.tailIndex.

• Kerumitan Kaedah Gilir

Kaedah baris gilir(), dequeue(), mengintip() dan panjang() baris Gilir kelas hanya digunakan Jadi:

属性访问（例如this.items[this.headIndex]），

或执行算术操作（例如this.headIndex++）

Oleh itu, kerumitan masa kaedah ini ialah masa malar O(1).

4. Ringkasan

Struktur data baris gilir ialah jenis "masuk dahulu, keluar dahulu" (FIFO): item terawal yang dimasukkan ke dalam baris gilir ialah item terawal yang dinyah gilir.

Barisan mempunyai 2 operasi utama: baris gilir dan dequeue. Selain itu, baris gilir boleh mempunyai operasi tambahan seperti pandangan dan panjang.

Semua operasi baris gilir mesti melaksanakan O(1) dalam masa yang tetap.

Cadangan berkaitan: Tutorial pembelajaran javascript

Atas ialah kandungan terperinci Ilustrasi terperinci dan contoh pelaksanaan baris gilir dalam JavaScript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!