本文共--字 阅读约--分钟 | 浏览: -- Last Updated: 2021-04-22
队列是一种列表，不同的是队列只能在队尾插入元素，在队首删除元素。队列用于存储按顺序排列的数据，一种先进先出(First-In-First-Out, FIFO)的数据结构，可以将队列想象成在银行前排队的人群，排在最前面的人第一个办理业务，新来的人只能在后面排队，直到轮到他们为止。
队列的两种主要操作是：向队列中插入新元素和删除队列中的元素，插入的操作也叫入队，删除操作也叫出队，入队操作在队尾插入新元素，出队操作删除队头的元素。另外一项重要操作是读取队头的元素 peek，使用 clear 方法可以清空队列。
在JavaScript使用数组能够很简单的实现队列。
function Queue() {
this.dataStore = [];
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
this.count = count;
}
// 入队
function enqueue(element) {
this.dataStore.push(element)
}
// 出队
function dequeue() {
return this.dataStore.shift()
}
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] + '\n';
}
return retStr;
}
function empty() {
return this.dataStore.length === 0;
}
function count() {
return this.dataStore.length;
}
// example 1
var q = new Queue();
q.enqueue('Meredith')
q.enqueue('Cynthia')
q.enqueue('Jennifer')
console.log(q.toString());
// Meredith
// Cynthia
// Jennifer
q.dequeue()
console.log(q.toString());
// Cynthia
// Jennifer
console.log('Front of queue: ' + q.front());
console.log('Back of queue: ' + q.back());
// Front of queue: Cynthia
// Back of queue: Jennifer
场景：当男男女女来到舞池，他们按照自己的性别排成两队，当舞池中有地方空出来时，选两个队列中的第一个人组成舞伴。他们身后的人各自向前移动一位，变成新的队首。当一队舞伴迈入舞池时，主持人会大声喊出他们的名字。当一队舞伴走出舞池，且两排队伍中有任意一队没人时，主持人也会把这个情况告诉大家。
将跳舞的人员的姓名存储在一个文本文件中 dancers.txt:
F Allison
M Frank
M Mason
M Clayton
F Cheryl
M Raymond
F Jennifer
M Bryan
M David
M Danny
F Aurora
代码实现：
const fs = require('fs')
function read(path) {
var res = fs.readFileSync(path, 'utf-8')
return res;
}
function Dancer(name, sex) {
this.name = name;
this.sex = sex;
}
function getDancers(males, females) {
var names = read('dancers.txt').split('\n')
for (var i = 0; i < names.length; ++i) {
var [sex, name] = names[i].trim().split(' ');
if (sex === 'F') {
females.enqueue(new Dancer(name, sex))
} else {
males.enqueue(new Dancer(name, sex))
}
}
}
function dance(males, females) {
var person
console.log('The dance partners are: \n');
while (!males.empty() && !females.empty()) {
// 输出当前跳舞的男士和女士是谁
person = females.dequeue()
console.log('Female dancer is: ' + person.name);
person = males.dequeue()
console.log('and the male dancer is: ' + person.name + '\n');
}
}
var maleDancers = new Queue();
var femaleDancers = new Queue();
getDancers(maleDancers, femaleDancers)
dance(maleDancers, femaleDancers)
// 组队完毕之后，如果还有人在排队，打印还有多少位正在等待
if (maleDancers.count() > 0) {
console.log(`There are ${maleDancers.count()} male dancers waiting do dance .`);
}
if (femaleDancers.count() > 0) {
console.log(`There are ${femaleDancers.count()} female dancers waiting do dance .`);
}
// 执行结果
// The dance partners are:
// Female dancer is: Allison
// and the male dancer is: Frank
// Female dancer is: Cheryl
// and the male dancer is: Mason
// Female dancer is: Jennifer
// and the male dancer is: Clayton
// Female dancer is: Aurora
// and the male dancer is: Raymond
// There are 3 male dancers waiting do dance .
对于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, 46, 85, 91, 92
代码实现如下：
// 创造十个盒子
var queues = [];
for (var i = 0; i < 20; i++) {
queues.push(new Queue())
}
// 随机创造20个0~99中的数字组成数组
var nums = []
for (var i = 0; i < 20; i++) {
nums.push(Math.floor(Math.random() * 100))
}
/**
* 进行基数排序
*
* @param {number[]} nums 需要排序的数组
* @param {Queue[]} queues 用来存储排序结果的“盒子” 由10个Queue组成
* @param {1|10} digit 用来分别当前是根据个位排序还是根据十位排序
*/
function distribute(nums, queues, digit) {
for (var i = 0; i < nums.length; i++) {
if (digit === 1) {
// 根据个位排序
// nums[i] % 10 即取出当前数字的个位
// 个位是几 就将该数入队到第几个盒子(Queue)
var index = nums[i] % 10;
queues[index].enqueue(nums[i])
} else {
// 根据十位排序
// Math.floor(nums[i] / 10) 取出数字的十位
// 十位是几 就将该数入队到第几个盒子(Queue)
var index = Math.floor(nums[i] / 10)
queues[index].enqueue(nums[i])
}
}
}
/**
* 用来将 基数排列过的数字 按顺序从十个盒子(Queue)中取出并排列在nums中
*
* @param {Queue[]} queues
* @param {number[]} nums
*/
function collect(queues, nums) {
var i = 0;
for (var j = 0; j < queues.length; j++) { // 外循环用来处理一个个的盒子
while(!queues[j].empty()) { // 内循环用来确保取空当前盒子(Queue)
nums[i++] = queues[j].dequeue();
}
}
}
// 展示数组
function displayArray(arr) {
console.log(arr.join(', '));
}
console.log('Before radix sort:');
displayArray(nums)
// 进行个位排序
distribute(nums, queues, 1)
// 按顺序取出并形成新的数组
collect(queues, nums)
// 进行十位排序
distribute(nums, queues, 10)
// 按顺序取出并形成新的数组
collect(queues, nums)
console.log();
console.log('After radix sort:');
displayArray(nums)
// Before radix sort:
// 49, 58, 41, 12, 97, 10, 46, 49, 49, 62, 4, 70, 87, 21, 57, 87, 40, 51, 53, 88
// After radix sort:
// 4, 10, 12, 21, 40, 41, 46, 49, 49, 49, 51, 53, 57, 58, 62, 70, 87, 87, 88, 97
在一般情况下，从队列中删除的元素，一定是率先入队的元素。但是也有一些使用队列的应用，在删除元素时不必遵守先进先出的约定，这种情况需要使用到优先队列。
从优先队列时删除元素时，需要考虑优先权的限制，比如医院急诊科的候诊室，就是一个采取优先队列的例子，当病人进入后候诊室时，分诊护士会评估患者病情的严重程度，然后给一个优先级代码，高优先级的患者优先就医，同来的优先级按照先来先服务的顺序就医。
// 病人类，拥有姓名和优先级，code越小 优先级越高
function Patient(name, code) {
this.name = name;
this.code = code;
}
// 使用组合继承 让优先队列继承于普通队列
function PriorityQueue() {
}
// 继承
PriorityQueue.prototype = new Queue()
PriorityQueue.prototype.constructor = PriorityQueue;
// 定义自己的dequeue逻辑，按照优先级进行出队操作
PriorityQueue.prototype.dequeue = function () {
var entry = 0;
// 找出最小的code
for (var i = 1; i < this.dataStore.length; ++i) {
if (this.dataStore[i].code < this.dataStore[entry].code) {
entry = i;
}
}
// 对其进行出队操作
return this.dataStore.splice(entry, 1)
}
// 定义自己的toString
PriorityQueue.prototype.toString = function () {
var retStr = ''
for (var i = 0; i < this.dataStore.length; i++) {
retStr += `${this.dataStore[i].name} code: ${this.dataStore[i].code} \n`
}
return retStr;
}
var pq = new PriorityQueue()
// 在队列中添加不同优先级的病人
var p = new Patient('Smith', 5)
pq.enqueue(p)
p = new Patient('Jones', 4)
pq.enqueue(p)
p = new Patient('Fehrenbach', 6)
pq.enqueue(p)
p = new Patient('Brown', 1)
pq.enqueue(p)
p = new Patient('Ingram', 1)
pq.enqueue(p)
console.log('Patient List:');
console.log(pq.toString());
var seen = pq.dequeue();
console.log('Patient being treated: ' + seen[0].name);
console.log('Patient waiting to be seen: ');
console.log(pq.toString());
var seen = pq.dequeue();
console.log('Patient being treated: ' + seen[0].name);
console.log('Patient waiting to be seen: ');
console.log(pq.toString());
var seen = pq.dequeue();
console.log('Patient being treated: ' + seen[0].name);
console.log('Patient waiting to be seen: ');
console.log(pq.toString());
// Patient List:
// Smith code: 5
// Jones code: 4
// Fehrenbach code: 6
// Brown code: 1
// Ingram code: 1
// Patient being treated: Brown
// Patient waiting to be seen:
// Smith code: 5
// Jones code: 4
// Fehrenbach code: 6
// Ingram code: 1
// Patient being treated: Ingram
// Patient waiting to be seen:
// Smith code: 5
// Jones code: 4
// Fehrenbach code: 6
// Patient being treated: Jones
// Patient waiting to be seen:
// Smith code: 5
// Fehrenbach code: 6