【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)
できたー。