JavaScript 대기열 원칙 및 사용 예에 대한 자세한 설명-JS 튜토리얼-php.cn

큐는 일종의 목록입니다. 차이점은 큐의 끝에만 요소를 삽입하고 처음에 요소를 삭제할 수 있다는 것입니다. 큐는 스택(후입 선출)과 달리 선입선출 순서로 데이터를 저장하는 데 사용됩니다. 스택에서는 스택에 푸시된 마지막 요소가 먼저 처리됩니다. 이제 우리는 식당에 식사를 하러 갈 때처럼 줄을 상상할 수 있습니다. 많은 사람들이 식사를 하기 위해 줄을 서고, 앞에 있는 사람이 먼저 식사를 합니다. 신규 이민자는 뒤쪽에만 줄을 설 수 있습니다. 그들의 차례가 될 때까지. 본 글에서는 주로 자바스크립트 데이터 구조와 알고리즘에서 큐의 원리와 사용법을 소개하고, 큐의 개념과 원리를 좀 더 자세히 설명하며, 자바스크립트에서 큐를 구현하고 사용하기 위한 관련 운용 기술과 주의사항을 예시 형태로 분석한다. 도움이 필요한 경우 다음을 참조하세요. 모두에게 도움이 되기를 바랍니다.

1: 대기열 작업

대기열에는 두 가지 주요 작업이 있습니다. 대기열의 꼬리enqueue()메서드에 새 요소를 삽입하는 것과 대기열의 선두에 있는 요소를 삭제하는 것dequeue()입니다. 메서드 외에도 대기열의 앞부분을 읽는 요소도 있습니다. 이 메서드를 front() 메서드라고 부를 수 있습니다. 이 메서드는 헤드 요소와 기타 메서드를 반환합니다.

위 설명을 보면 배열에도 위의 메서드와 비슷한 기능을 하는 두 가지 메서드가 있다고 생각하는 분들이 많을 것입니다. 배열의 push() 메서드도 배열에 새로운 요소를 추가합니다. 배열의 뒷면 shift() 메서드는 배열의 첫 번째 요소를 삭제할 수 있습니다. 다음 코드: push()方法也是往数组后面加入新元素，数组中shift()方法则可以删除数组里面的第一个元素。如下代码：

var arrs = [];
arrs.push("a");
arrs.push("b");
console.log(arrs); // ["a","b"];
arrs.shift();
console.log(arrs); // [&#39;b&#39;];

로그인 후 복사

下面我们可以使用上面的数组中的push()和shift()的2个方法来封装我们的队列Queue类；

1. 我们可以先定义一个构造函数Queue类，如下：

function Queue() {
  this.dataStore = [];
}

로그인 후 복사

如上：this.dataStore = [];

function enqueue(element) {
   this.dataStore.push(element);
}

로그인 후 복사

아래에서는 위 배열의 push() 및 shift() 두 가지 메서드를 사용하여 대기열 Queue 클래스를 캡슐화할 수 있습니다.

1. 먼저 다음과 같이 생성자 Queue 클래스를 정의할 수 있습니다.

function dequeue() {
  return this.dataStore.shift()
}

로그인 후 복사

위와 같이: this.dataStore = []; 빈 배열을 사용하면 대기열이 저장됩니다.

2. 팀의 꼬리에 요소를 추가하는 방법은 다음과 같습니다.

function front() {
  return this.dataStore[0];
}

로그인 후 복사

3. 팀장의 요소를 삭제하는 방법은 다음과 같습니다.

function back() {
  return this.dataStore[this.dataStore.length - 1];
}

로그인 후 복사

4. 팀장의 요소를 읽는 방법은 다음과 같습니다.

function toString() {
  var retStr = "";
  for(var i = 0; i < this.dataStore.length; ++i) {
    retStr += this.dataStore[i] + "\n";
  }
  return retStr;
}

로그인 후 복사

5. 다음과 같이 대기열 끝의 요소를 읽습니다.

function empty(){
  if(this.dataStore.length == 0) {
    return true;
  }else {
    return false;
  }
}

로그인 후 복사

6. the queue

