数据结构-队列

队列的特性

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队的元素遵循先进先出的原则。
如图:

实现思路

通过使用javascript提供的数组实现队列先进先出的特性,同时实现队列的大小,是否为空,添加、删除等基本功能,即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
var Queue = function(){
// 保存数据
var items = [];

/** 入队列 */
this.enQueue = function(element){
items.push(element);
}

/** 出队列 */
this.deQueue = function(){
return items.shift();
}

/** 队列顶 */
this.front = function(){
return items[0];
}

/** 队列大小 */
this.size = function(){
return items.length;
}

/** 是否为空 */
this.isEmpty = function(){
return items.length === 0
}

/** 队列内容 */
this.values = function(){
return items;
}
}

循环队列

小时候都玩过丢手绢,m个人围一圈,从一个人开始数数,数到n的时候,即数到这个数的人出局,一直淘汰直到最后剩下最后一个人,则这个人就是胜利者。

请思考下,如何选出这个胜利者?
这个一个循环数数的问题,相当于排队的人,从前面出队,插到队尾,一直循环,当数到n这数时,出队的人不再插到队尾直接淘汰,然后接着数,直到循环队列剩下最后一个人就是胜出。这就是一个循环队列的实例。以下便是代码的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var cricle = function(names, number){
var queue = new Queue();
for(let i = 0; i< names; i++>){
queue.enQueue(names[i]);
}
while(queue.size > 1){
// 循环队列,插入队尾
for(let i = 0; i< number-1; i++){
queue.enQueue(queue.deQueue());
}
// 数到第number次,出队列
console.log('出队列的姓名是:',que.dequeue())
}
// 最终结束只剩一个就是胜出者
console.log('最终胜利者的姓名是:',que.dequeue())
}
```

## 优先队列
火车抢票想必大家都经历过,出票的过程正常是按订购时间排队出票,然而买了加速包或者办了vip会员的人都有优先出票的权利,就不能正常排队了,同时还有黑卡会员,金卡会员等等,等级越高,肯定排队优先级不一样(无奈吧!!!)这个时候如何解决排队问题,简单的队列也就无法满足要求,这个时候我们就需要用到优先队列来解决问题。

何为加权队列?即在队列基础上加上一个优先级,在排队的时候需要按照优先级将优先级高的排在前面(也就是我们说的插队),下面就是优先队列的一个代码实现:

var PriorityQueue = function(){
// 保存数据的
var items = [];
// 辅助类(包括元素和优先级)
var priorityQueueItem = function(element, priority){
this.element = element;
this.priority = priority;
}

this.enQueue = function(element, priority){
    let queueItem = new priorityQueueItem(element, priority);
    let add = false;
    // 优先队列权限高的排前面
    for(let i = 0; i < items.length; i++){
        // 优先级大的插队排到前面
        if(queueItem.priotity > items[i].priority){
            items.spilce(i, 0, queueItem);
            add = true;
        }
    }
    /** 优先级最小 */
    if(!add){
        items.push(queueItem);
    }
}
/**
 * 其他队列的操作同上面普通队列的操作方法一致,这里不复述了
 */

}
`
优先队列的核心在于入队列的时候需要比较元素的优先级,然后插入合适的位置,其他操作与普通队列是一致的。

坚持原创技术分享,您的支持将鼓励我继续创作!