読者です 読者をやめる 読者になる 読者になる

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

アルゴリズムの勉強としてRubyでスタックを実装する。

スタックとは

スタックは、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し(LIFO: Last In First Out; FILO: First In Last Out)の構造で保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。
特にその具象としては、割込みやサブルーチンを支援するために極めて有用であることから、1970年代以降に新しく設計された、ある規模以上のコンピュータは、スタックポインタによるコールスタックをメモリ上に持っていることが多い。

スタック - Wikipedia

Rubyで実装

class Stack
  def initialize(capacity)
    @pointer = 0
    @max = capacity
    @stack = Array.new(capacity)
    p @stack
  end

  def push(value)
    if @pointer >= @max
      puts "スタックは満杯です"
    else
      @stack[@pointer] = value
      @pointer += 1
      p @stack
    end
  end

  def pop
    if @pointer <= 0
      puts "スタックは空です"
    else
      @pointer += -1
      puts "#{@stack[@pointer]}を取り出しました"
    end
  end

  def next_value
    if @pointer <= 0
      puts "スタックは空です"
    else
      result = @stack[@pointer - 1]
      puts "次に取り出される値は#{result}です"
    end
  end

  def search(value)
    for index in 0..(@pointer - 1)
      if @stack[index] == value
        puts "#{value}はスタック内に存在します"
        return
      end
    end
    puts "#{value}はスタック内に存在しません"
  end

  def clear
    @pointer = 0
    puts "スタックを空にしました。ポインタの位置は#{@pointer}です"
  end

  def capacity
    puts "容量のサイズは#{@max}です"
  end

  def number_of_data
    puts "スタックには#{@pointer}つのデータが格納されています"
  end

  def empty?
    if @pointer <= 0
      puts "スタックは空です"
    else
      puts "スタックはまだ空き領域が存在します"
    end
  end

  def full?
    if @pointer >= @max
      puts "スタックは満杯です"
    else
      puts "スタックはまだ空き領域が存在します"
    end
  end

  def dump
    if @pointer <= 0
      puts "スタックは空です"
    else
      for index in 0..(@pointer - 1)
        puts @stack[index]
      end
    end
  end
end

stack = Stack.new(5)
# => [nil, nil, nil, nil, nil]
stack.push(5)
# => [5, nil, nil, nil, nil]
stack.push(12)
# => [5, 12, nil, nil, nil]
stack.pop
# => 12を取り出しました
stack.push(2)
# => [5, 2, nil, nil, nil]
stack.push(52)
# => [5, 2, 52, nil, nil]
stack.next_value
# => 次に取り出される値は52です
stack.search(2)
# => 2はスタック内に存在します
stack.capacity
# => 容量のサイズは5です
stack.number_of_data
# => スタックには3つのデータが格納されています
stack.empty?
# => スタックはまだ空き領域が存在します
stack.push(87)
# => [5, 2, 52, 87, nil]
stack.push(12)
# => [5, 2, 52, 87, 12]
stack.full?
# => スタックは満杯です

参考文献、参考リンク