Q

JSのArrayは#(?:un)?shiftが遅くてキューとして使いにくいため，自作すると良いらしい。

/// q.js ///

// wrapper of native array
function Qa(){
  var q = [];
  q.enq = q.push;
  q.deq = q.shift;
  return q;
}

// relies on property-order-retention (wouldn't work on Rhino)
function Qd(){
  var q = {}, p = 0;
  this.enq = function(o){ return q[p++] = o };
  this.deq = function(){
    for(var k in q){
      var o = q[k];
      delete q[k];
      return o;
    }
  };
}

// based on http://www.safalra.com/web-design/javascript/queues/
function Qs(){
  var q = [], len = 0, spc = 0;
  this.enq = function(o){ return q[len++] = o };
  this.deq = function(){ if(len){
    var o = q[spc++];
    if(spc * 2 >= len){
      q = q.slice(spc);
      len -= spc;
      spc = 0;
    }
    return o;
  } };
}

/// q_test.js ///
load('q.js');

function test(qs, n){
  print('\nn =', n);
  for(var k in qs){
    var q = new qs[k], a = (''+ qs[k]).split(/\s+/), l = a.length, i, t;
    for(i = l; i--;) q.enq(a[i]);
    for(i = l; i-- && q.deq() === a[i];);
    print('[', k, ']  test ->', ~i ? 'FAILED' : 'OK');
    for(var m in {enq:1, deq:1}){
      for(i = n, t = new Date; i--;) q[m](0);
      print(' ', m +' time:', ((new Date - t)/n).toFixed(4), '[ms]');
    }
    for(i = n, t = new Date; i--;)
      q.enq(1), q.deq(), q.enq(2), q.enq(3), q.deq(), q.deq();
    print('  e+d time:', ((new Date - t)/n/3).toFixed(4), '[ms]');
  }
}

test(qs = {arr: Qa, del: Qd, sli: Qs}, 5000);
test(qs, 500);

n = 5000
[ arr ]  test -> OK
  enq time: 0.0026 [ms]
  deq time: 1.2408 [ms]
  e+d time: 0.0051 [ms]
[ del ]  test -> OK
  enq time: 0.0038 [ms]
  deq time: 0.5652 [ms]
  e+d time: 0.0117 [ms]
[ sli ]  test -> OK
  enq time: 0.0028 [ms]
  deq time: 0.0044 [ms]
  e+d time: 0.0117 [ms]

n = 500
[ arr ]  test -> OK
  enq time: 0.0020 [ms]
  deq time: 0.1280 [ms]
  e+d time: 0.0053 [ms]
[ del ]  test -> OK
  enq time: 0.0040 [ms]
  deq time: 0.0700 [ms]
  e+d time: 0.0120 [ms]
[ sli ]  test -> OK
  enq time: 0.0040 [ms]
  deq time: 0.0060 [ms]
  e+d time: 0.0120 [ms]

slice版が圧倒的。思いつきで書いてみたdelete版は(array版より多少速いものの結局)要素数に比例して遅くなってしまい，まるで使えない。