アルゴリズムとデータ構造の要点メモ in ruby（キュー）

目的

技術面接のために修行を始める。
ウェブでの技術試験時にみやすいようにこのページにまとめる。
Rubyでそそくさと実装できることを目的とする。

配列 https://qiita.com/tsnb/items/983c32d83331de1e0bea
連結リスト https://qiita.com/tsnb/items/3028ee788ff77ebaaa5e
スタック https://qiita.com/tsnb/items/e6901249629ef090ee8f

参考

• https://programming-place.net/ppp/contents/algorithm/index.html#header (分かりやすいです、書いた人あざます、この記事をRuby用にまとめてるだけです)

キュー（データ構造）

要点

キューは、一番最初に格納したデータからしか取り出せない

キューというデータ構造にとって、最低限必要な機能は以下のとおり

• データを追加する (enqueue)
• データを取り出す (dequeue)
• キューが空かどうか調べる (is_empty)

実装

• 配列で実現
• enqueue, dequeue
• is_emptyでキューが空かどうか確認
• nextで次にdequeueされる値を取得
• clearでキューを再作成
• キューリストを取得
• リングバッファ、"末尾の次は先頭" (tail+1)%max_size = front
• キューが満杯の時に、配列サイズを倍にする

class Queue
  attr_reader :next, :queue, :front, :tail

  def initialize(size)
    @struct_nil = Struct.new("MyNil", :x)
    @size = size
    @queue = arr_new(@size)
    @front = 0
    @tail = 0
    @next = @queue[front]
  end

  def clear
    @queue = arr_new(@size)
  end

  def is_empty
    @front == @tail
  end

  def is_full
    (@tail + 1) % @size == @front
  end

  def enqueue(val)
    @queue[@tail] = val
    resize
    next_tail # 次のエンキューのためにポインタをずらす
  end

  def dequeue
    unless is_empty
      val = @queue[@front]
      @queue[@front] = mynil
      next_front
      @next = @queue[@front]
      val
    end
  end

private
  def resize
    if is_full
      @queue = @queue[@front..-1].concat(@queue[0..@tail]) if @front > @tail
      @front = 0
      @tail = @size - 1
      @queue.concat(arr_new(@size))
      @size = @queue.size
    end
  end

  def next_tail
    @tail = (@tail + 1 == @size)? 0 : @tail + 1
  end

  def next_front
    @front = (@front + 1 == @size)? 0 : @front + 1
  end

  def arr_new(size)
    Array.new(size, mynil)
  end

  def mynil
    @struct_nil.new(nil)
  end
end

irb(main):811:0> q = Queue.new(2)
(irb):748: warning: redefining constant Struct::MyNil
=> #<Thread::Queue:0x00007fc7b700ff60 @struct_nil=Struct::MyNil, @size=2, @queue=[#<struct Struct::MyNil x=nil>, #<struct Struct::MyNil x=nil>], @front=0, @tail=0, @next=#<struct Struct::MyNil x=nil>>
irb(main):812:0> q.dequeue
=> nil
irb(main):813:0> q.enqueue(1)
=> 1
irb(main):814:0> q
=> #<Thread::Queue:0x00007fc7b700ff60 @struct_nil=Struct::MyNil, @size=2, @queue=[1, #<struct Struct::MyNil x=nil>], @front=0, @tail=1, @next=#<struct Struct::MyNil x=nil>>
irb(main):815:0> q.dequeue
=> 1
irb(main):816:0> q
=> #<Thread::Queue:0x00007fc7b700ff60 @struct_nil=Struct::MyNil, @size=2, @queue=[#<struct Struct::MyNil x=nil>, #<struct Struct::MyNil x=nil>], @front=1, @tail=1, @next=#<struct Struct::MyNil x=nil>>
irb(main):817:0> q.enqueue(2)
=> 0
irb(main):818:0> q
=> #<Thread::Queue:0x00007fc7b700ff60 @struct_nil=Struct::MyNil, @size=2, @queue=[#<struct Struct::MyNil x=nil>, 2], @front=1, @tail=0, @next=#<struct Struct::MyNil x=nil>>
irb(main):819:0> q.enqueue(3)
=> 2
irb(main):820:0> q
=> #<Thread::Queue:0x00007fc7b700ff60 @struct_nil=Struct::MyNil, @size=4, @queue=[2, 3, #<struct Struct::MyNil x=nil>, #<struct Struct::MyNil x=nil>], @front=0, @tail=2, @next=#<struct Struct::MyNil x=nil>>
irb(main):821:0> q.enqueue(4)
=> 3
irb(main):822:0> q
=> #<Thread::Queue:0x00007fc7b700ff60 @struct_nil=Struct::MyNil, @size=4, @queue=[2, 3, 4, #<struct Struct::MyNil x=nil>], @front=0, @tail=3, @next=#<struct Struct::MyNil x=nil>>
irb(main):823:0> q.dequeue
=> 2
irb(main):824:0> q
=> #<Thread::Queue:0x00007fc7b700ff60 @struct_nil=Struct::MyNil, @size=4, @queue=[#<struct Struct::MyNil x=nil>, 3, 4, #<struct Struct::MyNil x=nil>], @front=1, @tail=3, @next=3>
irb(main):825:0> q.enqueue(5)
=> 0
irb(main):826:0> q
=> #<Thread::Queue:0x00007fc7b700ff60 @struct_nil=Struct::MyNil, @size=4, @queue=[#<struct Struct::MyNil x=nil>, 3, 4, 5], @front=1, @tail=0, @next=3>
irb(main):827:0> q.enqueue(6)
=> 4
irb(main):828:0> q
=> #<Thread::Queue:0x00007fc7b700ff60 @struct_nil=Struct::MyNil, @size=8, @queue=[3, 4, 5, 6, #<struct Struct::MyNil x=nil>, #<struct Struct::MyNil x=nil>, #<struct Struct::MyNil x=nil>, #<struct Struct::MyNil x=nil>], @front=0, @tail=4, @next=3>

感想

リングバッファ、ポインタが回るあたりで考慮するのがめんどくさかった。
あと、resizeがめんどくさかった。バグありそう