- 定义
队列是遵循FIFO(First In First Out,先进先出)原则的一组有序的项。
在现实中,最常见的队列的例子就是排队:
- 创建队列
- 声明类并声明一个数组用于存储队列中元素的数据结构。
function Queue() {
var items = [];
//这里是属性和方法
}
- 实现enqueue()方法,向队列尾部添加数个新的项。
this.enqueue = function(element) {
//用push方法,将元素添加到数组末尾
items.push(element);
};
- 实现dequeue()方法,移除队的第一项(队首),并返回被移除的元素。
this.dequeue = function() {
//shift方法,移除数组中的第一项(索引为0)的元素
return items.shift();
};
- front()方法,返回队列中的第一个元素,不改变队列。
this.front = function() {
return items.shift();
};
- isEmpty()方法,如果队列中不包含任何元素,返回true,否则返回false。
this.isEmpty = function() {
return items.length == 0;
};
- clear()方法,清空队列元素
this.clear = function() {
items = [];
};
- size()方法,返回队列包含的元素个数。
this.size = function(){
return items.lenght;
};
- 完整代码如下
function Queue() {
var items = [];
this.enqueue = function(element) {
items.push(element);
};
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.toString());
}
}
var queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.print(); // "1,2"
- 优先队列
现实生活中也有优先队列,如头等舱>商务舱>经济舱,接下来我们用代码实现下优先队列。
function PriorityQueue() {
//声明一个items用于保存元素
var items = [];
//创建一个QueueElement类,用于保存元素和其在队列中的优先级(priority越小,优先级越高)
function QueueElement(element,priority) {
this.element = element;
this.priority = priority;
}
this.enqueue = function(element,priority) {
var queueElement = new QueueElement(element,priority);
//如果队列为空,可以将元素入列
if(this.isEmpty()) {
items.push(queueElement);
}else {
var added = false;
//反之就循环队列里面的每一个元素,比较优先级,如果priority小(优先级越高)的话,就用splice()方法放在该元素的前面
for(var i=0; i<items.length; i++) {
if(queueElement.priority < items[i].priority) {
items.splice(i,0,queueElement);
added = true;
break;
}
}
//如果添加的元素的priority比队列中的每一个元素都要大的话,就把它添加到队列的最后面
if(!added) {
items.push(queueElement);
}
}
};
this.isEmpty = function() {
return items.length === 0;
};
this.print = function() {
console.log(items);
};
}
var priorityQueue = new PriorityQueue();
priorityQueue.enqueue("one",1);
priorityQueue.enqueue("two",2);
priorityQueue.enqueue("zero",0);
priorityQueue.enqueue("four",4);
priorityQueue.print(); // "0,1,2,4"
- 循环队列
循环队列的一个例子就是击鼓传花游戏(HotPotato)。在这个游戏中,孩子们围成一个圆圈,把花尽快地传递给旁边的人。某一时刻传花停止,这个时候花在谁手里,谁就退出圆圈结束游戏。重复这个过程,直到只剩一个孩子(胜者)。
function hotPotato(nameList,num) {
var queue = new Queue();
//将传入的nameList遍历,将每一项添加到队列中
for(var i=0; i<nameList; i++) {
queue.enqueue(nameList[i]);
}
var eliminated = '';
//如果队列里的size大于1,就一直循环下去
while(queue.size() > 1) {
//将第一项放到最后一项,循环给定的num
for(var i=0; i<num; i++) {
queue.enqueue(queue.dequeue);
}
//传递次数达到了给定的数值,(移除第一项)
eliminated = queue.dequeue();
console.log(eliminated + '淘汰');
}
//返回队列中仅有的最后一项
return queue.dequeue();
}
var names = ['a','b','c','d','e'];
var winner = hotPotato(names,7);
console.log('胜利者' + winner);
参考学习 :
《javascript数据结构与算法学习》
《数据结构与算法javascript描述》