function Queue() {
  this.dataStore = [];
}
Queue.prototype = {
  // 向队尾添加一个元素
  enqueue: function(element) {
    this.dataStore.push(element);
  },
  // 删除队首的元素
  dequeue: function(){
    return this.dataStore.shift();
  },
  // 读取队首的元素
  front: function(){
    return this.dataStore[0];
  },
  // 读取队尾的元素
  back: function(){
    return this.dataStore[this.dataStore.length - 1];
  },
  // 显示队列内的所有元素
  toString: function(){
    var retStr = "";
    for(var i = 0; i < this.dataStore.length; ++i) {
      retStr += this.dataStore[i] + "\n";
    }
    return retStr;
  },
  // 判断队列是否为空
  empty: function(){
    if(this.dataStore.length == 0) {
      return true;
    }else {
      return false;
    }
  }
};

로그인 후 복사

7. 다음과 같이 큐가 비어 있는지 판단합니다.

var q = new Queue();
q.enqueue("a");
q.enqueue("b");
q.enqueue("c");
console.log(q.toString()); // a b c
q.dequeue();
console.log(q.toString()); // b c
console.log("Front of queue:" +q.front()); // b
console.log("Back of queue:" +q.back()); // c

로그인 후 복사

다음이 완료되었습니다. JS 코드는 다음과 같습니다.

var nums = ["50","12","95","7","90","3","74","81","91","72"];

로그인 후 복사

이제 위 코드를 테스트할 수 있습니다.

queues[0] = 50 或者 90
queues[1] = 81 或者 91
queues[2] = 12 或者 72
queues[3] = 3
queues[4] = 74
queues[5] = 95
queues[6] 
queues[7] = 7
queues[8]
queues[9]

로그인 후 복사

두 가지: 대기열을 사용하여 데이터 정렬

예를 들어 0 ~ 99의 숫자를 정렬하는 원칙은 다음과 같습니다. 먼저 숫자를 한 자리에서 정렬한 다음 숫자를 정렬합니다. 다시 십의 자리에. 각 숫자를 해당 숫자의 값에 따라 서로 다른 상자로 나누고, 한 자리에 있는 숫자는 나머지 방식을 사용하고, 10번째 숫자는 나누기 방식을 사용하는 것을 이러한 정렬이라고 합니다. "기수 정렬" 가장 빠른 정렬 방법은 아니지만 대기열을 사용하는 몇 가지 흥미로운 방법을 설명합니다.

예를 들어 다음 배열은

nums = [50,90,81,91,12,72,3,74,95,7]

로그인 후 복사

1입니다. 기수 정렬 - 단위 정렬 후 숫자는 다른 상자에 배포됩니다. (JS에서는 이를 다른 Queue 인스턴스 클래스에 할당할 수 있습니다.) 다음과 같습니다

queues[5] = 50
queues[9] = 90
queues[8] = 81
queues[9] = 91
queues[1] = 12
queues[7] = 72
queues[0] = 3
queues[7] = 74
queues[9] = 95
queues[0] = 7

로그인 후 복사

상자의 순서에 따라 숫자의 첫 번째 자리를 정렬한 결과는 다음과 같습니다.

nums = [3,7,12,50,72,74,81,90,91,95];

로그인 후 복사

2. 마지막 정렬 후의 결과는 상자에서 다른 항목에 할당됩니다. 다음과 같습니다:

/*
* 根据个位或十位上的数值，将数字分配到相应队列的函数
* @param digit
* digit=1 表示先按个位来分配
* digit = 10 表示是按十位来分配的
* @param n 表示循环比较多少次 一般数组几个数字就比较多少次
*/
distribute: function(nums,queues,n,digit){
   for(var i = 0; i < n; ++i) {
    if(digit == 1) {
      queues[nums[i] % 10].enqueue(nums[i]);
     }else {
      queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
     }
   }
}

로그인 후 복사

마지막으로 상자에 있는 숫자를 꺼내서 정렬된 숫자인 새 목록을 만듭니다.

는 다음과 같이 생성될 수 있습니다.

// 收集数字的函数
collect: function(queues,nums,n) {
  var i = 0;
  for(var digit = 0; digit < n; ++digit) {
    while(!queues[digit].empty()) {
      nums[i++] = queues[digit].dequeue();
    }
  }
}

로그인 후 복사

