javascript实现优先队列
2024-09-28 02:34:59
1.概念
一般情况下从队列中删除元素,都是率先入队的元素。但是有些使用队列的情况不遵循先进先出的原则,这就是插队,这需要使用优选队列的数据结构来进行描述。
从优先队列中删除元素的时候,需要考虑优先级的限制。比如医院急诊科的例子就是一个典型的优先队列的例子。当病人进入急诊室的时候,护士先根据病情给一个优先级代码,高优先级的患者先于低优先级的患者就医,优先级相同的根据先来先服务的顺序就医。
定义存储队列元素的对象,然后构建优先队列数据结构。
function Patient(name, code) {
this.name = name;
this.code = code;
}
变量code是一个整数,标识患者优先级或者病情验证程度,规定优先级代码越小优先级越高。新的dequeue() 方法遍历队列的底层存储数组,从中找出优先码最低的元素,然后使用数组的splice() 方法删除优先级最高的元素。新的dequeue() 方法定义如下所示:
function dequeue(){
var priority = this.dataStore[0].code;
var fromIndex = 0;
for (var i=1; i<this.dataStore.length; ++i) {
if (this.dataStore[i].code < priority) {
fromIndex = i;
}
}
return this.dataStore.splice(fromIndex, 1);
}
dequeue() 方法使用简单的顺序查找方法寻找优先级最高的元素(优先码越小优先级越高,比如,1 比5 的优先级高)。该方法返回包含一个元素的数组——从队列中删除的元素。
2.代码实现
完整的代码如下所示:
/*--------------Queue类的定义和测试代码----------------*/
function Queue(){
this.dataStore = [];
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
} //入队,就是在数组的末尾添加一个元素
function enqueue(element){
this.dataStore.push(element);
}
//出队,判断优先级删除,注意这里用的是数组的splice方法,不是slice方法
function dequeue(){
var priority = this.dataStore[0].code;
var fromIndex = 0;
for (var i=1; i<this.dataStore.length; ++i) {
if (this.dataStore[i].code < priority) {
fromIndex = i;
}
}
return this.dataStore.splice(fromIndex, 1);
}
//取出数组的第一个元素
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].name + " 优先级:" + this.dataStore[i].code + "<br>"
}
return retStr;
}
//判断数组是否为空
function empty(){
if(this.dataStore.length == 0){
return true;
}else{
return false;
}
}
//返回数组中元素的个数
function count(){
return this.dataStore.length;
} /*----------------基数排序-----------------*/ function Patient(name, code){
this.name = name;
this.code = code;
}
var p = new Patient('smith', 5);
var ed = new Queue();
ed.enqueue(p); p = new Patient('jones', 4);
ed.enqueue(p); p = new Patient('fehrendbach', 6);
ed.enqueue(p); p = new Patient('brown', 1);
ed.enqueue(p); p = new Patient('ingram', 1);
ed.enqueue(p); document.write(ed.toString()); var seen = ed.dequeue();
document.write('<br>');
document.write("服务病人:" + seen[0].name); document.write('<br>');
document.write(ed.toString()); seen = ed.dequeue();
document.write('<br>');
document.write("服务病人:" + seen[0].name); document.write('<br>');
document.write(ed.toString()); seen = ed.dequeue();
document.write('<br>');
document.write("服务病人:" + seen[0].name); document.write('<br>');
document.write(ed.toString());
输出结果为:
最新文章
- 第三讲. COTS包交换介绍
- ubuntu随笔
- [ASE]sprint2 总结 &; sprint3计划
- 使用SWFUpload无刷新上传图片
- HTML5 webapp框架
- 【阿里云产品公测】高大上的搜索服务OpenSearch,你值得拥有!
- bzoj1412: [ZJOI2009]狼和羊的故事
- ****php redis 的使用方法
- Codeforces 628D 数位dp
- Memcached启动脚本
- JavaScript判断对象类型及节点类型、节点名称和节点值
- SDP(5):ScalikeJDBC- JDBC-Engine:Streaming
- CSS规范—分类方法(NEC规范学习笔记)
- Codeforces Round #436 C. Bus
- threw exception [Handler processing failed; nested exception is java.lang.NoClassDefFoundError: com/dyuproject/protostuff/MapSchema$MessageFactory] with root cause
- JavaEE - 20181225
- mysql基本知识总结
- MySQL GTID 主从复制错误修复方法
- oracle的行级触发器使用
- WIN10 64位系统 如何安装.NET Framwork3.5
热门文章
- 福利->;KVC+Runtime获取类/对象的属性/成员变量/方法/协议并实现字典转模型
- 操作系统开发系列—12.f.在内核中添加中断处理 ●
- 使用imeOptions
- 【代码笔记】iOS-伸缩式动画
- 【代码笔记】iOS-仿QQ空间,歌曲播放
- 【VLC-Android】LibVLC API简介(相当于VLC的MediaPlayer)
- iOS tableView 静态单元格的实现
- UILabel和NSAttributedString那些事
- thinkphp 创建子应用
- [java]byte和byte[]与int之间的转换