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