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

スタックとキュー(待ち行列)

Ruby アルゴリズム

キュー(待ち行列)の Ruby 実装例です。スタックは Array で実装されているので、キューだけ実装してみました。ただし既に Queue クラスが thread ライブラリに存在するので、クラス名は UserQueue にしました。

以下は限られた長さの配列を無駄なく使うために、エンキューが配列の端まで行くと、逆の端にループするようになっています。なので、配列がすべて埋まってしまうと overflow エラーになります。デキューもループします。空の配列にデキューすると、underflow エラーになります。

class UserQueue
  def initialize(length)
    @length = length
    @q = Array.new(@length)
    @head = 0
    @tail = 0
    @full = false
  end
  
  def enqueue(x)
    raise puts "overflow" if @head == @tail and @full
    @q[@tail] = x
    @tail = (@tail == @length - 1) ? 0 : @tail + 1
    @full = true if @head == @tail
    self
  end
  
  def dequeue
    raise puts "underflow" if @head == @tail and !@full
    x = @q[@head]
    @q[@head] = nil
    @head = (@head == @length - 1) ? 0 : @head + 1
    @full = false if @head == @tail
    x
  end
  
  def inspect
    @q.inspect
  end
  alias to_s inspect
end

q = UserQueue.new(3)
p q.enqueue(1).enqueue(2)    #=>[1, 2, nil]
p q.dequeue                  #=>1
p q.enqueue(5).enqueue(6)    #=>[6, 2, 5]
p q.dequeue                  #=>2

キューは先に入れたものから先に出ます。これを FIFO (First In First Out) と言います。入出力のバッファなどがそれです。対して、スタックは後に入れたものが先に出ます。これを LIFO (Last In First Out) と言います。

じつは Ruby は Array で両頭キュー(double-ended queue)を実装しているので、組み込みを使えばキューも簡単に実現できてしまうのですが。

class UserQueue
  def initialize; @q = []; end
  def enqueue(x); @q.push(x); self; end
  def dequeue; @q.shift; end
end

ただし Ruby の実装ではエンキューで配列が端に到達してもループせず、配列の長さが伸びていきます。また、空になった配列にデキューしてもエラーにならず、ただ nil が返るだけです。


二つのスタックでキューを実装することができます。

class UserQueue
  def initialize; @q1 = []; @q2 = []; end
  def enqueue(x); @q1.push(x); self; end
  
  def dequeue
    if @q2.empty?
      s = @q1.size
      s.times {@q2.push(@q1.pop)}
    end
    @q2.pop
  end
end

エンキューは変数 @q1 にプッシュ、デキューは変数 @q2 からポップで行います。ただし @q2 が空の場合は、@q1 をすべてポップして @q2 に順にプッシュし、つまりは順序を逆にして移し替えてしまいます。これで可能です。

まったく同様に、二つのキューでスタックを実装することもできます。同じなので省略。

max優先度付き待ち行列(maxプライオリティキュー)についてはこちらを。

アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (世界標準MIT教科書)

アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (世界標準MIT教科書)

p.192-194