JavaScript: クロージャで 双方向リストを使って両端キューを作ってみた

速度出るかなーと思って作ってみたんだけど、自分の使い方ではそんなでもありませんでした。
要素数が多く(3000くらい?)なったら、メリットが出てくるかな。
せっかく作ったのでここに残しときます。

両端キュー is 何?

くわしくはこちらから：
双方向リスト
両端キュー

こんな風に使えます。

// 使用例：
//両端キューを作成
const q = deque()

//右から追加し、全体を表示
for(let i = 0; i < 4; i++){
    q.pushR(i)
    console.log(q.peekAll())
}

//左から追加し、全体を表示
for(let i = 0; i < 4; i++){
    q.pushL(-i)
    console.log(q.peekAll())
}

//左端、右端、長さを表示
console.log("peekL():", q.peekL())
console.log("peekR():", q.peekR())
console.log("size():", q.size())

//左から取り出し、残りを表示
for(let i = 0; i < 5; i++){
    console.log("popL():", q.popL())
    console.log(q.peekAll())
}

//右から取り出し、残りを表示
for(let i = 0; i < 4; i++){
    console.log("popR():", q.popR())
    console.log(q.peekAll())
}

// 出力：
[ 0 ]
[ 0, 1 ]
[ 0, 1, 2 ]
[ 0, 1, 2, 3 ]
[ -0, 0, 1, 2, 3 ]
[ -1, -0, 0, 1, 2, 3 ]
[ -2, -1, -0, 0, 1,  2,  3 ]
[ -3, -2, -1, -0, 0,  1,  2,  3 ]
peekL(): -3
peekR(): 3
size(): 8
popL(): -3
[ -2, -1, -0, 0,  1,  2,  3 ]
popL(): -2
[ -1, -0, 0, 1, 2, 3 ]
popL(): -1
[ -0, 0, 1, 2, 3 ]
popL(): -0
[ 0, 1, 2, 3 ]
popL(): 0
[ 1, 2, 3 ]
popR(): 3
[ 1, 2 ]
popR(): 2
[ 1 ]
popR(): 1
[]
popR(): undefined
[]

実装：

const deque = () => {
  let length = 0
  let head = undefined
  let last = undefined
  
  return {
    clear: () => {
      length = 0
      head = last = undefined     
    }
    
    , size: () => 
        length
    
    , peekL: () => 
        length === 0 ? undefined
        : head.val
    
    , peekR: () => 
        length === 0 ?  undefined
        : last.val
    
    , peekAll: () => {
      const peekRest = acc => e =>
      	e === undefined ? []
      	: e === null ? acc
      	: peekRest([...acc, e.val])(e.next)
      return peekRest([])(head)
    }
    
    , pushL: val => {
      if(length === 0){
        last = head = {prev: null, val: val, next: null}  
        length = 1
        return length
      }
      if(length === 1){
        last.prev = head = {prev: null, val: val, next: last}
        length = 2
        return length
      }
      head = head.prev = {prev: null, val: val, next: head}
      length ++
      return length
    }
    
    , pushR: val => {
      if(length === 0){
        head = last = {prev: null, val: val, next: null}  
        length = 1
        return length
      }
      if(length === 1){
        head.next = last = {prev: head, val: val, next: null}
        length = 2
        return length
      }
      last = last.next = {prev: last, val: val, next: null}
      length ++
      return length
    }
    
    , popL: () => {
      if(length === 0){
        return undefined
      }
      if(length === 1){
        const val = head.val
        head = last = undefined
        length = 0
        return val
      }
      const val = head.val
      head = head.next
      head.prev = null
      length --
      return val
    }
    
    , popR: () => {
      if(length === 0){
        return undefined
      }
      if(length === 1){
        const val = last.val
        head = last = undefined
        length = 0
        return val
      }
      const val = last.val
      last = last.prev
      last.next = null
      length --
      return val
    }
  }
}

ほぼ 双方向リスト, 両端キューを読んだまま、何の工夫もない素直な実装になっていると思います。

deque: 両端キューのクロージャを返す

クロージャとは?
クロージャ
deque はこんな風になっています：

const deque = () => {
  let length = 0        // キューの要素数
  let head = undefined  // キューの先頭
  let last = undefined  // キューの末尾
  
  return { ... } // 値が関数の要素のオブジェクトを返す

deque() を実行すると中身が関数のオブジェクトが返されるのですが、その関数たちが変数length,head,lastを使っているため、消されずにオブジェクトについてくる、という仕組みです。

以下、オブジェクト内の関数です。
L/R, head/last, prev/next は対称なので、L側についてだけにします。

clear:両端キューを初期化する

    clear: () => {
      length = 0
      head = last = undefined     
    }

単に変数を初期化するだけです。
双方向リストには循環参照がありますが、現在の実行環境ならちゃんとメモリー開放してくれるはずです。
メモリー管理

peekL:値を左側から取り出さずに取得する

peekL: () => 
        length === 0 ? undefined
        : head.val

キューの長さが 0 なら undefined を返し、そうでないなら先頭の差しているオブジェクトの要素valの値を返します。

peekAll():値を取り出さず、すべての値の配列を返す

peekAll: () => {
      const peekRest = acc => e =>
      	e === undefined ? []
      	: e === null ? acc
      	: peekRest([...acc, e.val])(e.next)
      return peekRest([])(head)
    }

内部関数 peekRest は末尾再帰になっています。
引数 e の値が undefined ならキューは空ということなので [] を返します。
e が null ならキューの末尾まで行ったということなので、acc を返します。
そうでないなら、配列 acc の末尾に e.val の値をつけたものと、e.nextが指しているオブジェクト を引数に再帰的にpeekRestを呼びます。

pushL:

 pushL: val => {
      if(length === 0){
        last = head = {prev: null, val: val, next: null}  
        length = 1
        return length
      }
      if(length === 1){
        last.prev = head = {prev: null, val: val, next: last}
        length = 2
        return length
      }
      head = head.prev = {prev: null, val: val, next: head}
      length ++
      return length
    }

以下、図示する予定