위와 같이 대기열 목록 상자를 사용하여 이 알고리즘을 구현할 수 있습니다. 각 대기열은 숫자에 해당하며 모든 대기열을 배열에 저장합니다. 그리고 fetch를 사용하세요. 나머지와 나누기 연산은 1과 10의 자리를 결정합니다. 알고리즘의 나머지 부분은 해당 대기열에 숫자를 추가하고, 1자리 값을 기준으로 재정렬한 다음, 10자리 값을 기준으로 정렬하고, 정렬된 숫자를 결과로 추가합니다.

다음은 일의 자리 또는 십의 자리의 값을 기준으로 해당 대기열에 번호를 할당하는 기능입니다.

function Queue() {
  this.dataStore = [];
}
Queue.prototype = {
  // 向队尾添加一个元素
  enqueue: function(element) {
    this.dataStore.push(element);
  },
  // 删除队首的元素
  dequeue: function(){
    return this.dataStore.shift();
  },
  // 读取队首的元素
  front: function(){
    return this.dataStore[0];
  },
  // 读取队尾的元素
  back: function(){
    return this.dataStore[this.dataStore.length - 1];
  },
  // 显示队列内的所有元素
  toString: function(){
    var retStr = "";
    for(var i = 0; i < this.dataStore.length; ++i) {
      retStr += this.dataStore[i] + "\n";
    }
    return retStr;
  },
  // 判断队列是否为空
  empty: function(){
    if(this.dataStore.length == 0) {
      return true;
    }else {
      return false;
    }
  },
  /*
   * 根据个位或十位上的数值，将数字分配到相应队列的函数
   * @param digit
   * digit=1 表示先按个位来分配
   * digit = 10 表示是按十位来分配的
   * @param n 表示循环比较多少次 一般数组几个数字就比较多少次
   */
  distribute: function(nums,queues,n,digit){
    for(var i = 0; i < n; ++i) {
      if(digit == 1) {
        queues[nums[i] % 10].enqueue(nums[i]);
      }else {
        queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
      }
    }
  },
  // 收集数字的函数
  collect: function(queues,nums,n) {
    var i = 0;
    for(var digit = 0; digit < n; ++digit) {
      while(!queues[digit].empty()) {
        nums[i++] = queues[digit].dequeue();
      }
    }
  },
  dispArray: function(arr) {
    for(var i = 0; i < arr.length; ++i) {
      console.log(arr[i]);
    }
  }
};

로그인 후 복사

다음은 대기열에서 숫자를 수집하는 함수입니다.

var q = new Queue();
  q.enqueue("a");
  q.enqueue("b");
  q.enqueue("c");
console.log(q.toString());
q.dequeue();
console.log(q.toString());
console.log("Front of queue:" +q.front());
console.log("Back of queue:" +q.back());
var queues = [];
for(var i = 0; i < 10; ++i) {
   queues[i] = new Queue();
}
var nums = ["50","12","95","7","90","3","74","81","91","72"];
console.log("before radix sort: ");
console.log(nums);
q.distribute(nums,queues,10,1);
q.collect(queues,nums,10);
q.dispArray(nums);
console.log("分割线");
q.distribute(nums,queues,10,10);
q.collect(queues,nums,10);
q.dispArray(nums);

로그인 후 복사

위에서는 많은 단계를 생략했기 때문에 설명이 명확하지 않을 수 있습니다. 먼저 순서도를 살펴보겠습니다. . 흐름도와 결합하면 마지막으로 모든 JS 코드를 결합하여 "기수 정렬"의 기본 원리를 이해할 수 있습니다. 아래에서는 다음 흐름도를 볼 수 있습니다.

🎜🎜마지막으로 모든 JS 코드는 🎜🎜🎜🎜rrreee🎜다음은 "기수 정렬" JS 코드를 테스트합니다. 🎜🎜🎜🎜

var q = new Queue();
  q.enqueue("a");
  q.enqueue("b");
  q.enqueue("c");
console.log(q.toString());
q.dequeue();
console.log(q.toString());
console.log("Front of queue:" +q.front());
console.log("Back of queue:" +q.back());
var queues = [];
for(var i = 0; i < 10; ++i) {
   queues[i] = new Queue();
}
var nums = ["50","12","95","7","90","3","74","81","91","72"];
console.log("before radix sort: ");
console.log(nums);
q.distribute(nums,queues,10,1);
q.collect(queues,nums,10);
q.dispArray(nums);
console.log("分割线");
q.distribute(nums,queues,10,10);
q.collect(queues,nums,10);
q.dispArray(nums);

로그인 후 복사