Detailed explanation of JavaScript priority queue and circular queue examples-JS Tutorial-php.cn

Detailed explanation of JavaScript priority queue and circular queue examples

小云云

Release： 2018-01-20 10:21:30

Original

1641 people have browsed it

This article mainly introduces the priority queue and circular queue of the JavaScript data structure. It analyzes the principles, definitions and usage of the priority queue and circular queue in the javascript data structure in detail in the form of examples. Friends in need can refer to it. I hope Can help everyone.

Priority Queue

Implement a priority queue: set the priority, then add elements at the correct position.

What we implement here is a minimum priority queue, and elements with small priority values (high priority) are placed in front of the queue.

//创建一个类来表示优先队列
function Priorityqueue(){
  var items=[];//保存队列里的元素
  function QueueEle(e,p){//元素节点，有两个属性
    this.element=e;//值
    this.priority=p;//优先级
  }
  this.enqueue=function(e,p){//添加一个元素到队列尾部
    var queueEle=new QueueEle(e,p);
    var added=false;
    //priority小的优先级高，优先级高的在队头
    if(this.isEmpty()){
      items.push(queueEle);
    }else{
      for(var i=0;i<items.length;i++){
        if(items[i].priority>queueEle.priority){
          items.splice(i,0,queueEle);
          added=true;
          break;
        }
      }
      if(!added){
        items.push(queueEle);
      }
    }
  }
  this.isEmpty=function(){
    return items.length==0;
  }
  this.dequeue=function(){
    return items.shift();
  }
  this.clear=function(){
    items=[];
  }
  this.print=function(){
    console.log(items);
  }
  this.mylength=function(){
    return items.length;
  }
}
var pqueue=new Priorityqueue();
pqueue.enqueue('a',2);
pqueue.enqueue('b',1);
pqueue.enqueue('c',2);
pqueue.enqueue('d',2);
pqueue.enqueue('e',1);
pqueue.print();
//[ QueueEle { element: 'b', priority: 1 },
// QueueEle { element: 'e', priority: 1 },
// QueueEle { element: 'a', priority: 2 },
// QueueEle { element: 'c', priority: 2 },
// QueueEle { element: 'd', priority: 2 } ]

Copy after login

Running results:

Add elements at the correct position: If the queue is empty, you can directly enqueue the elements. Otherwise, the priority of this element needs to be compared with other elements. When an item with a lower priority than the element to be added is found, the new element is inserted before it. In this way, for other elements with the same priority but added to the queue first, we also follow the first-in-first-out principle.

Maximum priority queue: Elements with larger priority values are placed at the front of the queue.

Circular Queue

Implement the drumming and flower passing game.

//创建一个类来表示队列
function Queue(){
  var items=[];//保存队列里的元素
  this.enqueue=function(e){//添加一个元素到队列尾部
    items.push(e);
  }
  this.dequeue=function(){//移除队列的第一项，并返回
    return items.shift();
  }
  this.front=function(){//返回队列的第一项
    return items[0];
  }
  this.isEmpty=function(){//如果队列中部包含任何元素，返回true，否则返回false
    return items.length==0;
  }
  this.mylength=function(){//返回队列包含的元素个数
    return items.length;
  }
  this.clear=function(){//清除队列中的元素
    items=[];
  }
  this.print=function(){//打印队列中的元素
    console.log(items);
  }
}
//击鼓传花
function hotPotato(namelist,num){
  var queue=new Queue();
  for(var i=0;i<namelist.length;i++){
    queue.enqueue(namelist[i]);
  }
  var eliminated=&#39;&#39;;
  while(queue.mylength()>1){
    for(i=0;i<num;i++){
      queue.enqueue(queue.dequeue());
    }
    eliminated=queue.dequeue();
    console.log("淘汰"+eliminated);
  }
  return queue.dequeue();
}
var namelist=['a','b','c','d','e'];
var winner=hotPotato(namelist,7);
console.log(winner+"获胜");
//淘汰c
//淘汰b
//淘汰e
//淘汰d
//a获胜

Copy after login

Run result:

Get a list and add all the names in it to the queue. Given a number, the queue is iterated over. Remove an item from the head of the queue and add it to the tail of the queue to simulate a circular queue. Once the number of passes reaches a given number, the person who got the flower is eliminated. When there is only one person left in the end, he is the winner.

Related recommendations:

Detailed explanation of how priority queue is implemented in JDK

PHP data structure queue (SplQueue) and priority queue ( SplPriorityQueue) simple usage example_PHP tutorial

Circular queue code implemented using arrays in javascript_javascript skills

The above is the detailed content of Detailed explanation of JavaScript priority queue and circular queue examples. For more information, please follow other related articles on the PHP Chinese website!