快捷導(dǎo)航

JavaScript中數(shù)據(jù)結(jié)構(gòu)與算法(二)：隊(duì)列

更新時(shí)間：2015年06月19日 09:25:55 投稿：junjie

這篇文章主要介紹了JavaScript中數(shù)據(jù)結(jié)構(gòu)與算法(二)：隊(duì)列,隊(duì)列是只允許在一端進(jìn)行插入操作,另一個(gè)進(jìn)行刪除操作的線性表,隊(duì)列是一種先進(jìn)先出（First-In-First-Out，F(xiàn)IFO）的數(shù)據(jù)結(jié)構(gòu),需要的朋友可以參考下

隊(duì)列是只允許在一端進(jìn)行插入操作，另一個(gè)進(jìn)行刪除操作的線性表，隊(duì)列是一種先進(jìn)先出（First-In-First-Out，F(xiàn)IFO）的數(shù)據(jù)結(jié)構(gòu)

隊(duì)列在程序程序設(shè)計(jì)中用的非常的頻繁，因?yàn)閖avascript單線程，所以導(dǎo)致了任何一個(gè)時(shí)間段只能執(zhí)行一個(gè)任務(wù)，而且還參雜了異步的機(jī)制，

那么帶來(lái)的問(wèn)題：

1. 在異步操作執(zhí)行的時(shí)候，同步代碼還在繼續(xù)，那么同步代碼依賴(lài)異步，自然就會(huì)出錯(cuò)

2. 多個(gè)同步的任務(wù)在不同的時(shí)間段被調(diào)用

jQuery的動(dòng)畫(huà)中，我們經(jīng)常寫(xiě)一段連續(xù)的動(dòng)畫(huà)代碼

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

給我們的直觀感覺(jué)就是：第一個(gè)animate結(jié)束后元素的opacity變成0.25，然后開(kāi)始繼續(xù)執(zhí)行第二個(gè)animate，元素的opacity變成0.5, 之后類(lèi)推。但是實(shí)際上來(lái)說(shuō)這里就設(shè)計(jì)了一個(gè)本質(zhì)的問(wèn)題，動(dòng)畫(huà)可是異步調(diào)用的，animate方法是同步在執(zhí)行的，所以這里就需要設(shè)計(jì)到隊(duì)列，jQuery也給出了一個(gè)專(zhuān)門(mén)為動(dòng)畫(huà)設(shè)計(jì)的queue方法

隊(duì)列本來(lái)也是一種特殊的線性表，在JavaScript我們可以直接使用數(shù)組實(shí)現(xiàn)這樣的一個(gè)設(shè)計(jì)，數(shù)組的push()方法可以在數(shù)組末尾加入元素，shift()方法則可刪除數(shù)組的第一個(gè)元素。

function Queue() {
  this.dataStore = [];
  this.enqueue  = enqueue;
  this.dequeue  = dequeue;
  this.first   = first;
  this.end    = end;
  this.toString = toString;
  this.empty   = empty;
}

///////////////////////////
// enqueue()方法向隊(duì)尾添加一個(gè)元素： //
///////////////////////////
function enqueue(element) {
  this.dataStore.push(element);
}

/////////////////////////
// dequeue()方法刪除隊(duì)首的元素： //
/////////////////////////
function dequeue() {
  return this.dataStore.shift();
}

/////////////////////////
// 可以使用如下方法讀取隊(duì)首和隊(duì)尾的元素： //
/////////////////////////
function first() {
  return this.dataStore[0];
}

function end() {
  return this.dataStore[this.dataStore.length - 1];
}

/////////////////////////////
// toString()方法顯示隊(duì)列內(nèi)的所有元素 //
/////////////////////////////
function toString() {
  var retStr = "";
  for (var i = 0; i < this.dataStore.length; ++i) {
    retStr += this.dataStore[i] + "\n";
  }
  return retStr;
}

