js学习队列以及使用队列实现约瑟夫环问题

广告位

js学习队列 一、队列结构 队列只允许在一端插入另一端删除,是一种先进先出(FIFO)的线性表。队列中插入端为…

js学习队列

一、队列结构

队列只允许在一端插入另一端删除,是一种先进先出(FIFO)的线性表。队列中插入端为队尾,删除端为队头。

js学习队列以及使用队列实现约瑟夫环问题

二、封装队列

1、以数组封装队列(类)

  class Queue{     constructor(){         this.item = [];     }     enQueue(element){         this.item.push(element);     }     deQueue(){         return this.item.shift();     }     front(){         return this.item[0];     }     isEmpty(){         return this.item.length == 0;     }     size(){         return this.item.length;     } } 

2、使用单向链表封装队列

         class LinkQueue{             constructor(){                 this.list = new OneLinkList();             }             enQueue(element){                 this.list.append(element);             }             deQueue(){                 let headData = this.list.head.data;                 this.list.removeAt(0);                 return headData;             }             front(){                 return this.list.head.data;             }             isEmpty(){                 return this.list.length == 0;             }             size(){                 return this.list.length;             }         } 

3、封装优先级队列

class PriorityElement{     constructor(element,priority){         this.element = element;         this.priority = priority;     } } class PriorityQueue{     constructor(){         this.item = [];     }     enQueue(element, priority){         let data = new PriorityElement(element,priority);         if(this.isEmpty()){             this.item.push(data);         }         else{             let added = false;             for(let i = 0; i < this.item.length; i++){                 if(data.priority < this.item[i].priority){                     this.item.splice(i,0,data);                     added = true;                     break;                 }             }             if(!added){                 this.item.push(data);             }         }     }     deQueue(){         return this.item.shift();     }     isEmpty(){         return this.item.length == 0;     }     size(){         return this.item.length;     }     front(){         return this.item[0];     }     toString(){         let result  = '';         for(let i = 0; i < this.item.length; i++){             result += this.item[i].element + '-' + this.item[i].priority + ' ';         }         return result;     } } 
三、队列的应用

1、使用队列实现约瑟夫环

约瑟夫环:m个人围成一个圈, 指定一个数字n,从第一个人开始报数, 每轮报到n的选手出局,由下一个人接着从头开始报,最后一个人是赢家。其中m>1,n>2。

        //队列:         function josephRingQueue(list, num, winNum) {             let queue = new Queue();             //遍历数组,让数组中的元素依次入队             list.forEach((item) => {                 queue.enQueue(item);             });             //队列中还有大于两个人时             while (queue.size() > winNum) {                 //存活的人从队首出对再从队尾入队                 for (let i = 0; i < num - 1; i++) {                     queue.enQueue(queue.deQueue());                 }                 //淘汰的人直接从队列出对不再入队                 queue.deQueue();             }             //队列中仅剩两个人时游戏结束             return queue;         }         let people = [];         ((people,n) => {             for(let i = 1; i <= n; i++){                 people.push(i);             }         })(people,41);         console.log(josephRingQueue(people,3,2).toString()); 

說着敷衍話

关于作者: 說着敷衍話

为您推荐