javaScript --- 队列学习

队列是一种列表，不同的是队列只能在队尾插入元素，在队首删除元素。

队列用于存储按顺序排列的数据，先进先出，这点和栈不一样，在栈中，最后入栈的元素反而被优先处理。

队列是一种先进先出(First-In-First-Out，FIFO)的数据结构。

队列被用在很多地方，比如提交操作系统执行的一系列进程、打印任务池等，一些仿真系统用队列来模拟银行或杂货店里排队的顾客。

1 对队列的操作

队列的两种主要操作是:向队列中插入新元素和删除队列中的元素。也叫入队和出队

队列的另外一项重要操作是读取队头的元素。这个操作叫做 peek()。该操作返回队头元素，但不把它从队列中删除。

2 一个用数组实现的队列

function Queue() {
    this.dataStore = [];
    this.enqueue = enqueue;
    this.dequeue = dequeue;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
}
// 向队尾添加一个元素enqueue
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() {
    if (this.dataStore.length == 0) {
        return true;
    }
    else {
        return false;
    }
}

模拟方块舞

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;
}
// 向队尾添加一个元素enqueue
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() {
    if (this.dataStore.length == 0) {
        return true;
    }
    else {
        return false;
    }
}
// 显示元素的个数
function count() {
    return this.dataStore.length;
}

// var q = new Queue();
// q.enqueue("Meredith");
// q.enqueue("Cynthia");
// q.enqueue("Jennifer");
// print(q.toString());
// q.dequeue();
// print(q.toString());
// print("Front of queue: " + q.front());
// print("Back of queue: " + q.back());

// 方块舞
// 舞者的姓名被从文件读入数组。然后 trim() 函数除去了每行字符串后的空格
// 。第二个循环将 每行字符串按性别和姓名分成两部分存入一个数组。然后根据性别，将舞者加入不同的队列。
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++) {
        names[i] = names[i].trim();
    }
    for (var i = 0; i < names.length; ++i) {
        var dancer = names[i].split(" ");
        var sex = dancer[0];
        var name = dancer[1];
        if (sex == "F") {
            females.enqueue(new Dancer(name, sex));
        }
        else {
            males.enqueue(new Dancer(name, sex));
        }
    }
}

function dance(males, females) {  // 进行匹配
    print("The dance partners are: \n");
    while (!females.empty() && !males.empty()) {
        person = females.dequeue();
        putstr("Female dancer is: " + person.name);
        person = males.dequeue();
        print("--------------and the male dancer is: " + person.name);
    }
    print();
}

var maleDancers = new Queue();
var femaleDancers = new Queue();
getDancers(maleDancers, femaleDancers);
dance(maleDancers, femaleDancers);
if (maleDancers.count() > 0) {
    print("There are " + maleDancers.count() + " male dancers waiting to dance.");
}
if (femaleDancers.count() > 0) {
    print("There are " + femaleDancers.count() + " female dancers waiting to dance.");
}

使用队列对数据进行排序

队列不仅用于执行现实生活中与排队有关的操作，还可以用于对数据进行排序。计算机刚刚出现时，程序是通过穿孔卡输入主机的，每张卡包含一条程序语句。这些穿孔卡装在一个盒子里，经一个机械装置进行排序。我们可以使用一组队列来模拟这一过程。这种排序技术叫做基数排序，参见 Data Structures with C++(Prentice Hall)一书。它不是最快的排序算法，但是它展示了一些有趣的队列使用方法。

基数排序

对于 0~99 的数字基数排序

// 使用队列代表盒子，可以实现这个算法。我们需要九个队列，每个对应一个数字。将所有 队列保存在一个数组中，使用取余和除法操作决定个位和十位。算法的剩余部分将数字加 入相应的队列，根据个位数值对其重新排序，然后再根据十位上的数值进行排序，结果即 为排好序的数字。
// 下面是根据相应位(个位或十位)上的数值，将数字分配到相应队列的函数
function distribute(nums, queues, n, digit) {  参数 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();
        }
    }
}
function dispArray(arr) {
    for (var i = 0; i < arr.length; ++i) {
        putstr(arr[i] + " ");
    }
}

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.floor(Math.random() * 101));
}
print("Before radix sort: ");
dispArray(nums);
distribute(nums, queues, 10, 1);
collect(queues, nums);
distribute(nums, queues, 10, 10);
collect(queues, nums);
print("\n\nAfter radix sort: ");
dispArray(nums);

下面是程序运行几次的结果:

     Before radix sort:
     45 72 93 51 21 16 70 41 27 31

     After radix sort:
     16 21 27 31 41 45 51 70 72 93

     Before radix sort:
     76 77 15 84 79 71 69 99 6 54

     After radix sort:
     6 15 54 69 71 76 77 79 84 99

优先队列

在一般情况下，从队列中删除的元素，一定是率先入队的元素。但是也有一些使用队列的应用，在删除元素时不必遵守先进先出的约定。这种应用，需要使用一个叫做优先队列的数据结构来进行模拟。

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;
}
// 向队尾添加一个元素enqueue
function enqueue(element) {
    this.dataStore.push(element)
}
// 删除对首的元素
// function dequeue() {
//     return this.dataStore.shift()
// }
//dequeue() 方法使用简单的顺序查找方法寻找优先级最高的元素(优先码越小优先级越高， 比如，1 比 5 的优先级高)。该方法返回包含一个元素的数组——从队列中删除的元素。
function dequeue() {
    var priority = this.dataStore[0].code;
    for (var i = 1; i < this.dataStore.length; ++i) {
        if (this.dataStore[i].code < priority) {
            priority = i;
        }
    }
    return this.dataStore.splice(priority, 1);
}

// 读取队首
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 toString() {
    var retStr = "";
    for (var i = 0; i < this.dataStore.length; ++i) {
        retStr += this.dataStore[i].name + " code: " + this.dataStore[i].code + "\n";
    }
    return retStr;
}
// 判断队列是否为空
function empty() {
    if (this.dataStore.length == 0) {
        return true;
    }
    else {
        return false;
    }
}
// 显示元素的个数
function count() {
    return this.dataStore.length;
}

function Patient(name, code) {
    this.name = name;
    this.code = code;
}

var p = new Patient("Smith", 5);
var ed = new Queue();
ed.enqueue(p);
p = new Patient("Jones", 4);
ed.enqueue(p);

p = new Patient("Fehrenbach", 6);
ed.enqueue(p);
p = new Patient("Brown", 1);
ed.enqueue(p);
p = new Patient("Ingram", 1);
ed.enqueue(p);
print(ed.toString());
var seen = ed.dequeue();
print("Patient being treated: " + seen[0].name);
print("Patients waiting to be")
print(ed.toString());

// 下一轮
var seen = ed.dequeue();
print("Patient being treated: " + seen[0].name);
print("Patients waiting to be seen :")
print(ed.toString())
// 输出
// Smith code: 5
// Jones code: 4
// Fehrenbach code: 6
// Brown code: 1
// Ingram code: 1

// Patient being treated: Jones
// Patients waiting to be
// Smith code: 5
// Fehrenbach code: 6
// Brown code: 1
// Ingram code: 1

// Patient being treated: Ingram
// Patients waiting to be seen:
// Smith code: 5
// Fehrenbach code: 6
// Brown code: 1

总结：优先队列有点迷糊似懂非懂练习题做完以后再回顾写