第19章

queue函数队列

head：返回队列第一个元素；tail 返回除第一个元素之外的队列；append返回尾部添加了指定元素的新队列

class SlowAppendShow[T](elems: List[T]) {  def head = elems.head  def tail = new SlowAppendShow(elems.tail)  def append(x: T) = new SlowAppendShow(elems::: List(x))}

2种表达方式效率都不高

class SlowAppendShow1[T](smele: List[T]) {  def head = smele.last  def tail = new SlowAppendShow1(smele.init)  def append(x: T) = new SlowAppendShow1(x:: smele)}

 高效率的解决办法：

class Queue[T]{  private val leading: List[T] = Nil  private val tariling: List[T] = Nil  private def mirror = {      if (leading.isEmpty)          new Queue{tariling.reverse}      else       this    def head = mirror.leading.head    def tail = {      val q = mirror      new Queue(q.leading.tail, q.tariling)    }    def append(x: T) =      new Queue(leading, x:: tariling)  }}

 最终解决方案

trait Queue[T] {  def head: T  def tail :Queue[T]  def append(x: T):Queue[T]}

object Queue{  def apply[T](xs: T*): Queue[T] =    new QueuImpml[T](xs.toList, Nil)  private class QueueImpl[T](    private val leading: List[T] = Nil,    private val tarining: List[T] = Nil    ) extends Queue[T] {      def mirror =        if(leading.isEmpty)            new QueueImpl[T](tarining.reverse, Nil)            else          this     def head : T = mirror.leading.head     def tail: QueueImpl[T] = {       val q = mirror       new QueueImpl[T](q.leading.tail, q.tarining)     }    def append(x: T) =       new QueueImpl[T](leading, x:: tarining)  }}

变化型注解：

下界：