【アルゴリズムの勉強】Rubyでデータ構造のキューを書いてみる
アルゴリズムの勉強としてリングバッファによるキューをRubyで実装する。
キューとは
キュー(英: queue)、あるいは待ち行列はコンピュータの基本的なデータ構造の一つ。データを先入れ先出し[1]のリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー[2]、取り出すことをデキュー[3]という。
Rubyで実装
class Queue def initialize(capacity) @number = @front = @rear = 0 @max = capacity @que = Array.new(capacity) p @que end def enque(value) if @number >= @max puts "キューは満杯です" else @que[@rear] = value @number += 1 if (@rear + 1) == @max @rear = 0 else @rear += 1 end p @que end end def deque if @number <= 0 puts "キューは空です" else result = @que[@front] @number += -1 if (@front + 1) == @max @front = 0 else @front += 1 end puts "#{result}を取り出しました" end end def next_value if @number <= 0 puts "キューは空です" else result = @que[@front] puts "次に取り出される値は#{result}です" end end def search(value) for i in 0..(@number - 1) index = (i + @front) % @max if @que[index] == value puts "#{value}はキュー内に存在します" return end end puts "#{value}はキュー内に存在しません" end def clear @number = @front = @rear = 0 puts "キューを空にしました。" end def capacity puts "キューの容量は#{@max}です" end def number_of_data puts "キューには#{@number}つのデータが格納されています" end def empty? if @number <= 0 puts "キューは空です" else puts "キューは空ではありません" end end def full? if @number >= @max puts "キューは満杯です" else puts "キューはまだ空き領域が存在します" end end def dump if @number <= 0 puts "スタックは空です" else for index in 0..(@number - 1) puts @que[index] end end end end queue = Queue.new(5) # => [nil, nil, nil, nil, nil] queue.enque(5) # => [5, nil, nil, nil, nil] queue.enque(12) # => [5, 12, nil, nil, nil] queue.deque # => 5を取り出しました queue.enque(2) # => [5, 12, 2, nil, nil] queue.enque(52) # => [5, 12, 2, 52, nil] queue.deque # => 12を取り出しました queue.next_value # => 次に取り出される値は2です queue.search(2) # => 2はキュー内に存在します queue.capacity # => キューの容量は5です queue.number_of_data # => キューには2つのデータが格納されています queue.empty? # => スタックはまだ空き領域が存在します queue.enque(87) # => [5, 12, 2, 52, 87] queue.enque(32) # => [32, 12, 2, 52, 87] queue.enque(412) # => [32, 412, 2, 52, 87] queue.enque(999) # => キューは満杯です queue.clear # => キューを空にしました。 queue.empty? # => キューは空です