Bakers queue impl in rubby just cuz. It's probably broken or terrible.

queue.rb

class PersistentList
  attr_reader :length, :head, :tail
  include Enumerable
  EMPTY = Object.new
  class << EMPTY
    include Enumerable
    def length; 0; end
    def each(&block); end
    def to_s; "()"; end
    def cons(item); PersistentList.new(item, self); end
  end

  def initialize(head, tail)
    @head = head
    @tail = tail
    @length = tail.length + 1
  end

  def cons(item); return PersistentList.new(item, self); end

  def PersistentList.list(*items)
    ret = EMPTY
    while(items.length > 0)
      ret = ret.cons(items.pop)
    end
    return ret
  end

  def each
    l = self
    while(l.length > 0)
      yield(l.head)
      l = l.tail
    end
  end

  def to_s
    ret = "("
    self.each{|x|ret = ret + x.to_s + " "}
    ret[ret.length-1] = ")"
    return ret
  end

  def inspect; self.to_s; end

  def reverse
    ret = EMPTY
    self.each {|x| ret = ret.cons(x) }
    return ret
  end
end

class PersistentQueue
  attr_reader :front, :back, :length
  def initialize(front, back)
    @front = front
    @back = back
    @length = front.length + back.length
  end

  EMPTY = PersistentQueue.new(PersistentList::EMPTY, PersistentList::EMPTY)

  def PersistentQueue.queue(*items)
    items.reduce(EMPTY){|acc,item|acc.push(item)}
  end

  def push(item)
    if(@length == 0)
      return PersistentQueue.new(PersistentList.list(item), PersistentList::EMPTY)
    else
      return PersistentQueue.new(@front, @back.cons(item))
    end
  end

  def pop
    raise "Called pop on empty queue!" if(@front.length == 0)
    new_front = @front.tail
    if(new_front.length == 0 and @back.length > 0)
      return PersistentQueue.new(@back.reverse, PersistentList::EMPTY)
    else
      return PersistentQueue.new(new_front, @back)
    end
  end

  def peek
    raise "Called peek on empty queue!" if(@front.length == 0)
    return @front.head
  end
end