快捷導(dǎo)航

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

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

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

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

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

那么帶來的問題：

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

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

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

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

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

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

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()方法顯示隊列內(nèi)的所有元素 //
/////////////////////////////
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的隊列是用數(shù)組描述的，底層解決了些弊端了。當(dāng)然還有查找算法上的問題，比如可以用數(shù)組實現(xiàn)單鏈表結(jié)構(gòu)等等，我們這里只討論javascript的隊列

模擬jQuery，使用隊列實現(xiàn)一個動畫

<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);
  }

  /**
   * 動畫
   * @return {[type]} [description]
   */
  var animation = function() {
    var self = {};
    var Queue = []; //動畫隊列
    var fireing = false //動畫鎖
    var first = true; //通過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)聽動畫完結(jié)
      element.addEventListener('webkitTransitionEnd', function() {
        func()
      });
    }

    var _fire = function() {
      //加入動畫正在觸發(fā)
      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);
        });

        //如果有一個隊列立刻觸發(fā)動畫
        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'
  });
};

測試

<!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);
 }

 /**
 * 動畫
 * @return {[type]} [description]
 */
 var animation = function() {
 var self = {};
 var Queue = []; //動畫隊列
 var fireing = false //動畫鎖
 var first = true; //通過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)聽動畫完結(jié)
  element.addEventListener('webkitTransitionEnd', function() {
  func()
  });
 }

 var _fire = function() {
  //加入動畫正在觸發(fā)
  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);
  });

  //如果有一個隊列立刻觸發(fā)動畫
  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>

您可能感興趣的文章: