スタック
5月 6th, 2008 admin Posted in Ruby, 今日のコード | 2 Comments » 
まだまだ続く「アルゴリズムとデータ構造シリーズ」です。今回からスタック＆キューについてです。
スタックとは
スタックとは最後に入れたデータが最初に取り出される特徴をもつデータ構造の一つ。
「後入れ先出し」「Last in first out(LIFO)」などと呼ばれる。
スタックではデータを入力することを「積む」「Push」などと表現し、出力させることを「取り出す」「Pop」と表現する。
スタックが空なのにデータを取り出そうとしてしまうことをスタックアンダーフロー、逆にスタックが一杯になっているのにデータを積もうとしてしまうことをスタックオーバーフローと言う。
Rubyの場合は配列にpopとpushメソッドが標準であるため配列をスタックとして簡単に使うことができる。
さらにRubyの場合には配列のサイズも動的に変更できるため、いつも以上に無駄な感じがするので前回作ったリストを使って（まじめに？）スタックを書いた。
コード
-
#Stack
-
class Node
-
attr_accessor :prev,:next,:data
-
def initialize(data)
-
@data = data
-
end
-
end
-
-
class Stack
-
def initialize()
-
@current_node = Node.new(nil);
-
@current_node.prev = nil
-
end
-
-
def pop
-
#スタックのサイズが０ならnil
-
if @current_node.prev.nil?
-
nil
-
else
-
@current_node = @current_node.prev
-
@current_node.data
-
end
-
end
-
-
def push(x)
-
#スタックにデータを積む
-
@current_node.data = x
-
#次のノードを用意しリンクする
-
new_node = Node.new(x)
-
@current_node.next = new_node
-
new_node.prev = @current_node
-
-
#新しいノードをセットする
-
@current_node = new_node
-
end
-
end
-
-
stack = Stack.new()
-
stack.push(1)
-
stack.push(2)
-
stack.push(3)
-
p stack.pop() # 3 <-最後に入れたのが最初にでてきている
-
p stack.pop() # 2
-
p stack.pop() # 1 <-最初に入れたのが最後にでてきている
-
p stack.pop() # nil <-スタックアンダーフロー
応用
スタックに配列を使い、データの出し入れに配列のpopとpushメソッドを使用した場合と比較しました。
それぞれ１から10000までのデータをpushしてpopするというものです。以下Ruby配列版のコードです。
-
#Stack
-
stack = Array.new()
-
-
10000.times do |i|
-
stack.push(i)
-
end
-
-
until stack.pop == nil do
-
end
私の環境でRuby配列版が4.79秒、リスト版が1.79秒と2倍以上の差が開く結果になりました。
配列のサイズをガンガン広げるより早いんじゃないかと期待したんですが・・・Rubyのコードを読めばわかるのかな？
まとめ
スタックはとても単純で「だからなんなの？」という感じもしなくもないんですが、すごい便利な使い方があったりして驚かされます。
次回はこの応用として、括弧の対応調べとか逆ポーランド電卓にチャレンジしてみます。
※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。
5月 6th, 2008 at 3:54:00
[...] スタック はてなに追加 MyYahoo!に追加 del.icio.usに追加 livedoorClipに追加 6 Responses to “Rubyでアルゴリズムとデータ構造” [...]
5月 7th, 2008 at 2:46:50
[...] 昨日学んだスタックの応用でHTMLなどの括弧の対応が正しく取れているかどうかを判定するスクリプトを書きました。 "< "と">"が正しい順番で同じ数になっているかどうかを判定します。 [...]