js-实现数据结构-队列

2018-12-18 本文已影响0人 ChicAboo

前言

前面讲过使用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

接着根据十位数在进行一次分配，如下所示：

接下来将这些数值串接起来，形成以下数值：

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

现在就完成了双向队列。双向队列能实现什么功能呢？如回文之类的使用双向队列能很方便的实现，思想如上一片文章中的栈，使用双向队列无论从前还是后插入数据，都一个原理。