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


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

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

那么带来的问题:

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

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

 


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

$book.animate({     opacity: 0.25, }).animate({     opacity: 0.5 }).animate({     opacity: 1 })

给我们的直观感觉就是:第一个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[0]; }  function end() {     return this.dataStore[this.dataStore.length - 1]; } 
///////////////////////////// // toString()方法显示队列内的所有元素 // ///////////////////////////// function toString() {     var retStr = "";     for (var i = 0; i < this.dataStore.length; ++i) {         retStr += this.dataStore[i] + "/n";     }     return retStr; }  //////////////////////// // 需要一个方法判断队列是否为空 // //////////////////////// function empty() {     if (this.dataStore.length == 0) {         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[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'     }); };

 

测试

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>