Home / 別館 Home / Ruby / アルゴリズム / スタック&キュー
| 掲示板 | Mail |

スタック&キュー

スタック

基本的な考え方

 スタックの元になる実際のデータを格納する配列と、スタックの最後に入れられたデータの位置を指すポインタを用意し、スタックにデータを追加するメソッド、スタックの最後にあるデータを読み出すメソッド、スタックからデータを削除するメソッドを用意すれば、スタックの基本部分は完成。

 さらに、スタックが空だったり、満杯だったりするかどうかのチェック機能があればいい。


配列によるスタックの実装 (List4-1)
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 メソッドが存在する上に、配列の大きさは動的に変更できるので、あまり意味はないかも。

 応用例:括弧の対応を調べるスクリプト


スタックの応用:括弧の対応を調べるスクリプト (List4-2)
#! /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 では、配列の大きさは動的に変更できるため、ここでは素直に書いてみます。

スタックの応用:括弧の対応を調べるスクリプト 素直に Array クラスを利用してみる
#! /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


キュー

 基本的な考え方

 スタックが、最後に入れたものから取り出すのに対して、キューは、追加データは最後に入れ、取り出すときは最初に入れたものとなる。

 ただし、これでは取り出した部分が空き状態になり、無題になるので、キューの末尾が配列の最後尾に達してしまった場合は配列の先頭に戻り、そこから再びデータを格納する「リングバッファ」という方法を取る。

 実装としては、キューにデータを追加する機能、キューからデータを読み出す機能、キューからデータを削除する機能を作成することになる。

 加えて、キューが空の状態、満杯の状態を判別できるようにすればいい。


キュー (List4-4, 4-5)
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


【参考書籍】
 紀平拓男、春日伸弥 『プログラミングの宝箱 アルゴリズムとデータ構造』(ソフトバンク パブリッシング 2003)
 参考URL:http://www.cmagazine.jp/books/takarabako/

Home / 別館 Home / Ruby / アルゴリズム / スタック&キュー
| 掲示板 | Mail |

とみくら まさや(vzx01036@nifty.ne.jp) $ Date: 2004/01/11 $