In-depth analysis of queue implementation in js (code sharing)

In the previous article "A brief analysis of the entry cache problem in Vue (code sharing)", I introduced you to the problem of entry cache in Vue. The following article will introduce you to the implementation of queues in js. Let's take a look.

Queue definition

Queue (Queue) is a first-in-first-out (First in,first out. Referred to as FIFO) An ordered set based on the principle. The difference between it and a stack is that the stack is first in, first out, and the queue is first in, first out. The stack enters and exits at one end, while the queue enters and exits at the other end. The deletion operation of the stack is performed at the end of the table, and the deletion operation of the queue is performed at the head of the table. The sequential stack can realize multi-stack space sharing, but the sequential queue cannot. The common denominator is that only insertion and deletion of elements is allowed at the endpoints. The management modes of multi-chain stacks and multi-chain queues can be the same.

Stack definition

JavaScript is a single-threaded language, and the main thread executes synchronous code. When a function is called, a "call record", also known as a "call frame", is formed in the memory to save information such as the call location and internal variables. If other functions are called within the function, another call record will be formed above the call record, and all call records form a "call stack". (Tail call, tail recursion optimization)

Heap (heap) definition

Objects are allocated in a heap, one used to represent a large unorganized area in memory.

So

JS is a single thread. The main thread executes synchronous code. Asynchronous tasks such as events and I/O operations will enter the task queue for execution. Asynchronous execution has After the result, it will change to a waiting state, forming a first-in-first-out execution stack. After the main thread's synchronization code is executed, the event will be read from the "task queue" and the callback of the event asynchronous task will be executed. This is why the execution order is, Synchronous > Asynchronous > Callback. To put it more simply: as long as the main thread is empty (synchronous), it will read the "task queue" (asynchronous), this is JavaScript operating mechanism.

This article will implement basic queue, priority queue and circular queue

Message Queue and Event LoopEvent Loop

AJavaScript The runtime contains a message queue to be processed (Asynchronous task), (internally it is a task that does not enter the main thread but enters the "task queue" (task queue). For example, UIEvents, ajaxNetwork requests, timers setTimeout and setInterval, etc. Each message is associated with a function (Callback function callback). When the stack is empty, a message is taken from the queue for processing. This processing involves calling the function associated with the message (and thus creating an initial stack Frame). When the stack is empty again, it means that the message processing is over.

This process is cyclic, so the entire operating mechanism is also called Event Loop (Event Loop ).

Basic queue

The basic queue method includes the following 6 methods

① To the queue (tail) Add element (enqueue)

② (from the head of the queue) Delete element (dequeue)

③ Check the element at the head of the queue (front)

④ Check whether the queue is Empty (isEmpty)

⑤ View the length of the queue (size)

⑥ View the queue (print)

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

Implementation of priority queue

In the priority queue, the addition or deletion of elements is based on priority. There are two ways to implement the priority queue: ① add first, dequeue normally; ② add normally, dequeue first

Add first , an example of normal dequeuing (minimum priority queue) (this example is based on the implementation of the queue, and changes the elements added to the queue from ordinary data to an object (array) type. The object contains the value of the element that needs to be added to the queue and Priority):

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

Circular queue

You can use a circular queue to simulate the game of drumming and passing flowers (Joseph ring problem): a group of children sit in a circle and pass each time n number, the child holding the flower in his hand when stopping is eliminated until there is only one child left in the team, the winner.

Loop queue, pop up (from the head of the queue) every time it loops A child, then add this child to the end of the queue, loop n times, and when the loop stops, the child at the head of the queue will pop up (eliminated) until there is only one child left in the queue.

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

/**
 *
 * @param {名单} names
 * @param {指定传递次数} num
 */
function onlyOne(names, num) {
  var queue = new Queue();
  //所有名单入队
  names.forEach((name) => {
    queue.enqueue(name);
  });

  //淘汰的人名
  var loser = "";
  //只要还有一个以上的人在，就一直持续
  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      //把每次出队的人，再次入队 ，这样一共循环了num 次（击鼓传花一共传了num次）
      queue.enqueue(queue.dequeue());
    }
    //到这就次数就用完了，下一个就要出队了
    loser = queue.dequeue();
    console.log(loser + "被淘汰了");
  }
  //到这就剩下一个人了
  return queue.dequeue();
}

var names = ["文科", "张凡", "覃军", "邱秋", "黄景"];
var winner = onlyOne(names, 99);
console.log("金马奖影帝最终获得者是：" + winner);

Recommended learning: JavaScript video tutorial

The above is the detailed content of In-depth analysis of queue implementation in js (code sharing). For more information, please follow other related articles on the PHP Chinese website!