Eingehende Analyse der Warteschlangenimplementierung in js (Code-Sharing)

Im vorherigen Artikel „Eine kurze Analyse des Problems des Eintragscaches in Vue (Code-Sharing)“ habe ich Ihnen das Problem des Eintragscaches in Vue vorgestellt. Der folgende Artikel führt Sie in die Implementierung von Warteschlangen in js ein.

Warteschlangendefinition

Warteschlange (Warteschlange) ist eine Art First-In, First-Out (First in, First out) code>. Abgekürzt als <code>FIFO) Prinzip der geordneten Sammlung. Der Unterschied zu einem Stapel besteht darin, dass der Stapel zuerst rein und zuerst raus ist und dass der Stapel an einem Ende ein- und ausgeht, während die Warteschlange an einem Ende ein- und ausgeht. Der Löschvorgang des Stapels wird am Ende der Tabelle ausgeführt, und der Löschvorgang der Warteschlange wird am Kopf der Tabelle ausgeführt. Der sequentielle Stapel kann die gemeinsame Nutzung von Speicherplatz über mehrere Stapel realisieren, die sequentielle Warteschlange jedoch nicht. Der gemeinsame Nenner ist, dass an den Endpunkten nur das Einfügen und Löschen von Elementen erlaubt ist. Die Verwaltungsmodi von Multi-Chain-Stacks und Multi-Chain-Warteschlangen können gleich sein. Queue）是一种遵从先进先出（First in,first out。简称FIFO）原则的有序集合。 它和栈的不同点是栈是先进后出的，队列是先进先出的，栈都是在一端进与出，而队列是在一端进在另一端出。栈的删除操作在表尾进行，队列的删除操作在表头进行。顺序栈能够实现多栈空间共享，而顺序队列不能。 共同点是只允许在端点处插入和删除元素。多链栈和多链队列的管理模式可以相同。

栈（stack）定义

JavaScript是单线程语言，主线程执行同步代码。 函数调用时， 便会在内存形成了一个“调用记录”，又称“调用帧”，保存调用位置和内部变量等信息。如果函数内部还调用了其他函数，那么在调用记录上方又会形成一个调用记录， 所有的调用记录就形成一个“调用栈”。（尾调用、尾递归优化）

堆（heap）定义

对象被分配在一个堆中，一个用以表示一个内存中大的未被组织的区域。

所以

JS是单线程， 主线程执行同步代码， 事件、I/O 操作等异步任务，将会进入任务队列执行，异步执行有结果之后，就会变为等待状态， 形成一个先进先出的执行栈，主线程的同步代码执行完之后，再从”任务队列”中读取事件， 执行事件异步任务的回调。 这就是为什么执行顺序是， 同步 > 异步 > 回调 更简单的说：只要主线程空了（同步），就会去读取”任务队列”（异步），这就是JavaScript的运行机制。

本文将实现 基本队列、优先队列和循环队列

消息队列与事件循环Event Loop

一个JavaScript运行时包含了一个待处理的消息队列（异步任务），（内部是不进入主线程，而进入”任务队列”（task queue）的任务。比如UI事件、ajax网络请求、定时器setTimeout和setInterval等。 每一个消息都与一个函数（回调函数callback

Stack-Definition

JavaScript ist eine Single-Thread-Sprache und der Haupt-Thread führt synchronen Code aus. Beim Aufruf einer Funktion wird im Speicher ein „Aufrufdatensatz“, auch „Aufrufrahmen“ genannt, erstellt, um Informationen wie den Aufrufort und interne Variablen zu speichern. Wenn andere Funktionen innerhalb der Funktion aufgerufen werden, wird über dem Anrufdatensatz ein weiterer Anrufdatensatz erstellt und alle Anrufdatensätze bilden einen „Aufrufstapel“. (Tail Call, Tail Recursion Optimization)

Heap (Heap)-Definition

