阅读 6

数据结构与算法-队列(Queue)

百度百科解释:队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

队列也是一种列表,队列用于存储按顺序排列的数据,先进先出(First-In-First-Out, FIFO),可以想象成银行前排队的人群。

使用数组实现队列

javascript中的数组具有其它编程语言中没有的优点,数组的push()可以在数组的末尾加入元素,shift()可以删除数组的第一个 元素。

function Queue () {
    this.dataStore = []
}
Queue.prototype = {
    constructor: Queue,
    // 向对位添加一个元素
    enqueue: function (element) {
        this.dataStore.push(element)
    },
    // 删除队首元素
    dequeue: function () {
        return this.dataStore.shift()
    },
    // 读取队首元素
    front: function () {
        return this.dataStore[0]
    },
    // 读取队尾元素
    back: function () {
        return this.dataStore[this.dataStore.length - 1]
    },
    // 显示队列内的所有元素
    toString: function () {
        var retStr = ''
        for (var i = 0; i < this.dataStore.length; i++) {
            retStr += this.dataStore[i] + '\n'
        }
        return retStr
    },
    // 判断队列是否为空
    empty: function () {
        if (this.dataStore.length === 0) {
            return true
        } else {
            return false
        }
    }
}
复制代码

使用队列对数据进行排序

计算机刚出现时,程序是通过穿孔卡输入主机的,每张卡包含一条程序语句。这些穿孔卡装在一个盒子里,经过一个机械装置进行排序。我们可以使用一组队列来模拟这一过程,这种排序技术叫做基数排序,它不是最快的排序算法,但是它展示了一些有趣的队列使用方法。

具体方法实现: 对0-99的数字,基数排序将数据集扫描两次。第一次按个位上的数字进行排序,第二次按十位上的数字进行排序,每个数字根据对应位上的数值被分在不同的盒子里。

假设有如下数字:91, 46, 85, 15, 92, 35, 31, 22

// 第一次按个位上扫描排序
box0: 
box1: 91, 31
box2: 92, 22
box3: 
box4: 
box5: 85, 15, 35
box6: 46
box7: 
box8:
box9
复制代码

排序后结果为:91, 31, 92, 22, 85, 15, 35, 46

box0:
box1: 15
box2: 22
box3: 31, 35
box4: 46
box5:
box6:
box7:
box8: 85
box9: 91, 92
复制代码

排序后结果为:15, 22, 31, 35, 46, 85, 91, 92

// 可以想象成上体育课时老师组队时,其实也是一种算法

使用队列代表盒子,可以实现这种算法。我们需要9个队列,每个对应一个数字,将所有队列保存在一个数组中,使用取余和除法操作决定个位和十位,根据算法的剩余部分将数字加入相应的队列。

// 根据相应位(个位,十位)上的数值,将数字分配到相应队列
function distribute (nums, queues, n, digit) {
    for (var i = 0; i < n; i++) {
        if (digit === 1) {
            queues[nums[i] % 10].enqueue(nums[i])
        } else {
            queues[Math.floor(nums[i] / 10)].enqueue(nums[i])
        }
    }
}

// 从队列中收集数字
function collect (queues, nums) {
    var i = 0
    for (var digit = 0; digit < 10; digit++) {
        while (!queues[digit].empty()) {
            nums[i++] = queues[digit].dequeue()
        }
    }
}

// 主程序
var queues = []
for (var i = 0; i < 10; i++) {
    queues[i] = new Queue()
}
var nums = []
for (var j = 0; j < 10; j++) {
    nums[j] = Math.floor(Math.floor(Math.random() * 101))
}
console.log('before')
console.log(nums)
distribute(nums, queues, 10, 1)
collect(queues, nums)
distribute(nums, queues, 10, 10)
collect(queues, nums)
console.log('after')
console.log(nums)
复制代码

队列和栈一样也是一种思想,比如提交操作系统执行的一系列进程,打印任务池等就要用到队列。一个名词在一种陌生环境内我们会感到很神奇,比如直接说计算机中的队列我们会感觉很高深,映射成生活中的例子我们就能理解了。当然这些术语,词,概念都是人为的抽象,人的高度概况。数学中的总总知识点,我们刚开始学的时候很难理解,因为没有使用语境带入,但是总有聪明人能完美使用,还能总结出新的知识,创造出新的东西,计算机就是人为知识的结晶,还能把我们的思想赋予计算机,随着科技的发展,计算机也会有思想的那一天。

关注下面的标签,发现更多相似文章
评论