Queue.scala

class Queue[T](
  // 待ち行列の正順リスト
  private val leading:List[T],
  // 待ち行列の逆順リスト
  private val trailing:List[T]
){
  // 2つのリストの同期
  private def mirror = {
    if(leading.isEmpty) new Queue(trailing.reverse, Nil)
    else this
  }
  // 同期をとった正順リストから先頭要素を取ります
  def head = mirror.leading.head
  
  // 同期をとった正順リストからtailを
  // 逆順リストはそのままの待ち行列を返します
  def tail = {
    val q = mirror
    new Queue(q.leading.tail, q.trailing)
  }
  
  // 逆順リストについて先頭（待ち行列的には末尾）に要素を追加します
  def append(x:T) = new Queue(leading, x :: trailing)
}