js数据结构算法---优先队列、双向队列

（一）什么是优先队列

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。

比如：医院急诊室，医生会根据患者的病情严重程度，给患者一个优先级码，当医生空闲时，候诊区优先级最高的患者最先就诊

队列出栈时，优先级高的先与优先级低的 

同样优先级的，按照入栈顺序出栈

（二）代码实现优先队列

与队列不同的是，每一各元素需要一个code优先级码

// 定义每个元素 class Patient { constructor (value, code) { this.value = value this.code = code // 最小值0 } } class Quence { constructor () { this.QuentList = [] } // 入列 enquence (patient) { this.QuentList.push(patient) } // 出列 code 码越高优先级越大 先出列 dequence () { // 遍历找到code最大的一项 var current = 0 for (var i = 0; i < this.QuentList.length; i++) { if (this.QuentList[i].code > this.QuentList[current].code) { current = i } } this.QuentList.splice(current, 1) // code最大项出栈 } getQuent () { return this.QuentList } } var queue = new Quence() queue.enquence(new Patient('lily', 4)) queue.enquence(new Patient('bob', 5)) queue.enquence(new Patient('lucy', 8)) queue.enquence(new Patient('hibby', 8)) queue.dequence() console.log(queue.getQuent())

（三）双向队列

允许队列从两端添加、删除元素

pop、push、unshift、shift

（四）代码实现

function Queue(){ this.dataStore = []; this.enqueueFront = enqueueFront; this.enqueueBack = enqueueBack; this.dequeueFront = dequeueFront; this.dequeueBack = dequeueBack; this.front = front; this.back = back; this.toString = toString; this.empty = empty; } //尾部入队，就是在数组的末尾添加一个元素 function enqueueBack(element){ this.dataStore.push(element); } //头部入队，就是在数组的头部添加一个元素 function enqueueFront(element){ this.dataStore.splice(0,0,element); } //尾部出队，就是删除数组的最后一个元素 function dequeueBack(){ return this.dataStore.splice(this.dataStore.length-1, 1); } //出队，就是删除数组的第一个元素 function dequeueFront(){ return this.dataStore.shift(); } //取出数组的第一个元素 function front(){ return this.dataStore[0]; } //取出数组的最后一个元素 function back(){ return this.dataStore[this.dataStore.length-1]; } function toString(){ var retStr = ""; for (var i=0; i<this.dataStore.length; ++i) { retStr += this.dataStore[i] + " " } return retStr; } //判断数组是否为空 function empty(){ if(this.dataStore.length == 0){ return true; }else{ return false; } } //返回数组中元素的个数 function count(){ return this.dataStore.length; } var q = new Queue(); q.enqueueFront("1"); q.enqueueFront("2"); q.enqueueBack("3"); q.enqueueBack("4"); document.write(q.toString()); document.write('<br>'); q.dequeueFront(); document.write(q.toString()); document.write('<br>'); q.dequeueBack(); document.write(q.toString()); document.write('<br>'); document.write('<br>');