Objekte werden in einem Heap zugeordnet, einem großen unorganisierten Bereich, der zur Darstellung eines Speichers verwendet wird.

Also

JS ist ein einzelner Thread. Der Hauptthread führt synchrone Aufgaben wie Ereignisse und E/A-Vorgänge zur Ausführung aus. Es wird zu einem First-In-First-Out-Ausführungsstapel im Wartezustand. Nachdem der Synchronisationscode des Hauptthreads ausgeführt wurde, wird das Ereignis aus der „Aufgabenwarteschlange“ gelesen und der Rückruf der asynchronen Ereignisaufgabe ausgeführt. Aus diesem Grund lautet die Ausführungsreihenfolge: synchron > asynchron > Rückruf: Solange der Hauptthread leer ist (synchron), wird die „Aufgabenwarteschlange“ gelesen (asynchron). Betätigungsmechanismus.

In diesem Artikel werden die Basiswarteschlange, die Prioritätswarteschlange und die Umlaufwarteschlange implementiert.

Nachrichtenwarteschlange und Ereignisschleife. Darin befinden sich Aufgaben, die nicht in den Hauptthread gelangen, sondern in die „Aufgabenwarteschlange“ (Aufgabenwarteschlange). Zum Beispiel UI-Ereignisse, ajax Netzwerkanfragen, Timer setTimeout und setInterval usw. Jede Nachricht ist einer Funktion zugeordnet (

callback function

callback Wenn leer, a Die Nachricht wird aus der Warteschlange entfernt und verarbeitet. Dies bedeutet, dass die mit der Nachricht verknüpfte Funktion aufgerufen wird (und somit ein erster Stapelrahmen erstellt wird). ist kontinuierlich, daher wird der gesamte Betriebsmechanismus auch als Ereignisschleife (

Ereignisschleife

) bezeichnet.

Basiswarteschlange

Die grundlegende Warteschlangenmethode umfasst die folgenden 6 Methoden:

① Elemente zur Warteschlange (Ende) hinzufügen (enqueue). )

② (vom Kopf der Warteschlange) Elemente entfernen (aus der Warteschlange entfernen)

③ Überprüfen Sie die Elemente am Kopf der Warteschlange (vorne) ④ Überprüfen Sie, ob die Warteschlange leer ist (isEmpty )

⑤ Sehen Sie sich die Warteschlange an Länge (Größe)

⑥ Anzeigen der Warteschlange (Drucken)

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

Implementierung der Prioritätswarteschlange

🎜In der Prioritätswarteschlange erfolgt das Hinzufügen oder Löschen von Elementen auf zwei Arten : ① Zuerst hinzufügen, normal aus der Warteschlange entfernen; ② Normal hinzufügen, zuerst aus der Warteschlange entfernen 🎜🎜Zuerst hinzufügen, normal aus der Warteschlange entfernen (Warteschlange mit minimaler Priorität) Beispiel (dieses Beispiel basiert auf der Implementierung der Warteschlange und fügt die zur Warteschlange hinzugefügten Elemente hinzu). Daten an einen Objekttyp (Array), der den Wert und die Priorität der Elemente enthält, die zur Warteschlange hinzugefügt werden müssen): Blumen weitergeben (Joseph-Ring-Problem): Eine Gruppe von Kindern sitzt im Kreis und gibt jedes Mal n Zahlen weiter. Das Kind, das beim Anhalten die Blume hält, scheidet aus, bis nur noch ein Kind im Team ist, der Gewinner wird jedes Mal durchlaufen (von der Spitze der Warteschlange) und dann n-mal an das Ende der Schleife hinzugefügt. eliminiert), bis nur noch ein Kind in der Warteschlange ist 🎜

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}
]

🎜 Empfohlenes Lernen: 🎜JavaScript-Video-Tutorial🎜🎜

Das obige ist der detaillierte Inhalt vonEingehende Analyse der Warteschlangenimplementierung in js (Code-Sharing). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!