学习Javascript数据结构与算法 — 队列

<b><em>代码运行环境：任何可以运行Javascript的环境即可。</em></b>

第一章：队列

1. 什么是队列？

<b>特性：先进去的元素，肯定先出队列。（ FIFO ）
生活中最常见的就是排队买车票。</b>

队列是一种特殊的线性表；
最开始的队列总是空的
它只允许在表的前端（front）进行删除操作；
而在表的后端（rear）进行插入操作；
队列是一种操作受限制的线性表；
进行插入操作的端称为队尾（ 入队 ）；
进行删除操作的端称为队头 ( 出队 )；
第一个插入的元素就是队头；

说到队列，肯定需要提到的是数组，数组在Javascript里是可修改的对象，以下是数组的一些核心方法：

1. concat(item1,item2,...,itemN) 合并一个或者多个数组 返回结果
2. push(item) 往数组最后面添加一个或多个元素，使用：“ , ” 分开参数。
3. pop() 从数组最后面，移除一个元素，并返回这个值
4. shift() 函数删除数组第一个元素，并返回这个值
5. unshift(item1,item2,...,itemN) 向数组的开头添加一个或更多元素，并返回数组更新后的长度。
6. slice(startIndex,endIndex) 从已有的数组中返回选定的元素。
7. splice(index,deleteNumber,item1...) 方法向/从数组中添加/删除项目，然后返回被删除的项目。
8. ...

2.实现

<code>
//我们创建一个类（函数）用来 表示队列
/*
我们将实现以下方法：
enqueue() 入队
dequeue () 出队
front () 返回队头
isEmpty() 队列是否为空
clear() 清空队列
size() 返回这个队列的长度
print() 打印队列所有元素
*/
function Queue(){
var items =[];
this.enqueue = function(elements){
items.push(elements); //入队，第一个进入的是队头，所以之后入队的元素应该是往后添加。
}
this.dequeue = function(){
return items.shift() //出队，一个入队的应该最先出队，所以应该删除第一个元素
}
this.front = function(){
return items[0]; //获取队头，返回第一个入队的元素
}
this.isEmpty = function(){
return items.length == 0;
}
this.clear = function(){
items = [];
}
this.size = function(){
return items.length;
}
this.print = function(){
console.log(items);
}
}

var newQueue = new Queue();
newQueue.enqueue(5); // [5]
newQueue.enqueue(8); //[5,8]
newQueue.enqueue(10); //[5,8,10]
newQueue.dequeue() //[8,10];
newQueue.isEmpty() // false
</code>
...

3. 队列的实现主要依靠数组，所以了解和学会数组的核心方法是很有必要的。

4. 接下来我们学习优先队列。普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。

—— END ——