queue.rb

class Queue
  def initialize
    @head = HeadNode.new
  end

  def size
    find_size(@head)
  end

  def push(object)
    tail.append(Node.new(object))
  end

  def pop
    @head.pop
  end

  private

  def tail
    find_tail(@head)
  end

  def find_tail(node)
    node.last? ? node : find_tail(node.next)
  end

  def find_size(node)
    node.last? ? 0 : 1 + find_size(node.next)
  end
end

class Node
  attr_reader :object, :next

  def initialize(object = nil)
    @object, @next = object, TailNode.node
  end

  def append(node)
    @next = node
  end

  def last?
    @next.tail?
  end

  def tail?
    false
  end
end

class HeadNode < Node
  def pop
    @next.object.tap { @next = @next.next }
  end
end

class EmptyQueueError < Exception
end

class TailNode < Node
  def self.node
    @tail_node ||= TailNode.new
  end

  def append(node)
    raise EmptyQueueError.new("Empty queue")
  end

  def object
    raise EmptyQueueError.new("Empty queue")
  end

  def next
    raise EmptyQueueError.new("Empty queue")
  end

  def tail?
    true
  end

  private

  def initialize
  end
end