スタックとキュー（待ち行列）

キュー（待ち行列）の 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 "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 "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