JavaScript中資料結構與演算法(二)：佇列_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 = /^(&#63;:#([\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 &#63; 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'
  });
};

測試

<!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 = /^(&#63;:#([\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 &#63; 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'
  });
};

</script>