【アルゴリズムの勉強】Rubyでデータ構造のキューを書いてみる

Ruby アルゴリズム

アルゴリズムの勉強としてリングバッファによるキューをRubyで実装する。

キューとは

キュー（英: queue）、あるいは待ち行列はコンピュータの基本的なデータ構造の一つ。データを先入れ先出し[1]のリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー[2]、取り出すことをデキュー[3]という。

キュー (コンピュータ) - Wikipedia

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?
# => キューは空です

参考文献、参考リンク