キュー
5月 8th, 2008 admin Posted in Ruby, アルゴリズムとデータ構造, 今日のコード | 
今日も「アルゴリズムとデータ構造シリーズ」です。本日は「キュー」について。本当はスタックで逆ポーランド記法の式の計算をする予定でしたが面白くないのでスキップします。（逆ポーランド変換ならトライしますが）
キューとは
キューとは最初に入れたデータを最初に取り出すと言う特徴を持つデータ構造。行列などに例えられる。
「先入れ先出し」「First in first out(FIFO)」などと呼ばれる
キューではデータを入力することを「エンキュー」「push」などと表現し、出力させることを「デキュー」「pop」と表現する。
スタックに比べるとキューはWi○MXのあれとかプリンタのあれとか、そもそもqueueの直訳が待ち行列ですって感じで説明しやすい。
キューのデータ構造を配列で表現しようとするととても大きな配列が必要になるため、適当な大きさの配列の頭とお尻をくっつけて使う「リングバッファ」という方法がよくとられます。
リストを使ってキューを実現すればこの問題は発生しないのですが、今回は勉強なのでリングバッファを使ったキューを実装しました。
コード
RUBY:
-
#Queue
-
$KCODE = "SJIS"
-
QUEUE_EMPTY = -1
-
-
class Queue
-
def initialize(max)
-
@queue = Array.new()
-
@max = max
-
@first = 0
-
@last = 0
-
end
-
-
def enqueue(val)
-
if((@last + 1)%@max == @first)
-
p "ジョブが満杯です"
-
else
-
@queue[@last] = val
-
@last = (@last+1)%@max
-
end
-
end
-
-
def dequeue()
-
ret = nil
-
if @first == @last
-
return QUEUE_EMPTY
-
else
-
ret = @queue[@first]
-
@first = (@first+1)%@max
-
return ret
-
end
-
end
-
-
def print_all()
-
i = @first
-
while i != @last
-
print @queue[i].to_s + " "
-
i = (i+1)%@max
-
end
-
print "\n"
-
end
-
end
-
-
queue = Queue.new(5)
-
i = nil
-
while i != 0 do
-
print "現在のキュー\n"
-
queue.print_all
-
print "コマンドを入力して下さい\n0:終了 1:ジョブをためる 2:ジョブを実行\n"
-
i = gets.chomp.to_i
-
-
case i
-
when 1
-
print "ジョブの識別番号（1~1000）を適当に入力してください："
-
j = gets.chomp.to_i
-
queue.enqueue(j) if (j>= 1 && j <= 1000)
-
-
when 2
-
j = queue.dequeue
-
if j == QUEUE_EMPTY
-
print "ジョブがありません\n"
-
else
-
print "識別番号" + j.to_s + "のジョブを実行\n"
-
end
-
end
-
end
実行画面
まとめ
キューを使うようなプログラムを書いてみたいと思った。キューかっこいい！
あと、BASICみたいなプログラムが書けておもしろかった。
※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。
5月 8th, 2008 at 3:33:46
[...] キュー はてなに追加 MyYahoo!に追加 del.icio.usに追加 livedoorClipに追加 8 Responses to “Rubyでアルゴリズムとデータ構造” [...]