摘要：队列是一种列表不同的是队列只能在队尾插入元素在队首删除元素是一种先进先出的数据结构队列被用在很多地方比如提交操作系统执行的一系列进程打印任务池等一些仿真系统用队列来模拟银行或杂货店排队的顾客队列的操作主要有两种操作向队尾中插入新元素入队删除
队列是一种列表, 不同的是队列只能在队尾插入元素, 在队首删除元素. 是一种 先进先出 的数据结构. 队列被用在很多地方, 比如提交操作系统执行的一系列进程、打印任务池等, 一些仿真系统用队列来模拟银行或杂货店排队的顾客.队列的操作
主要有两种操作:
向队尾中插入新元素 入队 ;
删除队头的元素 _出队_;
队列的另一项重要操作是读取队头的元素. 这个操作叫做peek(). 该操作返回队头元素, 但不把它从队列中删除. 除了读取队头元素, 我们还想知道队列中存储了多少元素, 可以使用length属性满足该需求; 想要清空队列中所有元素, 可以使用clear()方法.
用数组实现的队列使用数组来实现队列看起来顺理成章. js中的数组具有其他编程语言中没有的优点, 数组的push()方法可在数组末尾加入元素, shift()方法则可删除数组的第一个元素.
push()方法将它的参数插入数组中第一个开放的位置, 该位置总是在数据的末尾, 即使是一个空数组也是如此. eg:
class Queue {
constructor() {
this._dataStore = [];
}
enqueue(element) {
this._dataStore.push(element);
}
dequeue(element) {
return this._dataStore.shift();
}
front() {
return this._dataStore[0];
}
back() {
return this._dataStore[this._dataStore.length - 1];
}
toString() {
return this._dataStore.join(" ");
}
empty() {
if(this._dataStore.length) {
return false;
};
return true;
}
count() {
return this._dataStore.length;
}
};
// 测试
const q = new Queue();
q.enqueue("a");
q.enqueue("b");
q.enqueue("c");
console.log(q.toString());
q.dequeue();
console.log(q.toString());
console.log(`队首: ${q.front()}`);
console.log(`队尾: ${q.back()}`);
/*
输出结果:
a b c
b c
队首: b
队尾: c
*/
实例
方块舞的舞伴分配问题
当男男女女来到舞池, 他们按照自己的性别排成两列. 当舞池中有地方空出来时, 选两个队列中的第一个人组成舞伴. 他们身后的人各自向前移动一位, 变成新的队首. 当一对舞伴迈入舞池时, 主持人会大声喊出他们的名字. 当一对舞伴走出舞池, 且两排队伍中有任意一队没人时, 主持人也会把这种情况告诉大家.
我们把跳舞的男男女女存在persons对象中.
function getDancers(maleDancers, femaleDancers) {
let dancers = [];
for(let i = 0; i < 8; i++) {
dancers.push({
name: `男${i + 1}`,
sex: "M"
});
if(i < 5) {
dancers.push({
name: `女${i + 1}`,
sex: "F"
});
}
};
dancers.forEach(i => {
if(i.sex === "F") {
femaleDancers.enqueue(i);
} else {
maleDancers.enqueue(i)
}
})
};
function dance(maleDancers, femaleDancers) {
while(!maleDancers.empty() && !femaleDancers.empty()) {
const female = femaleDancers.dequeue();
const male = maleDancers.dequeue();
console.log(`将要入场的舞者是: ${female.name}和${male.name}`);
}
}
const maleDancers = new Queue();
const femaleDancers = new Queue();
getDancers(maleDancers, femaleDancers);
dance(maleDancers, femaleDancers);
程序输出为:
将要入场的舞者是: 女1和男1 将要入场的舞者是: 女2和男2 将要入场的舞者是: 女3和男3 将要入场的舞者是: 女4和男4 将要入场的舞者是: 女5和男5
可能还想对该程序作如下修改: 想显示排队等候跳舞的男性和女性的数量. 队列中目前尚没有显示元素个数的方法, 加入count()在Queue类中.
function getDancers(maleDancers, femaleDancers) {
let dancers = [];
for(let i = 0; i < 8; i++) {
dancers.push({
name: `男${i + 1}`,
sex: "M"
});
if(i < 5) {
dancers.push({
name: `女${i + 1}`,
sex: "F"
});
}
};
dancers.forEach(i => {
if(i.sex === "F") {
femaleDancers.enqueue(i);
} else {
maleDancers.enqueue(i)
}
})
};
function dance(maleDancers, femaleDancers) {
while(!maleDancers.empty() && !femaleDancers.empty()) {
const female = femaleDancers.dequeue();
const male = maleDancers.dequeue();
console.log(`将要入场的舞者是: ${female.name}和${male.name}`);
}
};
const maleDancers = new Queue();
const femaleDancers = new Queue();
getDancers(maleDancers, femaleDancers);
dance(maleDancers, femaleDancers);
if(maleDancers.count() > 0) {
console.log(`还有${maleDancers.count()}名男舞者等候`)
};
if(femaleDancers.count() > 0) {
console.log(`还有${maleDancers.count()}名女舞者等候`)
};
程序输出为:
将要入场的舞者是: 女1和男1 将要入场的舞者是: 女2和男2 将要入场的舞者是: 女3和男3 将要入场的舞者是: 女4和男4 将要入场的舞者是: 女5和男5 还有3名男舞者等候数据排序
队列不仅用于执行显示生活中与排队有关的操作, 还可以用于对于数据进行排序. 计算机刚出现时, 程序是通过穿孔卡输入主机的, 每张卡包含一条程序语句. 这些穿孔卡装在个盒子里, 经一个机械装置进行排序.
这种排序叫做 基础排序 . 虽然它不是最快的排序算法, 但是它展现了一些有趣的队列使用方法.
对于0~99的数字, 基数排序将数据集扫描两次. 第一次按个位上的数字进行排序, 第二次按照十位上的数字进行排序. 每个数字根据对应位上的数值被分在不同盒子里. 假设有如下数字:
91, 46, 85, 15, 92, 35, 31, 22
经过基数排序第一次扫描之后, 数字被分配到如下盒子中:
Bin 0: Bin 1: 91, 31 Bin 2: 92, 22 Bin 3: Bin 4: Bin 5: 85, 15, 35 Bin 6: 46 Bin 7: Bin 8: Bin 9:
根据盒子的顺序, 对数字进行一次排序的结果如下:
91, 31, 92, 22, 85, 15, 35, 46
然后根据十位上的数值再将上次排序的结果分配到不同的盒子中:
Bin 0: Bin 1: 15 Bin 2: 22 Bin 3: 31, 35 Bin 4: 46 Bin 5: Bin 6: Bin 7: Bin 8: 85 Bin 9: 91, 92
最后将盒子中的数字取出, 组成一个新的列表, 该列表即为排好序的数字:
15, 22, 31, 35, 45, 85, 91, 92
算法如下:
function distribute(nums, queues, n, digit) {
for(let 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]);
}
}
};
function collect(queues, nums) {
let i = 0;
for(let digit = 0; digit < 10; digit++) {
while (!queues[digit].empty()) {
nums[i++] = queues[digit].dequeue();
}
}
};
function dispArray(arr) {
let str = "";
arr.forEach(i => {
str += " " + i
});
console.log(str)
};
const queues = [];
for(let i = 0; i <= 10; i++) {
queues[i] = new Queue()
};
const nums = [];
for(let i = 0; i < 10; i++) {
nums[i] = Math.floor(Math.floor(Math.random() * 100))
};
dispArray(nums);
distribute(nums, queues, 10, 1);
collect(queues, nums);
distribute(nums, queues, 10, 10);
collect(queues, nums);
dispArray(nums);
下面是运行几次的结果:
32 35 21 63 59 83 72 22 16 10 10 16 21 22 32 35 59 63 72 83 80 22 14 57 95 11 38 99 6 11 6 11 11 14 22 38 57 80 95 99优先队列
一般情况下, 从队列中删除元素, 一定是率先入队的元素. 但是也有一些使用队列的应用, 在删除删除元素时不必遵守先进先出的约定. 这种应用, 需要使用一个叫做 优先队列 的数据结构来进行模拟.
从优先队列中删除元素时, 需要考虑优先权的限制. 比如医院急症科的候诊室, 就是一个采用 优先队列 的例子. 当病人进入候诊室时, 分诊护士会评估患者病情的严重程度, 然后给一个优先级代码. 高优先级的患者先于低优先级的患者就医, 同样优先级的患者按照先来先服务的顺序就医.
首先定义存储队列元素的对象, 然后再构建我们的 优先队列 系统:
function Patient(name, code) {
this.name = name;
this.code = code;
};
变量code是一个整数, 表示患者的优先级或病情严重程度.
现在需要重新定义dequeue()方法, 使其删除队列中拥有最高级优先级的元素. 我们规定: 优先码的值最小的元素优先级最高. 新的dequeue()方法遍历队列的底层存储数组, 从中找出优先码最低的元素, 然后使用数组的splice()方法删除优先级最高的元素. 新的dequeue()方法如下:
dequeue(element) {
let entry = 0;
this._dataStore.forEach((i, index) => {
if(i.code < this._dataStore[entry].code) {
entry = index;
}
});
return this._dataStore.splice(entry, 1);
}
dequeue()方法使用简单的顺序查找方法寻找优先级最高的元素(代码越小优先级越高, eg: 1比5的优先级高). 该方法返回包含一个元素的数组 一一 从队列中删除的元素.
最后需要定义toString()方法来显示Patient对象:
toString() {
var str = "";
this._dataStore.forEach(i => {
str += i.name + " code:" + i.code + "
";
});
return str;
}
实现:
const ed = new Queue();
ed.enqueue(new Patient("病患1", 5))
ed.enqueue(new Patient("病患2", 4))
ed.enqueue(new Patient("病患3", 6))
ed.enqueue(new Patient("病患4", 1))
ed.enqueue(new Patient("病患5", 1))
console.log(ed.toString())
const seen = ed.dequeue();
console.log(seen[0].name)
console.log(ed.toString())
const seen1 = ed.dequeue();
console.log(seen1[0].name)
console.log(ed.toString())
const seen2 = ed.dequeue();
console.log(seen2[0].name)
console.log(ed.toString())
输出如下:
病患1 code:5 病患2 code:4 病患3 code:6 病患4 code:1 病患5 code:1 病患4 病患1 code:5 病患2 code:4 病患3 code:6 病患5 code:1 病患5 病患1 code:5 病患2 code:4 病患3 code:6 病患2 病患1 code:5 病患3 code:6练习 双向队列
修改一个Queue类, 形成一个Deque类. 这是一个和队列类似的数据结构, 允许从队列两端添加和删除元素, 因此也叫 双向队列 . 写一段测试程序测试该类:
class Queue {
constructor() {
this._dataStore = [];
}
// 队尾入队
enqueueBack(element) {
this._dataStore.push(element);
}
// 队首入队
enqueueFront(element) {
this._dataStore.unshift(element);
}
// 队尾出队
dequeueBack() {
return this._dataStore.pop();
}
// 队首出队
dequeueFront() {
return this._dataStore.shift();
}
// 第一个
front() {
return this._dataStore[0];
}
// 最后一个
back() {
return this._dataStore[this._dataStore.length - 1];
}
// 输出
toString() {
return this._dataStore.join(" ");
}
// 是否为空
empty() {
if(this._dataStore.length) {
return false;
};
return true;
}
// 个数
count() {
return this._dataStore.length;
}
};
const d = new Queue();
d.enqueueBack(3)
d.enqueueBack(4)
d.enqueueBack(5)
console.log(d.toString())
d.enqueueFront(2)
d.enqueueFront(1)
console.log(d.toString())
d.dequeueBack()
d.dequeueBack()
console.log(d.toString())
d.dequeueFront()
console.log(d.toString())
输入结果:
3 4 5 1 2 3 4 5 1 2 3 2 3使用Deque类来判断一个给定单词是否为回文
首先让单词每个字母入队, 然后两端同时出队, 判断队首队尾字母是否相等.
const str = "121"
function isPalindrome(word) {
const d = new Queue();
for(let w of word) {
d.enqueueBack(w)
};
while(!d.empty()) {
if(d.front() !== d.back()) {
return false;
} else {
d.dequeueBack();
d.dequeueFront();
}
};
return true;
};
console.log(isPalindrome(str)); // true
修改文章中 优先队列 使得优先级高的元素优先码也大.
这里只需要在出队的时候按照优先码最大的先出队.
...
dequeue(element) {
let entry = 0;
this._dataStore.forEach((i, index) => {
if(i.code > this._dataStore[entry].code) {
entry = index;
}
});
return this._dataStore.splice(entry, 1);
}
...
验证:
function Patient(name, code) {
this.name = name;
this.code = code;
};
const ed = new Queue();
ed.enqueue(new Patient("病患1", 5))
ed.enqueue(new Patient("病患1-1", 5))
ed.enqueue(new Patient("病患3", 6))
ed.enqueue(new Patient("病患4", 1))
ed.enqueue(new Patient("病患5", 1))
console.log(ed.toString())
const seen = ed.dequeue();
console.log("出队病患 =>", seen[0].name)
console.log(ed.toString())
const seen1 = ed.dequeue();
console.log("出队病患 =>", seen1[0].name)
console.log(ed.toString())
const seen2 = ed.dequeue();
console.log("出队病患 =>", seen2[0].name)
console.log(ed.toString())
输入结果:
病患1 code:5 病患1-1 code:5 病患3 code:6 病患4 code:1 病患5 code:1 出队病患 => 病患3 病患1 code:5 病患1-1 code:5 病患4 code:1 病患5 code:1 出队病患 => 病患1 病患1-1 code:5 病患4 code:1 病患5 code:1 出队病患 => 病患1-1 病患4 code:1 病患5 code:1修改上例, 使得候诊室内的活动可以被控制
类似菜单系统, 让用户可以进行如下选择:
患者进入候诊室
患者就诊
显示等待就诊患者名单
class Queue {
constructor() {
this._dataStore = [];
}
enqueue(element) {
this._dataStore.push(element);
}
dequeue(element) {
let entry = 0;
this._dataStore.forEach((i, index) => {
if(i.code > this._dataStore[entry].code) {
entry = index;
}
});
return this._dataStore.splice(entry, 1);
}
front() {
return this._dataStore[0];
}
back() {
return this._dataStore[this._dataStore.length - 1];
}
toString() {
var str = "";
this._dataStore.forEach(i => {
str += i.name + " code:" + i.code + "
";
});
return str;
}
empty() {
if(this._dataStore.length) {
return false;
};
return true;
}
count() {
return this._dataStore.length;
}
};
class Room {
constructor() {
this._q = new Queue();
}
// 患者进入候诊室 code值越大 优先级越高
enter(name, code) {
this._q.enqueue({
name, code
});
}
// 患者就诊 也是就是从候诊室队列中出队
seeDoctor() {
return this._q.dequeue()[0].name;
}
// 显示等待就诊患者名单
showRoom() {
return this._q.toString();
}
};
const r = new Room();
r.enter("患者1", 2);
r.enter("患者2", 3);
r.enter("患者3", 1);
r.enter("患者4", 4);
r.enter("患者5", 4);
r.enter("患者6", 5);
console.log(r.showRoom())
console.log(r.seeDoctor(), " 就诊")
console.log(r.seeDoctor(), " 就诊")
console.log(r.showRoom())
console.log(r.seeDoctor(), " 就诊")
console.log(r.showRoom())
输出结果:
患者1 code:2 患者2 code:3 患者3 code:1 患者4 code:4 患者5 code:4 患者6 code:5 患者6 就诊 患者4 就诊 患者1 code:2 患者2 code:3 患者3 code:1 患者5 code:4 患者5 就诊 患者1 code:2 患者2 code:3 患者3 code:1
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/97847.html
摘要：在队列的这种数据结构里面，新增的元素都在尾部，要移除的元素都在顶部。代码实现下面用代码来实现队列这个数据结构，同样都采用的语法，我们先定义一个类来表示队列，然后在这个类的基础上定义一下方法来模拟队列的行为。 队列和栈非常的类似，但是他们采用了不同的原则，栈采用的是后进先出，队列正好相反，采用的是先进先出的原则。队列的定义如下 队列是遵循FIFO(先进先出)原则的有序集合，新添加的元素保...
摘要：前言数据结构与算法专题会不定时更新，欢迎各位读者监督。队列和栈类似，也是一个遵循特殊规则约束的数据结构。将没有元素的队列称之为空队，往队列中插入元素的过程称之为入队，从队列中移除元素的过程称之为出队。 声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。 前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本文介绍数据结构中的队列（queue）的概念、存储结构、队列的特点...
摘要：而且目前大部分编程语言的高级应用都会用到数据结构与算法以及设计模式。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。 前言 JavaScript是当下最流行的编程语言之一，它可以做很多事情： 数据可视化（D3.js，Three.js，Chart.js）; 移动端应用(React Native,Weex,AppCan,Flutter,Hybrid App,小程...
阅读 1646·2021-09-07 10:24
阅读 1849·2019-08-30 15:55
阅读 1897·2019-08-30 15:43
阅读 554·2019-08-29 15:25
阅读 842·2019-08-29 12:19
阅读 1814·2019-08-23 18:32
阅读 1402·2019-08-23 17:59
阅读 852·2019-08-23 12:22
