JS Queue 队列

队列

队列（queue）是遵循先进先出（First In First Out, FIFO）的一组有序的项目，队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

队列

• 队列是一种特殊的线性表，是一种操作受限的线性表。
• 队列只能在队尾（rear）插入元素，在队首（front）删除元素。
• 队列中无元素时称为空队列
• 队列是一种先进先出（First-In-First-Out, FIFO）的数据结构

队列操作

顺序队列出队入队

• 入队（enqueue）：向队列中插入新元素，在队尾插入新元素。
• 出队（dequeue）：删除队列中的元素，删除对头的元素。
• 读取（peek）：读取对头的元素，返回对头元素。
• 队头（front/head）
• 队尾（end/rear）
• 长度（size/length）
• 清空（clear）

队列的插入和删除操作

队列机制

• 操作系统中作业、进程和线程基于队列机制调度
• 消息队列机制是在多个不同应用之间实现相互通信的一种异步传输模式

队列分类

• 顺序队列：每次插入，指针rear+1，每次删除，指针front+1。
• 循环队列

数组实现

栈使用top变量记录栈顶的位置，队列则使用front和rear分别标记队列第一个元素和最后一个元素的位置。

队列的数组实现

function Queue(){
    var items = [];

    this.enqueue = function(element){
        items.push(element);
    };
    this.dequeue = function(){
        return items.shift();
    };
    this.front = function(){
        return items[0];
    };
    this.end= function(){
        return items[items.length-1];
    };
    this.clear = function(){
        items = [];
    };
    this.isEmpty = function(){
        return items.length == 0;
    };
    this.size = function(){
        return items.length;
    };
    this.print = function(){
        console.log(items.toString());
    };
}

var queue = new Queue();
console.log(queue.isEmpty());//true

queue.enqueue('jack');
queue.enqueue('john');
queue.enqueue('camila');
queue.print();//jack,john,camila

console.log(queue.isEmpty());//false
console.log(queue.size());//3

console.log(queue.front());//jack
console.log(queue.end());//camila

queue.dequeue();
queue.print();//john,camila

队列操作

出队入队

队列实现

function enqueue(element){
    this.data.push(element);
}
function dequeue(){
    return this.data.shift();
}
function front(){
    return this.data[0];
}
function back(){
    return this.data[this.data.length-1];
}
function empty(){
    this.data.length==0;
}
function size(){
    return this.data.length;
}
function toString(){
    var string = '';
    for(var i=0; i<this.data.length; ++i){
        string += this.data[i]+'\n';
    }
    return string;
}
function Queue(){
    this.data = [];

    this.enqueue = enqueue;
    this.dequeue = dequeue;
    this.front = front;
    this.back = back;
    this.empty = empty;
    this.size = size;
    this.toString = toString;
}

/*test*/
var queue = new Queue();
queue.enqueue('meredith');
queue.enqueue('cynthia');
queue.enqueue('jennifer');
print(queue.toString());//meredith cynthia jennifer
print(queue.front());//meredith
print(queue.back());//jennifer

queue.dequeue();
print(queue.toString());//cynthia jennifer

方块舞分配

当男女来到舞池，按照性别排成两队。当舞池中有地方空出来时，选两个队列中的第一个人组成舞伴儿。他们身后的人各自向前移动一位，变成新的队首。当一堆舞伴儿迈入舞池时，主持人会大声喊出他们的名字。当一对舞伴儿走出舞池，且两排队伍中有任意一对没人时，主持人也会把这个情况告诉大家。

方块舞

方块舞人员清单

$ vim dancer.txt
F Allison McMillan
M Frank Opitz
M Mason McMillan
M Clayton Ruff
F Cheryl Ferenback
M Raymond Williams
F Jennifer Ingram
M Bryan Frazer
M David Durr
M Danny Martin
F Aurora Adney

基数排序

计算机刚出现时，程序是通过穿孔卡输入主机的，每张卡包含一条程序语句。这些穿孔卡装在一个盒子里，经过一个机械装置进行排序。这种排序基数叫做基数排序，参见Data Structures with C++(Prentice Hall)一书。

对于00~99的数字，基数排序将数据集扫描两次，第一次按个位上的数字排序，第二次按十位上的数字进行排序。每个数字根据对应位上的数值被分配在不同的盒子里。

假设有如下数字：91,46,85,15,92,35,31,22
经过基数排序第一次扫描后数字被分配到如下盒子中：
Bin0
Bin1:91,31
Bin2:92,22
Bin3
Bin4
Bin5:85,15,35
Bin6:46
Bin7
Bin8
Bin9
根据盒子的顺序，对数字第一次排序的结果是：91,31,92,22,85,15,35,46
然后根据十位上的数值再将上次排序的结果分配到不同的盒子中：
Bin0
Bin1:15
Bin2:22
Bin3:31,35
Bin4:46
Bin5
Bin6
Bin7
Bin8:85
Bin9:91,92
最后，将盒子中的数字取出，组成一个新列表，该列表即排序号的数字：15,22,31,46,85,91,92

基数排序

优先队列

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

优先队列

优先队列中元素的添加和移除是基于优先级的限制。

• 机场登机的顺序中，头等舱和商务舱乘客优先级要高于经济舱乘客。
• 医院急诊科候诊室，医生优先处理病情严重的患者，护士鉴别分类根据穿着病情严重程度放号。

实现队列优先有两种方式

• 设置优先级，然后在正确的位置添加元素
• 用入列操作添加元素，然后按照优先级移除他们。

循环队列

循环队列的一个列子是击鼓传花（HotPotato）

击鼓传花

循环队列出队入队