数据结构与算法JavaScript (二) 队列

队列是只允许在一端进行插入操作，另一个进行删除操作的线性表，队列是一种先进先出（First-In-First-Out，FIFO）的数据结构

队列在程序程序设计中用的非常的频繁，因为javascript单线程，所以导致了任何一个时间段只能执行一个任务，而且还参杂了异步的机制，

那么带来的问题：

1. 在异步操作执行的时候，同步代码还在继续，那么同步代码依赖异步，自然就会出错

2. 多个同步的任务在不同的时间段被调用

jQuery的动画中，我们经常写一段连续的动画代码

$book.animate({

    opacity: 0.25,

}).animate({

    opacity: 0.5

}).animate({

    opacity:

})

给我们的直观感觉就是：第一个animate结束后元素的opacity变成0.25，然后开始继续执行第二个animate，元素的opacity变成0.5, 之后类推。但是实际上来说这里就设计了一个本质的问题，动画可是异步调用的，animate方法是同步在执行的，所以这里就需要设计到队列，jQuery也给出了一个专门为动画设计的queue方法

队列本来也是一种特殊的线性表，在JavaScript我们可以直接使用数组实现这样的一个设计，数组的push()方法可以在数组末尾加入元素，shift()方法则可删除数组的第一个元素。

function Queue() {

    this.dataStore = [];

    this.enqueue   = enqueue;

    this.dequeue   = dequeue;

    this.first     = first;

    this.end       = end;

    this.toString  = toString;

    this.empty     = empty;

}

///////////////////////////

// enqueue()方法向队尾添加一个元素： //

///////////////////////////

function enqueue(element) {

    this.dataStore.push(element);

}

/////////////////////////

// dequeue()方法删除队首的元素： //

/////////////////////////

function dequeue() {

    return this.dataStore.shift();

}

/////////////////////////

// 可以使用如下方法读取队首和队尾的元素： //

/////////////////////////

function first() {

    return this.dataStore[];

}

function end() {

    return this.dataStore[this.dataStore.length - ];

}

/////////////////////////////

// toString()方法显示队列内的所有元素 //

/////////////////////////////

function toString() {

    var retStr = "";

    for (var i = ; i < this.dataStore.length; ++i) {

        retStr += this.dataStore[i] + "\n";

    }

    return retStr;

}

////////////////////////

// 需要一个方法判断队列是否为空 //

////////////////////////

function empty() {

    if (this.dataStore.length == ) {

        return true;

    } else {

        return false;

    }

}

var q = new Queue();

q.enqueue("Aaron1");

q.enqueue("Aaron2");

q.enqueue("Aaron3");

console.log("队列头: " + q.first());   //("Aaron1");

console.log("队列尾: " + q.end());  //("Aaron3");

队列采用的是线性的存储，那么就存在着顺序储存的一些弊端，比如排队买票，如果第一个买好了，后面的就会自然的往前移动一个空位，这样涉及到整个队列的每一个成员都要往前移动，不过JavaScript的队列是用数组描述的，底层解决了些弊端了。当然还有查找算法上的问题，比如可以用数组实现单链表结构等等，我们这里只讨论javascript的队列

模拟jQuery，使用队列实现一个动画

<div id="div1" style="width:100px;height:50px;background:red;cursor:pointer;color:#fff;text-align:center;line-height:50px;">点击</div>

(function($) {

    window.$ = $;

})(function() {

    var rquickExpr = /^(?:#([\w-]*))$/;

    function aQuery(selector) {

        return new aQuery.fn.init(selector);

    }

    /**

     * 动画

     * @return {[type]} [description]

     */

    var animation = function() {

        var self = {};

        var Queue = []; //动画队列

        var fireing = false //动画锁

        var first = true; //通过add接口触发

        var getStyle = function(obj, attr) {

            return obj.currentStyle ? obj.currentStyle[attr] : getComputedStyle(obj, false)[attr];

        }

        var makeAnim = function(element, options, func) {

            var width = options.width

                //包装了具体的执行算法

                //css3

                //setTimeout

            element.style.webkitTransitionDuration = '2000ms';

            element.style.webkitTransform = 'translate3d(' + width + 'px,0,0)';

            //监听动画完结

            element.addEventListener('webkitTransitionEnd', function() {

                func()

            });

        }

        var _fire = function() {

            //加入动画正在触发

            if (!fireing) {

                var onceRun = Queue.shift();

                if (onceRun) {

                    fireing = true;

                    //next

                    onceRun(function() {

                        fireing = false;

                        _fire();

                    });

                } else {

                    fireing = true;

                }

            }

        }

        return self = {

            //增加队列

            add: function(element, options) {

                Queue.push(function(func) {

                    makeAnim(element, options, func);

                });

                //如果有一个队列立刻触发动画

                if (first && Queue.length) {

                    first = false;

                    self.fire();

                }

            },

            //触发

            fire: function() {

                _fire();

            }

        }

    }();

    aQuery.fn = aQuery.prototype = {

        run: function(options) {

            animation.add(this.element, options);

            return this;

        }

    }

    var init = aQuery.fn.init = function(selector) {

        var match = rquickExpr.exec(selector);

        var element = document.getElementById(match[])

        this.element = element;

        return this;

    }

    init.prototype = aQuery.fn;

    return aQuery;

}());

//dom

var oDiv = document.getElementById('div1');

//调用

oDiv.onclick = function() {

    $('#div1').run({

        'width': ''

    }).run({

        'width': ''

    }).run({

        'width': ''

    });

};

测试

<!doctype html><div id="div1" style="width:100px;height:50px;background:red;cursor:pointer;color:#fff;text-align:center;line-height:50px;" data-mce-style="width: 100px; height: 50px; background: red; cursor: pointer; color: #fff; text-align: center; line-height: 50px;">点击</div><script type="text/javascript">

(function($) {

window.$ = $;

})(function() {

var rquickExpr = /^(?:#([\w-]*))$/;

function aQuery(selector) {
return new aQuery.fn.init(selector);
}

/**
* 动画
* @return {[type]} [description]
*/
var animation = function() {
var self = {};
var Queue = []; //动画队列
var fireing = false //动画锁
var first = true; //通过add接口触发

var getStyle = function(obj, attr) {
return obj.currentStyle ? obj.currentStyle[attr] : getComputedStyle(obj, false)[attr];
}

var makeAnim = function(element, options, func) {
var width = options.width
//包装了具体的执行算法
//css3
//setTimeout
element.style.webkitTransitionDuration = '2000ms';
element.style.webkitTransform = 'translate3d(' + width + 'px,0,0)';

//监听动画完结
element.addEventListener('webkitTransitionEnd', function() {
func()
});
}

return self = {
//增加队列
add: function(element, options) {
Queue.push(function(func) {
makeAnim(element, options, func);
});

//如果有一个队列立刻触发动画
if (first && Queue.length) {
first = false;
self.fire();
}
},
//触发
fire: function() {
_fire();
}
}
}();

aQuery.fn = aQuery.prototype = {
run: function(options) {
animation.add(this.element, options);
return this;
}
}

var init = aQuery.fn.init = function(selector) {
var match = rquickExpr.exec(selector);
var element = document.getElementById(match[1])
this.element = element;
return this;
}

init.prototype = aQuery.fn;

return aQuery;
}());

//dom
var oDiv = document.getElementById('div1');

//调用
oDiv.onclick = function() {
$('#div1').run({
'width': '500'
}).run({
'width': '300'
}).run({
'width': '1000'
});
};

</script>

秒客网

数据结构与算法JavaScript (二) 队列

相关文章