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

感謝のプログラミング 10000時間

たどり着いた結果(さき)は、感謝でした。

「スタック」は様々なデータを順番に出したり入れたりする時に使うデータ構造。

<スポンサーリンク>

スタックとは?

後から入ってきたデータが先に出て行く、「後入れ先出し(Last In First Out:FIFO)」のデータ構造。
食器棚に入っているお皿のようなもの。
皿を使う時は、食器棚の上から順番に取っていく。
使い終わったお皿は皿の上にどんどん積んでいく。
そんな皿のように後から入れたものから出していくのがスタック構造である。
で、このやり方に従って扱われるデータの集合を「スタック」という。

スタックにデータを追加することをpush
スタックからデータを削除することをpopという。

スタックオーバーフローとスタックアンダーフロー

スタックオーバーフロー(StackOverFlow)とは、配列が満杯になっているのに、まだ追加してしまうこと。
スタックアンダーフロー(StackUnderFlow)とは、配列が空なのに、データを読み出したり削除しようとしてしまうことをいう。

Rubyでスタックを使うサンプル

以下にRubyでスタック構造を扱うサンプルを作ってみる。
例外の処理などはわざと変な名前でやっている感がある。

class SampleDoubleStack
  @stack_top
  @stack_max_size
  @stack
  attr_accessor:stack
  attr_accessor:stack_top
  def initialize(stack_max_size)
    @stack_top = 0
    @stack_max_size = stack_max_size
    @stack = Array.new(stack_max_size,nil)
  end

  catch :stack_over_flow do
    def push(val)
      if (@stack_top == @stack_max_size)
        throw:stack_over_flow
      else
        stack[@stack_top] = val
        @stack_top = @stack_top + 1
      end
    end
  end

  catch :stack_under_flow do
    def pop()
      if (@stack_top == 0)
        throw stack_under_flow
      else
        @stack_top = @stack_top - 1
        return stack[@stack_top]
      end
    end
  end

end

## Main ##
simple_double_stack = SampleDoubleStack.new(3)
begin
  puts "「push」か「pop」か「end」を入力してください."
  buf = gets.chomp
  if buf == "push"
    puts "pushしたい数値を入力してください!"
    push_num = gets.to_i
    simple_double_stack.push(push_num)
  end

  if buf == "pop"
    puts "popします"
    puts simple_double_stack.pop
  end
end until buf == "end"

Stack Over Flowを発生させる

「push」か「pop」か「end」を入力してください.
push
pushしたい数値を入力してください!
1
「push」か「pop」か「end」を入力してください.
push
pushしたい数値を入力してください!
2
「push」か「pop」か「end」を入力してください.
push
pushしたい数値を入力してください!
3
「push」か「pop」か「end」を入力してください.
push
pushしたい数値を入力してください!
5
C:/eclipse/pleiades/workspace/rubytest/stack/simple_stack.rb:16:in `throw': uncaught throw `stack_over_flow' (NameError)
	from C:/eclipse/pleiades/workspace/rubytest/stack/simple_stack.rb:16:in `push'
	from C:/eclipse/pleiades/workspace/rubytest/stack/simple_stack.rb:45

Stack Under Flowを発生させる

「push」か「pop」か「end」を入力してください.
push
pushしたい数値を入力してください!
23
「push」か「pop」か「end」を入力してください.
pop
popします
23
「push」か「pop」か「end」を入力してください.
pop
C:/eclipse/pleiades/workspace/rubytest/stack/simple_stack.rb:27:in `pop': undefined local variable or method `stack_under_flow' for #<SampleDoubleStack:0x3b4e47c> (NameError)
	from C:/eclipse/pleiades/workspace/rubytest/stack/simple_stack.rb:50
popします

勉強した本

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

プログラミングの宝箱 アルゴリズムとデータ構造 第2版


アルゴリズムとデータ構造のバイブルです。

感謝のプログラミング

今回で感謝のプログラミングは【609時間目】
10000時間まで、あと【9391時間】