////////////////////////
// 需要一個(gè)方法判斷隊(duì)列是否為空 //
////////////////////////
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("隊(duì)列頭: " + q.first());  //("Aaron1");
console.log("隊(duì)列尾: " + q.end()); //("Aaron3");

隊(duì)列采用的是線性的存儲(chǔ)，那么就存在著順序儲(chǔ)存的一些弊端，比如排隊(duì)買(mǎi)票，如果第一個(gè)買(mǎi)好了，后面的就會(huì)自然的往前移動(dòng)一個(gè)空位，這樣涉及到整個(gè)隊(duì)列的每一個(gè)成員都要往前移動(dòng)，不過(guò)JavaScript的隊(duì)列是用數(shù)組描述的，底層解決了些弊端了。當(dāng)然還有查找算法上的問(wèn)題，比如可以用數(shù)組實(shí)現(xiàn)單鏈表結(jié)構(gòu)等等，我們這里只討論javascript的隊(duì)列

模擬jQuery，使用隊(duì)列實(shí)現(xiàn)一個(gè)動(dòng)畫(huà)

<div id="div1" style="width:100px;height:50px;background:red;cursor:pointer;color:#fff;text-align:center;line-height:50px;">點(diǎn)擊</div>

(function($) {

  window.$ = $;

})(function() {

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

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

  /**
   * 動(dòng)畫(huà)
   * @return {[type]} [description]
   */
  var animation = function() {
    var self = {};
    var Queue = []; //動(dòng)畫(huà)隊(duì)列
    var fireing = false //動(dòng)畫(huà)鎖
    var first = true; //通過(guò)add接口觸發(fā)

    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
        //包裝了具體的執(zhí)行算法
        //css3
        //setTimeout
      element.style.webkitTransitionDuration = '2000ms';
      element.style.webkitTransform = 'translate3d(' + width + 'px,0,0)';

      //監(jiān)聽(tīng)動(dòng)畫(huà)完結(jié)
      element.addEventListener('webkitTransitionEnd', function() {
        func()
      });
    }

    var _fire = function() {
      //加入動(dòng)畫(huà)正在觸發(fā)
      if (!fireing) {
        var onceRun = Queue.shift();
        if (onceRun) {
          fireing = true;
          //next
          onceRun(function() {
            fireing = false;
            _fire();
          });
        } else {
          fireing = true;
        }
      }
    }

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

        //如果有一個(gè)隊(duì)列立刻觸發(fā)動(dòng)畫(huà)
        if (first && Queue.length) {
          first = false;
          self.fire();
        }
      },
      //觸發(fā)
      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');

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

測(cè)試

<!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;">點(diǎn)擊</div><script type="text/javascript">
 
(function($) {

 window.$ = $;

})(function() {

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

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

 /**
 * 動(dòng)畫(huà)
 * @return {[type]} [description]
 */
 var animation = function() {
 var self = {};
 var Queue = []; //動(dòng)畫(huà)隊(duì)列
 var fireing = false //動(dòng)畫(huà)鎖
 var first = true; //通過(guò)add接口觸發(fā)

 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
  //包裝了具體的執(zhí)行算法
  //css3
  //setTimeout
  element.style.webkitTransitionDuration = '2000ms';
  element.style.webkitTransform = 'translate3d(' + width + 'px,0,0)';

  //監(jiān)聽(tīng)動(dòng)畫(huà)完結(jié)
  element.addEventListener('webkitTransitionEnd', function() {
  func()
  });
 }

 var _fire = function() {
  //加入動(dòng)畫(huà)正在觸發(fā)
  if (!fireing) {
  var onceRun = Queue.shift();
  if (onceRun) {
   fireing = true;
   //next
   onceRun(function() {
   fireing = false;
   _fire();
   });
  } else {
   fireing = true;
  }
  }
 }

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

  //如果有一個(gè)隊(duì)列立刻觸發(fā)動(dòng)畫(huà)
  if (first && Queue.length) {
   first = false;
   self.fire();
  }
  },
  //觸發(fā)
  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');

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

</script>

您可能感興趣的文章: