スタックの元になる実際のデータを格納する配列と、スタックの最後に入れられたデータの位置を指すポインタを用意し、スタックにデータを追加するメソッド、スタックの最後にあるデータを読み出すメソッド、スタックからデータを削除するメソッドを用意すれば、スタックの基本部分は完成。
さらに、スタックが空だったり、満杯だったりするかどうかのチェック機能があればいい。
class SampleStack
def initialize( stackMaxSize )
@stackMaxSize = stackMaxSize
@stackTop = 0
@stack = Array.new(@stackMaxSize)
end
def push( val )
if (@stackTop == @stackMaxSize)
puts "もう一杯です！"
else
@stack[@stackTop] = val
@stackTop += 1
end
end
def pop()
if (@stackTop == 0)
puts "空っぽです！"
else
@stackTop -= 1
return @stack[@stackTop]
end
end
end
stack = SampleStack.new(5)
p stack.push(1)
p stack.push(2)
p stack.push(3)
p stack.push(4)
p stack.push(5)
p stack.push(6) # これは格納されない
p stack.pop
p stack.pop
p stack.pop
p stack.pop
p stack.pop
p stack.pop # これは取り出せない
●冨倉メモ
一応、こんな感じになるのでしょうけれど、そもそも Ruby では、Array クラスに push, pop メソッドが存在する上に、配列の大きさは動的に変更できるので、あまり意味はないかも。
#! /usr/bin/env ruby
# Usage : staple.rb [target_files]
# ----- 括弧のクラス ---------------------------------------------------
# Stapleクラスは自分の出現位置と対応する括弧のタイプを知っている
# また、前後関係も知っている
# ----------------------------------------------------------------------
class Staple
attr_reader :line, :column, :type, :next, :prev
def initialize( line, column, type )
@line = line # 出現行
@column = column # 出現場所
@type = type # 自身の括弧のタイプ
@next = nil # 次のノード
@prev = nil # 前のノード
end
# 対応する括弧のタイプ
def pare
case @type
when '('
str = ')'
when '{'
str = '}'
when '['
str = ']'
when ')'
str = '('
when '}'
str = '{'
when ']'
str = '['
end
return str
end
def setNext( target )
@next = target
end
def setPrev( target )
@prev = target
end
end
# ----- スタック -------------------------------------------------------
class StackByList
attr_reader :head, :last
def initialize
@head = nil
@last = nil
end
def push( line, column, type )
newStaple = Staple.new( line, column, type )
newStaple.setNext( nil )
# リストの最後に追加する
if @last != nil
@last.setNext( newStaple )
newStaple.setPrev( @last )
@last = newStaple
else
@head = @last = newStaple
newStaple.setPrev( nil )
end
end
def pop()
if @head == nil
return nil
break
end
ret = Staple.new( @last.line, @last.column, @last.type )
if last.prev == nil
@head = nil
else
@last.prev.setNext( nil )
end
@last = @last.prev
return ret
end
def getNode()
ret = Array.new
thisNode = @head
while thisNode != nil
ret.push(thisNode)
thisNode = thisNode.next
end
return ret
end
end
# ---------- 実行部分
START_PATTERN = /¥(|¥{|¥[/
END_PATTERN = /¥)|¥}|¥]/
line = 0
stack = StackByList.new # スタック
while string = ARGF.gets
column = 1
# 一文字ずつ読み込んで、括弧の開始であれば、スタックに追加。
# 括弧の終了であれば、スタックの最後と比較して一致していれば
# スタックから取り出し、不一致であれば、スタックに追加。
string.scan(/./).each do |char|
if char.match( START_PATTERN )
stack.push( line + 1, column, char )
column += 1
elsif char.match( END_PATTERN )
if stack.last != nil
if char == stack.last.pare
stack.pop
else
stack.push( line + 1, column, char )
end
else
stack.push( line + 1, column, char )
end
column += 1
end
end
line += 1
end
# 最終的にスタックに残っているものが括弧の対応が取れていない
stack.getNode.each do |e|
puts "#{e.line}行目の#{e.column}番目の #{e.type} が対応していません"
end
書籍ではリストとの組み合わせで実装されていますが、Ruby では、配列の大きさは動的に変更できるため、ここでは素直に書いてみます。
#! /usr/bin/env ruby
# Usage : staple.rb [target_files]
# ----- 括弧のクラス ---------------------------------------------------
# Stapleクラスは自分の出現位置と対応する括弧のタイプを知っている
# ----------------------------------------------------------------------
class Staple
attr_reader :line, :column, :type
def initialize( line, column, type )
@line = line # 出現行
@column = column # 出現場所
@type = type # 自身の括弧のタイプ
end
# 対応する括弧のタイプ
def pare
case @type
when '('
str = ')'
when '{'
str = '}'
when '['
str = ']'
when ')'
str = '('
when '}'
str = '{'
when ']'
str = '['
end
return str
end
end
# ---------- 実行部分
START_PATTERN = /¥(|¥{|¥[/
END_PATTERN = /¥)|¥}|¥]/
line = 0
stack = Array.new() # スタックを配列だけで書いてみる
while string = ARGF.gets
column = 1
# 一文字ずつ読み込んで、括弧の開始であれば、スタックに追加。
# 括弧の終了であれば、スタックの最後と比較して一致していれば
# スタックから取り出し、不一致であれば、スタックに追加。
string.scan(/./).each do |char|
if char.match( START_PATTERN )
staple = Staple.new( line + 1, column, char )
stack.push( staple )
column += 1
elsif char.match( END_PATTERN )
if stack.last != nil
if char == stack.last.pare
stack.pop
else
staple = Staple.new( line + 1, column, char )
stack.push( staple )
end
else
staple = Staple.new( line + 1, column, char )
stack.push( staple )
end
column += 1
end
end
line += 1
end
# 最終的にスタックに残っているものが括弧の対応が取れていない
stack.each do |e|
puts "#{e.line}行目の#{e.column}番目の #{e.type} が対応していません"
end
スタックが、最後に入れたものから取り出すのに対して、キューは、追加データは最後に入れ、取り出すときは最初に入れたものとなる。
ただし、これでは取り出した部分が空き状態になり、無題になるので、キューの末尾が配列の最後尾に達してしまった場合は配列の先頭に戻り、そこから再びデータを格納する「リングバッファ」という方法を取る。
実装としては、キューにデータを追加する機能、キューからデータを読み出す機能、キューからデータを削除する機能を作成することになる。
加えて、キューが空の状態、満杯の状態を判別できるようにすればいい。
class Queue
def initialize( size )
@size = size + 1
@queue = Array.new( @size )
@first = 0
@last = 0
end
def enqueue( val )
if (@last + 1) % @size == @first
puts "キューが満杯です"
else
@queue[@last] = val
@last = (@last + 1) % @size
end
end
def dequeue()
ret = nil
if @first == @last
return -1
else
ret = @queue[@first]
@first = (@first + 1) % @size
return ret
end
end
def printQueue
i = @first
while i != @last
print "#{@queue[i]} "
i = (i + 1) % @size
end
end
end
class Example
def main
q = Queue.new( 5 )
i = nil
while i != 0
puts "現在のキュー :"
q.printQueue
puts ""
puts "コマンド 0:終了 1:ジョブをためる 2:ジョブを実行"
i = gets.chomp.to_i
case i
when 1
puts "ジョブの識別番号（1〜1000）を適当に入力して下さい"
j = gets.chomp.to_i
if (j >= 1 && j <= 1000)
q.enqueue(j)
end
when 2
j = q.dequeue
if j == -1
puts "ジョブがないです"
else
puts "識別番号 : #{j} のジョブを実行中……"
end
end
end
end
end
ex = Example.new
ex.main