数据结构—-队列

我心飞翔 分类:javascript

1、队列的定义

队列是一种特殊的线性表,其特殊之处在于,它只允许你在队列的头部删除元素,在队列的末尾添加新的元素。

2、队列的方法

  • enqueue 从队列尾部添加一个元素(新来一个排队的人,文明礼貌,站在了队伍末尾)
  • dequeue 从队列头部删除一个元素(排队伍最前面的人刚办理完登机手续,离开了队伍)
  • head 返回头部的元素,注意,不是删除(只是看一下,谁排在最前面)
  • size 返回队列大小(数一数有多少人在排队)
  • clear 清空队列(航班取消,大家都散了吧)
  • isEmpty 判断队列是否为空 (看看是不是有人在排队)
  • tail 返回队列尾节点

3、实现队列

这里先用数组的方式实现。如下:

function Queue () {
    var items = [];
    this.enqueue = function(item){
        items.push(item)
    }
    this.dequeue = function(){
        items.shift()
    }
    this.head = function(){
        return items[0]
    }
    this.size = function(){
        return items.length
    }
    this.clear = function(){
        items = []
    }
    this.isEmpty = function(){
        return items.length === 0
    }
    this.tail = function(){
        return items[items.length-1]
    }
}
 

4、队列的小练习

Q1:   约瑟夫环问题。有一个数组a[100]存放0--99;要求每隔两个数删掉一个数,到末尾时循环至开头继续进行,求最后一个被删掉的数。

上代码:

function del_circle(arr){
    var _queue = new Queue();
    var index = 0;
    // 把数组中的元素入栈
    for(var i=0;i<arr.length;i++){
        _queue.enqueue(arr[i]);
    }
    var index = 0;
    while(_queue.size() !== 1){
        // 弹出一个元素,判断是否需要删除
        var item = _queue.dequeue();
        index += 1;
        // 每隔两个删除一个,将不是被删除的元素入栈,即放到对列的尾部
        if(index %3 !== 0){
            _queue.enqueue(item);
        }
    }
    return _queue.head();
}

var arr = [];
for(var i=0;i<100;i++){
    arr.push(i);
}
console.log(del_circle(arr));
 

思路:

准备好一个队列(头部可删除元素,尾部添加元素),将100个数入栈。每隔两个删除一个,并将这两个数放到队列的末尾。每隔3取余,找到这个要删除的数,用 index 做标记,前两个数入队列。依次循环这样。。。。

Q2:  斐波那契数列

前两项是 1  1,以后每项是前两项之和,即 f(n) = f(n-1) + f(n-2)。

1、递归方式实现:

function fibonacci(n){
    if(n<=2) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}
 

2、队列实现

function fibonacci(n){  var queue = new Queue();  var index = 0; // 计数用来实现每3个删除一个  // 先放入斐波那契序列的前两个数值  queue.enqueue(1);  queue.enqueue(1);  while(index < n-2){    // 出队列一个元素    var del_item = queue.dequeue();    // 取队列头部元素    var head_item = queue.head();    var next_item = del_item + head_item;    // 将计算结果放入队列    queue.enqueue(next_item);    index += 1;  }  queue.dequeue();  return queue.head();}
 

思路:

将每次前两项相加之和从队尾入队列,先放入两个数到队列中,将队列头部删除的元素记为 del_item, 这是队列中剩余 head_item , 两者相加 得 next_item 再将其从队尾入队列。

回复

我来回复
  • 暂无回复内容