Javascriptで両端キュー（ArrayDeque）を実装してみた

#説明上の特記事項
キューの概念として、「取り出す場所を順番の最初」「追加する場所を順番の最後」と示すことが多いが、物理的な位置の図示をする関係上
・最初：左側
・最後：右側
とみなす。

#Javascriptの配列型は左側から追加（unshift）・削除（shift）が遅い
https://qiita.com/Nabetani/items/03d12e76b916a037187f

(左から追加する回数を2倍にしたら、2倍を確実に超える処理時間になってしまう)

#これで起こる問題
Javascriptで幅優先探索（01BFS）の問題解決において、処理時間がネックになる。
幅優先探索の基本実装はキューに則る。なので行いたい操作は「キューの左端から取り出すこと、右端に追加すること」である。

・使うデータ構造は配列型
・配列型がサポートしてるshiftメソッド、pushメソッドを使う
となると考えられる。

基礎コードを以下に示す。頂点0を始点とした幅優先探索とする。

normal.js

//頂点と隣接リスト群。コード例すべてで共通。
var node = [
  {
    depth : -1,
    edges : [1, 3, 5]
  },
  {
    depth : -1,
    edges : [2, 4]
  },
  ....
];

var queue = [0];

while(queue.length > 0){
  var now = queue.shift();
  var edges = node[now].edges;
  for(var i = 0; i < edges.length; i++){
    var next = edges[i];
    if(node[next].depth == -1){
       node[next].depth = node[now].depth + 1;
       queue.push(next);
    }
  }
}

処理時間は後で。

#早いキューを作る
まずはキューを作るための発想の出どころから
キューの出入りの仕方は「尺取り法」と同じ考えを持つことができる。

キューに対する情報として、「次に取り出す位置」を定義する。
・取り出したら1つ右に進める。
・「取り出す位置」と「queueの大きさ」が一致した（＝取り出す先になにもない）時、処理を終了する。

取り出し位置を決めたことで、尺取虫の
・取り出し位置：後ろ足
・追加時の配列の大きさ：前足
が決められたと言える。

insectMoth.js

var queue = [0];
var pollIndex = 0;//取り出し位置

while(pollIndex < queue.length){
  var now = queue[pollIndex];
  pollIndex++;//取り出し位置更新
  var edges = node[now].edges;
  for(var i = 0; i < edges.length; i++){
    var next = edges[i];
    if(node[next].depth == -1){
       node[next].depth = node[now].depth + 1;
       queue.push(next);
    }
  }
}

//私の提出コード漁ったら「追加する位置」も定義してるものがあるが必要なし

処理時間は後で。

#キューはできたけど両端キューではないので作る
01BFSは「左に追加」が想定されるので、位置の指定がマイナスとなる可能性がある。
しかし配列型はマイナスな位置を指定したり、その位置に値を置くなどができない。

🤔？

・・・使えないので配列型からオブジェクト型に変更する。

今度は左右それぞれで「次に追加する位置」を定義する。（黒矢印）
「取り出す位置」は自動で決まる（白矢印）

そのままでは使えないので補正を行う。

・要素数が0個→1個に変化する時
どっちの方向から追加したかに関わらず、追加した時の場所が「X」の時、
次に追加する位置は、
左側：X - 1
右側：X + 1

・要素数が1個→0個に変化する時
どちらから削除したかに関わらず、次に追加する位置は左右ともに同じになる。

左から削除：右の追加位置を左に1つ進める
右から削除：左の追加位置を右に1つ進める

ArrayDeque.js

var queue = {
  firstIndex : 0,
  lastIndex : 0,
  map : {},
  shift : function(){
    if(this.nullCheck()){
      return null;
    }
    var retVal = this.map[this.firstIndex + 1];
    this.firstIndex++;
    if(Math.abs(this.firstIndex - this.lastIndex) == 1){
      this.lastIndex--;
    }
    return retVal;
  },
  unshift : function(V){
    this.map[this.firstIndex] = V;
    if(this.nullCheck()){
      this.lastIndex++;
    }
    this.firstIndex--;
  },
  pop : function(){
    if(this.nullCheck()){
      return null;
    }
    var retVal = this.map[this.lastIndex - 1];
    this.lastIndex--;
    if(Math.abs(this.firstIndex - this.lastIndex) == 1){
      this.firstIndex++;
    }
    return retVal;
  },
  push : function(V){
    this.map[this.lastIndex] = V;
    if(this.nullCheck()){
      this.firstIndex--;
    }
    this.lastIndex++;
  },
  nullCheck : function(){
    return this.firstIndex == this.lastIndex;
  }
}

queue.push(0);
while(!queue.nullCheck()){
  var now = queue.shift();
  var edges = nodes[now];
  for(var i = 0; i < edges.length; i++){
    var next = edges[i];
    if(node[next].depth == -1){
      node[next].depth = node[now].depth + 1;
      queue.push(next);
    }
  }
}

#処理時間
頂点数10万、辺数20万くらいで試す。

・最初の：652ms
・次の　：154ms
・最後の：129ms

汎用性の意味でも両端キューを想定したオブジェクトでやれば無問題。

#副産物
JavaのArrayDequeと違って、キュー内の任意の位置の値を見たり書き換えたりすることができる。
ピンポイントだが、この問題の正解に貢献した。

#考えられる不都合
取り出し時に値の物理削除は行わない。よって無駄が残る。これが原因の不具合は未確認なため、今の所スルーしてる。

#終わりに
気がついたら作れてた。
処理コストが高い問題とその解決方法について、類題の記事があまり見つからないので事例紹介で投稿した。

・スタック2個でキューを実現