Analisis mendalam pelaksanaan baris gilir dalam js (perkongsian kod)

Dalam artikel sebelumnya "Analisis ringkas tentang masalah cache kemasukan dalam Vue (perkongsian kod) ", saya memperkenalkan anda kepada masalah cache kemasukan dalam Vue. Artikel berikut akan memperkenalkan anda kepada pelaksanaan baris gilir dalam js.

Definisi baris gilir

Baris gilir (Queue) ialah sejenis yang pertama masuk dahulu keluar (First in, first out. Disingkat sebagai FIFO) Himpunan prinsip yang teratur. Perbezaan antara timbunan dan timbunan ialah timbunan masuk dahulu, keluar dahulu, dan baris gilir masuk dahulu, keluar dahulu Timbunan masuk dan keluar pada satu hujung, manakala baris gilir masuk dan keluar di hujung yang satu lagi. Operasi pemadaman timbunan dilakukan di hujung jadual, dan operasi pemadaman baris gilir dilakukan di kepala jadual. Tindanan berjujukan boleh merealisasikan perkongsian ruang berbilang tindanan, tetapi baris gilir tidak boleh. Penyebut biasa ialah hanya sisipan dan pemadaman elemen dibenarkan pada titik akhir. Mod pengurusan tindanan berbilang rantai dan baris gilir berbilang rantai boleh menjadi sama.

Takrif tindanan

JavaScript ialah bahasa satu-utas dan utas utama melaksanakan kod penyegerakan. Apabila fungsi dipanggil, "rekod panggilan", juga dikenali sebagai "bingkai panggilan", dibentuk dalam memori untuk menyimpan maklumat seperti lokasi panggilan dan pembolehubah dalaman. Jika fungsi lain dipanggil dalam fungsi, rekod panggilan lain akan dibentuk di atas rekod panggilan, dan semua rekod panggilan membentuk "timbunan panggilan". (Panggilan ekor, pengoptimuman rekursi ekor)

Takrif timbunan (timbunan)

objek diperuntukkan dalam timbunan, kawasan besar yang tidak teratur dalam ingatan.

Jadi

JS ialah satu utas utama melaksanakan tugasan segerak seperti peristiwa dan operasi I/O akan memasuki baris gilir tugasan selepas pelaksanaan tak segerak mempunyai keputusan, Ia akan berubah kepada keadaan menunggu, membentuk timbunan pelaksanaan pertama masuk dahulu Selepas kod penyegerakan utas utama dilaksanakan, acara akan dibaca daripada "baris gilir tugas" dan panggilan balik acara tidak segerak. tugas akan dilaksanakan. Inilah sebabnya mengapa perintah pelaksanaan adalah, segerak > tak segerak > panggil balik Untuk meletakkannya dengan lebih mudah: selagi utas utama kosong (segerak), ia akan membaca "baris gilir tugas" (tak segerak). JavaScript.

Artikel ini akan melaksanakan baris gilir asas, baris gilir keutamaan dan baris gilir bulat

Baris gilir mesej dan gelung acaraGelung Acara

