阅读《数据结构与算法 JavaScript 描述 第二版》之队列
概述
- 数据尾部进入
- 数据头部移除
特点
- First-In-First-Out 先进后出
实现一个简单的队列
实现一个简单的队列数据类型（基于数组）
```js export default function Queue() { this.dataStore = []; }
Queue.prototype.enqueue = function(elment) { this.dataStore.push(elment) }
Queue.prototype.dequeue = function() { return this.dataStore.shift() }
Queue.prototype.front = function() { return this.dataStore[0] }
Queue.prototype.back = function() { return this.dataStore[this.dataStore.length - 1] }
Queue.prototype.toString = function() { let retStr = ""; for (let i = 0; i < this.dataStore.length; ++i) { retStr += this.dataStore[i] + "\n"; }
return retStr }
Queue.prototype.empty = function() { if(this.dataStore.length === 0) { return true } else { return false } } ```
下面是通过 Jest 的测试用例
配置 jest
```sh npm install jest
$ ./node_modules/jest/bin/jest.js --init # 使用 jest 提供的命令自动初始化 ```
考虑到目前 es module 已经开始普及，此时使用 esm 比较合适，在初始化的时候注意选择与 esm 的选项。同时 package.json 的内容中：
json
{
"type": "module",
}
- 测试用例中，使用测试套件 describe/测试用例 it， 使用 spec 标记是测试文件
测试用例
```js import Queue from "../Queue"
describe("api 测试", () => {
it("toString 方法测试", () => {
let q = new Queue()
q.enqueue('张三')
q.enqueue('李四')
q.enqueue('王五')
expect(q.toString()).toMatchInlineSnapshot("张三
李四
王五
")
})
it("dequeue 方法测试", () => {
let q = new Queue()
q.enqueue('张三')
q.enqueue('李四')
q.enqueue('王五')
q.dequeue()
expect(q.toString()).toMatchInlineSnapshot("李四
王五
")
})
it("front/back 方法测试", () => {
let q = new Queue()
q.enqueue('张三')
q.enqueue('李四')
q.enqueue('王五')
q.dequeue()
expect(q.front()).toMatchInlineSnapshot("李四")
expect(q.back()).toMatchInlineSnapshot("王五")
})
})
```
三个示例
- 方块舞的舞伴分配问题
方块舞的舞伴分配问题
```js import fs from 'node:fs'
export default function Queue() { this.dataStore = []; }
Queue.prototype.enqueue = function(elment) { this.dataStore.push(elment) }
Queue.prototype.dequeue = function() { return this.dataStore.shift() }
Queue.prototype.front = function() { return this.dataStore[0] }
Queue.prototype.back = function() { return this.dataStore[this.dataStore.length - 1] }
Queue.prototype.toString = function() { let retStr = ""; for (let i = 0; i < this.dataStore.length; ++i) { retStr += this.dataStore[i] + "\n"; }
return retStr }
Queue.prototype.empty = function() { if(this.dataStore.length === 0) { return true } else { return false } }
Queue.prototype.count = function() { return this.dataStore.lastIndexOf.length; } ```
- 实现跳舞人分配
```js
export let maleDancers = new Queue() export let femaleDancers = new Queue()
export function Dancer(name, sex) { this.name = name; this.sex = sex; }
export function getDancers(maleDancers, femaleDancers) { let names = read(join(__dirname, './texts/dancers.txt')).split('\n')
for (let i = 0; i < names.length; ++i) { names[i] = names[i].trim() }
for (let i = 0; i < names.length; ++i) { let dancer = names[i].split(" "); let sex = dancer[0]; let name = dancer[1];
if(sex == 'F') {
femaleDancers.enqueue(new Dancer(name, sex))
} else {
maleDancers.enqueue(new Dancer(name, sex))
}
}
console.log('males', femaleDancers, maleDancers) }
export function dance(males, females) {
console.log("这个舞者的伴侣时: \n");
while(!females.empty() && !males.empty()) {
let fperson = females.dequeue();
let mperson = males.dequeue();
console.log(男舞者是：${mperson.name}, 对应的女舞者是：${fperson.name})
}
console.log('') }
export function read(path) { let dancersContent = fs.readFileSync(path, { encoding: 'utf-8' }) return dancersContent } ```
- 编写测试用例
```js import { dirname, join } from "node:path"; import { fileURLToPath } from "url";
import Queue, { getDancers, read, / maleDancers, femaleDancers, /dance } from "../Queue";
const __filename = fileURLToPath(import.meta.url); const __dirname = dirname(__filename);
describe("测试舞伴匹配", () => { it("dancers", () => { let maleDancers = new Queue(); let femaleDancers = new Queue();
getDancers(maleDancers, femaleDancers);
expect(maleDancers).toMatchInlineSnapshot(Queue {
"dataStore": [
Dancer {
"name": "李四",
"sex": "M",
},
Dancer {
"name": "王五",
"sex": "M",
},
Dancer {
"name": "赵六",
"sex": "M",
},
Dancer {
"name": "周八",
"sex": "M",
},
Dancer {
"name": "郑十",
"sex": "M",
},
Dancer {
"name": "王一",
"sex": "M",
},
Dancer {
"name": "刘二",
"sex": "M",
},
],
});
expect(femaleDancers).toMatchInlineSnapshot(Queue {
"dataStore": [
Dancer {
"name": "张三(女)",
"sex": "F",
},
Dancer {
"name": "孙七(女)",
"sex": "F",
},
Dancer {
"name": "吴九(女)",
"sex": "F",
},
Dancer {
"name": "钱一(女)",
"sex": "F",
},
],
});
dance(maleDancers, femaleDancers);
expect(maleDancers).toMatchInlineSnapshot(`
Queue {
"dataStore": [
Dancer {
"name": "郑十",
"sex": "M",
},
Dancer {
"name": "王一",
"sex": "M",
},
Dancer {
"name": "刘二",
"sex": "M",
},
],
}
);
expect(femaleDancers).toMatchInlineSnapshot(
Queue {
"dataStore": [],
}
`);
});
});
```
写到这里，发现书本里面其实也是有错误存在的。所以书是用来系统学习的。真正的掌握还要看自己。
基数排序
添加三个辅助方法
```js // 可选 个位数，十位数 来排序 export const distrbute = function(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(num[i]) } } }
// 收集元素 export const collect = function(queues, nums) { let i = 0; for (let digit = 0; digit < 10; ++digit) { while (!queues[digit].empty()) { nums[i++] = queues[digit].dequeue() } } }
// 展示元素：因为使用测试用例，展示使用快照 export const dispArray = function(arr) { for (let i = 0; i < arr.length; ++i) { console.log(arr[i] + " ") } } ```
测试用例
```js
describe("基数排序测试", () => { it("基数算法", () => { let queues = []; for (let i = 0; i < 10; ++i) { queues[i] = new Queue(); }
let nums = [];
for (let i = 0; i < 10; ++i) {
nums[i] = Math.floor(Math.floor(Math.random() * 101));
}
dispArray(nums);
expect(nums).toMatchInlineSnapshot(`
[
71,
78,
61,
91,
21,
2,
24,
38,
71,
37,
]
);
distrbute(nums, queues, 10, 1);
collect(queues, nums);
(nums, queues, 10, 10);
collect(queues, nums);
expect(nums).toMatchInlineSnapshot(
[
2,
21,
24,
37,
38,
61,
71,
71,
78,
91,
]
`);
});
});
```
小结
- 理解队列，以及队列与列表的区别。列表
先进后出，队列先进先出。 - 队列特点是：从
尾部插入，从头部删除。 - 其次就是 Queue api的设：
属性和方法。 - 实现了两个示例：一个是在队列中分配舞伴，一个是基数排序。同时使用 Jest 作为测试工具（如：快照测试）。