栈和队列是数据结构里的基本概念之一。所以今天讨论的内容是如何在JavaScript中实现一个队列。
什么是队列
顾名思义，就是排队的意思。之前看《JS高级编程》时里面好像举了一个买电影票的例子，我们排队买票，第一个人买完了票从队伍的最前面离开，新来的人要站在队伍的最后一个。
所以，在数据结构语言中，队列是一个动态的集合：其中新元素将被插入到队列的末尾(入队 ENQUEUE)；并且要从队列的头部删除元素(出队 DEQUEUE)；同时EnQueue和DeQueue是队列结构需要支持的两个主要操作。
删除的操作基于FIFO(先进先出)原则，先一步入队的元素必须先一步出队。
举一个作业调度的例子。
队列
这样的调度方式确保了任何工作都不会被遗忘或者等待太久。
如何在JS里使用队列
在JS中实现Queue的最简单的方法是将数组作为容器存储。使用Array.shift()方法可以移除并返回第一个元素，简单但并不高效。因为：
- shift()的时间复杂度是O(n)，n是队列的长度，但是DeQueue()的目标运行时间应为O(1)
- Array.prototype里的大部分操作的时间复杂度都是O(n)
- 数组是索引集合，所有的数据都被分配到内存中。如果队列过大，则每次更改都将移动大块内存以使用索引来保持数组可访问。
从时间和准确性的角度上看，数组并不是最好的存储容器，那么有比数组更好的存储容器吗？对象。JS里的一切不都是对象吗？
代码实现
- 队列的基本结构
function Queue(){
// 声明一个对象作为队列的存储容器
// 声明头尾两端的索引值
}
- EnQueue的实现
EnQueue: function(item){
// 将入队的值分配一个尾部索引
// 尾部的索引值递增
}
- DeQueue的实现
DeQueue: function(){
// 检查队列是否为空
// 获取当前的头部索引指向的值
// 删除数组头部元素
// 将下一个索引变为头部索引
// 为空则重置, 确保头尾索引不会过大
// 返回删除的值
}
function Queue(){
let storage = {},
top = 0,
end= 0;
return {
enQueue: function(item){
storage[end] = item;
end++;
},
deQueue: function(){
let size = end - top;
if (size <= 0) return undefined;
let item = storage[top];
delete storage[top];
top++;
if (top === end){
top = 0;
end = 0;
}
return item;
},
size: function(){
return end - top;
},
peek: function(){
return storage[end - 1];
},
print: function(){
let result = [];
for (let key in storage){
result.push(storage[key]);
}
return result;
}
}
}
现在，访问Object的属性需要O(1)时间，因此EnQueue和DeQueue方法每个都将花费固定的时间，不会因队列大小的变化而变化。
