Purely Functional Data Structure ch03.scala

object QueueTest {

    object Queue {
        def empty[T]: Queue[T] = Queue[T]()

        def queue[T](f: List[T], r: List[T]): Queue[T] = {
            f match {
                case Nil =>
                    Queue(r.reverse, Nil)
                case _ =>
                    Queue(f, r)
            }
        }
    }

    case class Queue[T](f: List[T] = Nil, r: List[T] = Nil) {
        def isEmpty: Boolean = {
            f.isEmpty && r.isEmpty
        }

        def snoc(v: T): Queue[T] = {
            Queue.queue[T](f, v +: r)
        }

        def head: Option[T] = {
            f match {
                case Nil =>
                    None
                case x :: xs =>
                    Some(x)
            }
        }

        def tail: Queue[T] = {
            Queue.queue[T](f.tail, r)
        }
    }


    def main(args: Array[String]): Unit = {
        var queue = Queue.empty[Int].snoc(1).snoc(2).snoc(3).snoc(4)
        println(queue)
        println(queue.head)
        queue = queue.tail
        println(queue.head)
        queue = queue.tail
        println(queue.head)
        queue = queue.tail
        println(queue.head)
        queue = queue.tail
    }
}