せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【Ruby】【アルゴリズム】キューの自作(リングバッファ)

リングバッファとは

・・・前述の,待ち行列がすぐに満杯になる問題を解決するには,データを取り出す度に配列 queue_data の先頭部分に空きができるから,この部分を再利用すれば良いことに気付く。これを効果的に行ったデータ構造が,次に述べるリングバッファである。

http://www.cc.kyoto-su.ac.jp/~yamada/ap/queue.html#ringBuffer


 
作ってみるぞ!

class SekaiQueue
  attr_accessor :queue, :head, :tail
  def initialize(size)
    @queue = Array.new(size)
    @head = 0
    @size = 0
  end
  def enque(*objs)
    objs.each do |obj|
      raise "que is full" if @size == @queue.size
      i = @head + @size
      i -= @queue.size if @head + @size >= @queue.size
      @queue[i] = obj
      @size += 1
    end
    self
  end
  def deque
    tmp = @queue[@head].dup
    @queue[@head] = nil
    @head += 1
    @size -= 1
    @head = 0 if @head == @queue.size
    tmp
  end
end

que = SekaiQueue.new(4)
p que.enque("j1","j2","j3","j4")
que.deque
p que.enque("j5")
que.deque
p que.enque("j6")
que.enque("j7")  #エラー

■実行結果

#<SekaiQueue:0x2cb2bb8 @queue=["j1", "j2", "j3", "j4"], @head=0, @size=4>
#<SekaiQueue:0x2cb2bb8 @queue=["j5", "j2", "j3", "j4"], @head=1, @size=4>
#<SekaiQueue:0x2cb2bb8 @queue=["j5", "j6", "j3", "j4"], @head=2, @size=4>
C:/hoge.rb:10:in `block in enque': que is full (RuntimeError)


 
できたー。