js의 대기열 구현에 대한 심층 분석(코드 공유)

이전 글 "Vue의 엔트리 캐시 문제에 대한 간략한 분석(코드 공유)"에서 Vue의 엔트리 캐시 문제에 대해 소개해드렸습니다. 다음 기사에서는 js의 대기열 구현을 소개합니다.

큐 정의

큐(큐)는 일종의 선입선출(선입선출, 선출)입니다. code>. FIFO로 축약됨) 원칙적으로 정렬된 컬렉션입니다. 스택과 차이점은 스택은 선입선출이고, 큐는 선입선출이라는 점입니다. 스택은 한쪽 끝에서 들어가고 나가는 반면, 큐는 한쪽 끝에서 들어가고 나옵니다. 스택의 삭제 작업은 테이블 끝에서 수행되고, 큐의 삭제 작업은 테이블의 헤드에서 수행됩니다. 순차 스택은 다중 스택 공간 공유를 실현할 수 있지만 순차 큐는 그렇지 않습니다. 공통분모는 끝점에서는 요소의 삽입과 삭제만 허용된다는 것입니다. 멀티체인 스택과 멀티체인 큐의 관리 모드는 동일할 수 있습니다. Queue）是一种遵从先进先出（First in,first out。简称FIFO）原则的有序集合。 它和栈的不同点是栈是先进后出的，队列是先进先出的，栈都是在一端进与出，而队列是在一端进在另一端出。栈的删除操作在表尾进行，队列的删除操作在表头进行。顺序栈能够实现多栈空间共享，而顺序队列不能。 共同点是只允许在端点处插入和删除元素。多链栈和多链队列的管理模式可以相同。

栈（stack）定义

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

堆（heap）定义

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

所以

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

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

消息队列与事件循环Event Loop

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

스택 정의

JavaScript는 단일 스레드 언어이며, 메인 스레드는 동기 코드를 실행합니다. 함수가 호출되면 호출 위치, 내부 변수 등의 정보를 저장하기 위해 메모리에 '콜 프레임'이라고도 불리는 '호출 기록'이 생성된다. 함수 내에서 다른 함수가 호출되면 호출 기록 위에 또 다른 호출 기록이 형성되고, 모든 호출 기록은 "호출 스택"을 형성합니다. (테일 호출, 테일 재귀 최적화)

힙(힙) 정의

객체는 메모리를 나타내는 데 사용되는 조직화되지 않은 대규모 영역인 힙에 할당됩니다.

So

JS는 단일 스레드입니다. 메인 스레드는 동기 코드를 실행하며, 비동기 실행 결과가 나온 후 실행을 위해 작업 대기열에 들어갑니다. 대기 상태는 선입선출 실행 스택을 형성합니다. 메인 스레드의 동기화 코드가 실행된 후 "작업 대기열"에서 이벤트를 읽고 이벤트 비동기 작업의 콜백이 실행됩니다. 이것이 실행 순서가 동기>비동기>콜백인 이유입니다. 더 간단하게 말하면 메인 스레드가 비어 있는 한(동기) "작업 대기열"(비동기)을 읽습니다. 작동 메커니즘.

이 문서에서는 기본 대기열, 우선 순위 대기열 및 순환 대기열을 구현합니다.

메시지 대기열 및 이벤트 루프

이벤트 루프

A JavaScript 런타임에는 보류 중인 메시지 대기열(

비동기 작업

)이 포함되어 있습니다. ( 내부에는 메인 스레드에 들어가지 않고 "작업 대기열"(작업 대기열)에 들어가는 작업이 있습니다. 예를 들어 UI 이벤트, ajax 네트워크 요청, 타이머 setTimeout 및 setInterval 등. 각 메시지는 함수(

콜백 함수

콜백)와 연결됩니다. 메시지는 대기열에서 제거되고 처리됩니다. 이 프로세스에는 메시지와 관련된 함수 호출이 포함됩니다(따라서 초기 스택 프레임 생성). 스택이 다시 비어 있으면 메시지가 처리된다는 의미입니다. 연속적이므로 전체 동작 메커니즘을 이벤트 루프(

Event Loop)라고도 합니다.

기본 큐

기본 큐 방법에는 다음 6가지 방법이 포함됩니다.

① 큐에 요소를 추가합니다(tail). )

②(큐의 선두에서) 요소 제거(큐에서 제거)

3 큐의 선두에 있는 요소 확인(앞)

4 ​​큐가 비어 있는지 확인(isEmpty )

⑤ 큐 보기 길이(크기)

⑥ 대기열 보기(인쇄) 🎜

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

🎜🎜우선순위 대기열 구현🎜🎜🎜우선순위 대기열에서는 요소 추가 또는 삭제가 우선순위에 따라 이루어집니다. : ① 먼저 추가, 정상적으로 대기열에서 제거; ② 일반적으로 추가, 먼저 대기열에서 제거 🎜🎜먼저 추가, 정상적으로 대기열에서 제거(최소 우선순위 대기열) 예(이 예는 대기열 구현을 기반으로 하며 대기열에 추가된 요소를 추가합니다. 일반에서 변경 데이터를 큐에 추가해야 하는 요소의 값과 우선순위가 포함된 객체(배열) 유형으로 변환): 🎜

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🎜🎜🎜원형 큐를 사용하여 드럼 연주 게임을 시뮬레이션할 수 있습니다. 꽃 전달(요셉 반지 문제): 한 무리의 어린이가 원 안에 앉아 매번 n개의 숫자를 전달합니다. 멈출 때 꽃을 들고 있는 어린이는 팀에 단 한 명의 어린이만 남을 때까지 탈락합니다. 🎜🎜대기열. (큐의 헤드에서) 하위 항목을 팝한 다음 이 하위 항목을 큐의 끝에 추가합니다. 루프가 중지되면 큐의 헤드에 있는 하위 항목이 팝됩니다( 제거) 대기열에 자식이 한 명만 남을 때까지 🎜

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

🎜 추천 학습: 🎜JavaScript 비디오 튜토리얼🎜🎜

위 내용은 js의 대기열 구현에 대한 심층 분석(코드 공유)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!