阅读《数据结构与算法 JavaScript 描述 第二版》之队列

概述

• 数据尾部进入
• 数据头部移除

特色

• First-In-First-Out 先进后出

完成一个简单的行列

完成一个简单的行列数据类型（基于数组）

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

npm install jest
$ ./node_modules/jest/bin/jest.js --init # 运用 jest 提供的指令主动初始化

考虑到现在 es module 现已开始遍及，此刻运用 esm 比较合适，在初始化的时候注意选择与 esm 的选项。同时 package.json 的内容中：

{
    "type": "module",
}

• 测验用例中，运用测验套件 describe/测验用例 it， 运用 spec 符号是测验文件

测验用例

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(`"王五"`)
  })
})

三个示例

• 方块舞的舞伴分配问题

方块舞的舞伴分配问题

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;
}

• 完成跳舞人分配

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
}

• 编写测验用例

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": [],
}
`);
  });
});

写到这里，发现书本里边其实也是有过错存在的。所以书是用来体系学习的。真正的掌握还要看自己。

基数排序

添加三个辅佐办法

// 可选 个位数，十位数 来排序
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] + " ")
  }
}

测验用例

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 作为测验工具（如：快照测验）。