閱讀《資料結構與演算法 JavaScript 描述 第二版》之佇列

語言: CN / TW / HK

概述

  • 資料尾部進入
  • 資料頭部移除

特點

  • 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 作為測試工具(如:快照測試)。