数据结构-队列

发表于 | 分类于 |

chapter-5 队列

特性

  • 一种列表
  • 只能在队尾插入元素，队首删除元素
  • 存储按顺序排列的数据，先进先出（FIFO）
  • 用于提交操作系统执行的一系列进程

主要操作

  • 插入（入队）- 队尾插入新元素
  • 删除（出队）- 删除队头元素
  • 读取队头元素 - peek
  • 存储多少元素 - length
  • 清空所有元素 - clear

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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 () {
        return this.dataStore;
    },
    // 判断是否为空
    empty: function () {
        return this.dataStore.length === 0;
    }
}

测试结果：

使用

方块舞的舞伴分配问题

基数排序

  • 9个队列，每个对应1-9每个数字，所有队列保存在一个数组里，使用取余和除法操作决定个位和十位。先根据个位数值对其排序，在根据十位数字排序呢，结果即为排序好的数字
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    /**
     * 分配函数
     * @param {array[num]} nums 排序数字数组
     * @param {array} queues 队列数组，每一项代表分配的基数数字
     * @param {int} n 进制 
     * @param {int} digit 当前位数，1：个位、10：十
     */
    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]);
            }
        }   
    }
    /**
     * 出队收集
     * @param {array} queues 队列数组
     * @param {array} nums 排序数组
     */
    function collect(queues, nums) {
        // debugger
        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 i = 0; i < 10; i++) {
        nums[i] = Math.floor(Math.random() * 100);
    }
    console.log('原始数据：' + nums);
    // 个位分布排序
    distribute(nums, queues, 10, 1);
    collect(queues, nums);
    console.log('个位排序后数据：' + nums);
    // 十位分布排序
    distribute(nums, queues, 10, 10);
    collect(queues, nums);
    console.log('十位排序后数据：' + nums);
test 结果

优先队列

  • 一般情况下，队列中删除的元素遵循先入先出的原则。
  • 可以实现一个按优先权重限制的队列，高优先级先出，同优先级按先入先出处理。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    /**
     * 存储队列元素
     * @param {*} name 
     * @param {int} code 表示优先级
     */
    function Patient (name, code) {
        this.name = name;
        this.code = code;
    }
    // 重新定义dequeue函数
    // 顺序查找方法寻找优先级最高的元素（code越小，优先级越高）
    function dequeue () {
        var entry = 0;
        for (var i = 0; i < this.dataStore.length;i++) {
            if (this.dataStore[i].code < this.dataStore[entry].code) {
                entry = i;
            }
        }
        return this.dataStore.splice(entry, 1);
    }
    Queue.prototype.dequeue = dequeue;
    // 主程序
    var ed = new Queue();
    // 数据
    var data = [
        ['Smith', 5],
        ['Jones', 4],
        ['Fehrenbach', 6],
        ['Brown', 1],
        ['Ingram', 1]
    ];
    // 入队
    for (var dd = 0; dd < data.length; dd++) {
        var p = new Patient(data[dd][0], data[dd][1]);
        ed.enqueue(p);
    }
    console.log('初始数据：' + JSON.stringify(ed.dataStore));
    // 出队
    var index = 0;
    while (!ed.empty()) {
        var seen = ed.dequeue();
        // debugger
        data[index++] = seen[0];
    }
    console.log('排序后数据：' + JSON.stringify(data));