前言
前面讲过使用js模拟栈的算法，今天主要讲，使用js模拟队列的算法，为什么要这样做呢？说实话是闲的无聊，现在处于一个项目空档期，为了不至于太无聊，就想把数据结构里面的算法都使用js模拟一遍。
队列
1、什么是队列？
想象中午食堂吃饭时、等电梯时、早晚高峰进地铁时，都需要排队。那么肯定是先排队的有优先权，然后依次进入。队列也是这个道理，只有一个出口，一个入口，特点是先进先出，这和栈的思想相反。明白了队列的特点，分析如何使用js实现队列？
队列有一个入口，取名为enqueue;出口取名为dequeue;正常情况下，还需要读取队首和队尾元素，命名为front和back，读取队列所有元素，命名为toStringData, 判断队列是否空，命名为isEmpty。现在可以完成队列的构造函数了，如下：
function Queue() {
this.data = [];
this.enqueue = enqueue; //队尾添加一个元素
this.dequeue = dequeue; //队首删除一个元素
this.front = front; //读取队首元素
this.back = back; //读取队尾元素
this.toStringData = toStringData; //显示队内元素
this.isEmpty = isEmpty; //判断队列是否为空
}
2、使用enqueue()方法，在队尾添加一个元素，如下：
function enqueue(element) {
this.data.push(element);
}
3、使用dequeue()方法，在队首删除一个元素，并返回删除的值，如下：
function dequeue() {
return this.data.shift();
}
4、使用front()方法，返回队首元素，如下：
function front() {
return this.data[0];
}
5、使用back()方法，返回队尾元素，如下：
function back() {
return this.data[this.data.length - 1];
}
6、使用toStringData()方法，返回队列元素，如下：
function toStringData() {
let queueString = '';
for (let i = 0; i < this.data.length; i++) {
queueString += this.data[i] + '\n';
}
return queueString;
}
7、使用isEmpty()方法，判断队列是否为空，如下：
function isEmpty() {
return this.data.length === 0;
}
到这里，就使用js实现了一个单向队列。
实例
1、使用队列进行排序（基数排序）
首先介绍下什么是基数排序，基数排序又叫分配式排序或桶子法，它是通过数据的部分信息，将要排序的元素分配至桶中，以达到排序的作用。
假设有一串数值，如下所示：
98、25、31、10、99、81、65、42、51
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：
0： 10
1： 31 81 51
2： 42
3：
4：
5： 25 65
6：
7：
8： 98
9： 99
接下来将这些桶子中的数值串接起来，如下所示：
10 31 81 51 42 25 65 98 99
接着根据十位数在进行一次分配，如下所示：
0：
1： 10
2： 25
3： 31
4： 42
5： 51
6： 65
7：
8： 81
9： 98 99
接下来将这些数值串接起来，形成以下数值：
10 25 31 42 51 65 81 98 99
这时候排序已经完成；如果有三位数或这更高位数，则持续进行以上动作，直至最高位为止。
如何使用队列的思想进行排序呢？假设是0～99间的数进行比较，首先需要比较个位数，因为数值在0～99之间，只需对数进行取余,即可得到个位数，对数值除以10，向下取整可得到十位数。到这儿开始使用队列(桶)进行存值，需要是个队列分别存储0～9的值。如下：
/**
* @param nums 初始数组
* @param queue 队列数组
* @param n 几位数
* @param digit 个位数或十位以上的数
* */
function distribute (nums, queue, n, digit) {
for (let i = 0; i < n; i++) {
if (digit === 1) {
queue[nums[i] % 10].enqueue(nums[I]);
} else {
queue[Math.floor(nums[i] / 10)].enqueue(nums[I]);
}
}
}
基数排序后展示函数，如下：
/**
* @param queues 队列数组
* @nums nums 初始数组
* */
function showAfterData (queues, nums) {
let i = 0;
for (let digit = 0; digit < 10; ++digit) {
while (!queues[digit].isEmpty()) {
nums[i++] = queues[digit].dequeue();
}
}
return nums;
}
完成算法后，随机来点数实验下，如下：
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));
}
console.log('个位数排序：');
distribute(nums, queues, 10, 1);
console.log(collect(queues, nums));
console.log('十位数排序：');
distribute(nums, queues, 10, 10);
console.log(collect(queues, nums));
结果如下：
基数排序结果
双向队列
双向队列即队列的首尾都能进能出，那么只需在单向队列中添加两个方法，队首添加一个元素方法(fenqueue)，队尾删除一个元素的方法('bdequeue'),即可.
队列的构造函数添加两个方法，如下：
function Queue() {
this.data = [];
this.enqueue = enqueue; //队尾添加一个元素
this.dequeue = dequeue; //队首删除一个元素
`this.fenqueue = fenqueue; //队首添加一个元素`
`this.bdequeue = bdequeue; //队尾删除一个元素`
this.front = front; //读取队首元素
this.back = back; //读取队尾元素
this.toStringData = toStringData; //显示队内元素
this.isEmpty = isEmpty; //判断队列是否为空
}
function fenqueue (element) {
this.data.unshift(element);
}
function bdequeue () {
return this.data.pop();
}
现在就完成了双向队列。双向队列能实现什么功能呢？如回文之类的使用双向队列能很方便的实现，思想如上一片文章中的栈，使用双向队列无论从前还是后插入数据，都一个原理。
网友评论