A JavaScript masa jalan termasuk A baris gilir mesej belum selesai (Tugas tak segerak), (secara dalaman ia adalah tugasan yang tidak memasuki urutan utama tetapi memasuki "baris gilir tugas" (task queue). Contohnya, acara UI, ajax permintaan rangkaian , pemasa setTimeout dan setInterval, dsb. Setiap mesej dikaitkan dengan fungsi ( fungsi panggil balik callback Apabila tindanan kosong, mesej dikeluarkan daripada baris gilir untuk pemprosesan. Proses ini terdiri daripada memanggil fungsi yang dikaitkan dengan mesej (dan dengan itu mencipta bingkai timbunan awal apabila timbunan kosong semula, ini bermakna pemprosesan mesej telah selesai secara berterusan, jadi keseluruhan mekanisme operasi juga dipanggil Gelung Acara (

Gelung Acara

)

Baris Gilir Asas

Kaedah Gilir Asas , termasuk 6 kaedah berikut

① Tambah elemen ke baris gilir (ekor) (enqueue)

② (dari kepala baris gilir) padam elemen (dequeue)

③ Semak elemen di kepala baris gilir (depan)

④ Semak sama ada baris gilir kosong (Kosong)

⑤ Semak panjang baris gilir (saiz)

⑥ Semak baris gilir (cetak )

function Queue() {
  //初始化队列（使用数组实现）
  var items = [];

  //入队
  this.enqueue = function (ele) {
    items.push(ele);
  };

  //出队
  this.dequeue = function () {
    return items.shift();
  };

  //返回首元素
  this.front = function () {
    return items[0];
  };

  //队列是否为空
  this.isEmpty = function () {
    return items.length == 0;
  };

  //清空队列
  this.clear = function () {
    items = [];
  };

  //返回队列长度
  this.size = function () {
    return items.length;
  };

  //查看列队
  this.show = function () {
    return items;
  };
}

var queue = new Queue();
queue.enqueue("hello");
queue.enqueue("world");
queue.enqueue("css");
queue.enqueue("javascript");
queue.enqueue("node.js");
console.log(queue.isEmpty()); // false
console.log(queue.show()); //hello,world,css3,javascript,node.js
console.log(queue.size()); //5
console.log(queue.front()); //hello
console.log(queue.dequeue()); //hello
console.log(queue.show()); //'world', 'css', 'javascript', 'node.js'
console.log(queue.clear());
console.log(queue.size()); //0

Pelaksanaan baris gilir keutamaan

Dalam baris gilir keutamaan, elemen ditambah atau dipadam berdasarkan keutamaan Terdapat dua cara untuk melaksanakan baris gilir keutamaan: ① Tambah dahulu, dequeue seperti biasa. ② Tambah seperti biasa, nyah gilir dahulu

Tambah dahulu, nyah gilir secara normal (gilir keutamaan minimum) contoh (contoh ini berdasarkan pelaksanaan baris gilir dan menambah elemen yang ditambahkan pada baris gilir Tukar daripada data biasa kepada objek ( array), yang mengandungi nilai dan keutamaan elemen yang perlu ditambah pada baris gilir):

function PriorityQueue() {
    //初始化队列（使用数组实现）
    var items = []
    //因为存在优先级，所以插入的列队应该有一个优先级属性
    function queueEle(ele, priority) {
        this.ele = ele
        this.priority = priority
    }
    //入队
    this.enqueue = function (ele, priority) {
        let element = new queueEle(ele, priority)
        //为空直接入队
        if (this.isEmpty()) {
            items.push(element)
        }
        else {
            var qeueued = false; //是否满足优先级要求，并且已经入队
            for (let i = 0; i < this.size(); i++) {
                if (element.priority < items[i].priority) {
                    items.splice(i, 0, element)
                    qeueued = true
                    break;
                }
            }
            //如果不满足要求，没有按要求入队，那么就直接从尾部入队
            if (!qeueued) items.push(element)
        }
    }

    //出队
    this.dequeue = function () {
        return items.shift()
    }

    //返回首元素
    this.front = function () {
        return items[0]
    }

    //队列是否为空
    this.isEmpty = function () {
        return items.length == 0
    }

    //清空队列
    this.clear = function () {
        items = []
    }

    //返回队列长度
    this.size = function () {
        return items.length
    }

    //查看列队
    this.show = function () {
        return items
    }
}

var priorityQueue = new PriorityQueue();
priorityQueue.enqueue(&#39;优先级2-1&#39;, 2);
priorityQueue.enqueue(&#39;优先级1-1&#39;, 1);
priorityQueue.enqueue(&#39;优先级1-2&#39;, 1);
priorityQueue.enqueue(&#39;优先级3-1&#39;, 3);
priorityQueue.enqueue(&#39;优先级2-2&#39;, 2);
priorityQueue.enqueue(&#39;优先级1-3&#39;, 1);
priorityQueue.show(); // 按优先级顺序输出

//输出
[
0:queueEle {ele: "优先级1-1", priority: 1},
1:queueEle {ele: "优先级1-2", priority: 1},
2:queueEle {ele: "优先级1-3", priority: 1},
3:queueEle {ele: "优先级2-1", priority: 2},
4:queueEle {ele: "优先级2-2", priority: 2},
5:queueEle {ele: "优先级3-1", priority: 3}
]

Baris gilir bulat

Anda boleh menggunakan beratur bulat untuk mensimulasikan permainan gendang dan hantaran bunga (masalah cincin Joseph): sekumpulan kanak-kanak duduk dalam bulatan dan lulus n nombor setiap kali Apabila mereka berhenti, kanak-kanak yang memegang bunga di tangannya disingkirkan sehingga ada sahaja seorang kanak-kanak yang tinggal dalam pasukan itu ialah pemenangnya

Gelung baris gilir, pop anak (dari kepala baris gilir) setiap kali, dan kemudian tambahkan kanak-kanak ini ke penghujung baris gilir, gelung n kali, dan timbulkan kepala barisan apabila gelung berhenti (dihapuskan) sehingga hanya tinggal seorang kanak-kanak dalam baris gilir:

Tutorial video JavaScript

Atas ialah kandungan terperinci Analisis mendalam pelaksanaan baris gilir dalam js (perkongsian kod). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!