アルゴリズムとデータ構造の要点メモ in ruby（スタック）

目的

技術面接のために修行を始める。
ウェブでの技術試験時にみやすいようにこのページにまとめる。
Rubyでそそくさと実装できることを目的とする。

配列 https://qiita.com/tsnb/items/983c32d83331de1e0bea
連結リスト https://qiita.com/tsnb/items/3028ee788ff77ebaaa5e

参考

• https://programming-place.net/ppp/contents/algorithm/index.html#header (分かりやすいです、書いた人あざます、この記事をRuby用にまとめてるだけです)

スタック（データ構造）

要点

スタックにとって、最低限必要な機能は以下のとおり
データを積む (push)
データを降ろす (pop)

必要な機能の要件だけが定義されているデータ構造を、抽象データ構造と呼ぶ。
実現方法は、配列でも連結リストでも良い。

実装1

• 配列で実現、rubyなので動的に配列のサイズ確保する
• push, pop
• is_emptyでスタックが空かどうか確認
• topでスタックの最上段の要素を参照
• clearでスタックを再作成

class Stack
  attr_reader :top

  def initialize
    @stack = Array.new
    @top = @stack.last
  end

  def clear
    @stack = Array.new
  end

  def is_empty
    @stack.empty?
  end

  def push(val)
    @stack.push(val)
    @top = @stack.last
  end

  def pop
    @stack.pop()
    @top = @stack.last
  end
end

s = Stack.new
s.top
s.is_empty
s.push(1)
s.top
s.is_empty
s.push(2)
s.top
s.pop
s.top
s.clear
s.is_empty

irb(main):028:0> s = Stack.new
=> #<Stack:0x00007fc7b602ac58 @stack=[], @top=nil, @size=0>
irb(main):029:0> s.top
=> nil
irb(main):030:0> s.is_empty
=> true
irb(main):031:0> s.push(1)
=> 1
irb(main):032:0> s.top
=> 1
irb(main):033:0> s.is_empty
=> false
irb(main):034:0> s.push(2)
=> 2
irb(main):035:0> s.top
=> 2
irb(main):036:0> s.pop
=> 1
irb(main):037:0> s.top
=> 1
irb(main):038:0> s.clear
=> []
irb(main):040:0> s.is_empty
=> true

実装2

• スタックの中身を表示
• 配列のサイズを指定して確保するようにする、領域が足りない場合に2倍に拡張する
• 配列サイズを指定するとnilが入ってしまうので、本当にnilを入れたい場合に困るため、独自のnilとして扱うStructを定義した（処理性能は・・rubyなので考えない!）

class Stack
  attr_reader :top, :stack

  def initialize(size)
    @struct_nil = Struct.new("MyNil", :x)
    @size = size
    @stack = arr_new(@size)
    @top = @stack.last
  end

  def clear
    @stack = arr_new(@size)
  end

  # 無理やりサイズ指定でStruct::MyNilクラスで値を埋めて初期化しているので
  #   uniqして残った値のクラスが定義したStruct::MyNilクラスと全て等しければempty
  def is_empty
    @stack.uniq.map {|v| v.class == Struct::MyNil}.count(false) == 0
  end

  def is_full
    @stack.uniq.map {|v| v.class == Struct::MyNil}.count(false) == @size
  end

  def push(val)
    if is_full
      @stack = arr_new(@size).concat(@stack)
      @size = @stack.size
    end
    @stack.rotate!
    @stack[-1] = val
    @top = @stack.last
  end

  def pop
    val = @stack.pop()
    @stack.unshift(mynil)
    @top = @stack.last
    val
  end

private
  def arr_new(size)
    Array.new(size, mynil)
  end

  def mynil
    @struct_nil.new(nil)
  end
end

irb(main):340:0> s = Stack.new(2)
(irb):294: warning: redefining constant Struct::MyNil
=> #<Stack:0x00007fc7b78170a0 @stack=[#<struct Struct::MyNil x=nil>, #<struct Struct::MyNil x=nil>], @top=#<struct Struct::MyNil x=nil>, @size=2, @struct_nil=Struct::MyNil>
irb(main):341:0> s.stack
=> [#<struct Struct::MyNil x=nil>, #<struct Struct::MyNil x=nil>]
irb(main):342:0> s.push(1)
=> 1
irb(main):344:0> s.stack
=> [#<struct Struct::MyNil x=nil>, 1]
irb(main):345:0> s.push(2)
=> 2
irb(main):346:0> s.stack
=> [1, 2]
irb(main):347:0> x = s.pop
=> 2
irb(main):348:0> x
=> 2
irb(main):349:0> s.stack
=> [#<struct Struct::MyNil x=nil>, 1]
irb(main):350:0> s.push(3)
=> 3
irb(main):351:0> s.stack
=> [1, 3]
irb(main):352:0> s.push(4)
=> 4
irb(main):353:0> s.stack
=> [#<struct Struct::MyNil x=nil>, 1, 3, 4]
irb(main):354:0> s.push(5)
=> 5
irb(main):355:0> s.stack
=> [1, 3, 4, 5]
irb(main):356:0> s.push(6)
=> 6
irb(main):357:0> s.stack
=> [#<struct Struct::MyNil x=nil>, #<struct Struct::MyNil x=nil>, #<struct Struct::MyNil x=nil>, 1, 3, 4, 5, 6]