MegaQueue.scala

package Lab4

class MegaQueue[T] private (val L1 : List[T], val L2: List[T]) {
  def this(L : List[T]) {
    this(Nil, L)
  }

  def enqueue(elem: T): MegaQueue[T] = {
    new MegaQueue[T](L1, elem :: L2)
  }

  def dequeue(): (T, MegaQueue[T]) = L1 match {
    case x :: xs => (x, new MegaQueue[T](xs, L2))
    case Nil if !empty() => new MegaQueue[T](L2.reverse, Nil).dequeue()
    case Nil => throw new RuntimeException("Queue underflow")
  }

  def empty(): Boolean = {
    L1.isEmpty && L2.isEmpty
  }

  override def toString() : String = {
    "L1: " + L1.toString() + "\n" + "L2: " + L2.toString()
  }

  /* TODO(aolo2): max
  *
  * For T <= NUMERIC
  * max, last_max
  * enqueue - if (el > max) max = el
  * dequeue - if (el > max) max = last_max
  * + special case = empty queue
  *
  * */
}

object Main extends App {
  val mq = new MegaQueue[Int](List(1, 2))
  val mq2 = mq.enqueue(0)
  val (e, mq3) = mq2.dequeue()
  val (e2, mq4) = mq3.dequeue()
  val (e3, mq5) = mq4.dequeue()
  val (e4, mq6) = mq5.dequeue()
  println(mq)
  println(mq2)
  println(mq3)
  println(mq4)
  println(mq5)
  println(mq6)
}