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，使用队列实现一个动画

点击

(function($) {

  window.$ = $;

})(function() {

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

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

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

测试

点击