Стандарт immutable.Queue в Scala можно адаптировать для такой работы, для амортизируемой сложности. Однако обратите внимание, что операция peek вернет новую очередь, или, в противном случае, последовательные вызовы peek вполне могут быть выполнены в O (n).
Вы можете либо расширить Queue, либо создать совершенно новый класс, адаптируя его. Вот версия, расширяющая его:
import scala.collection._
import generic._
import immutable.Queue
import mutable.{ Builder, ListBuffer }
class MyQueue[+A] protected(in0: List[A], out0: List[A]) extends scala.collection.immutable.Queue[A](in0, out0) with GenericTraversableTemplate[A, MyQueue] with LinearSeqLike[A, MyQueue[A]] {
override def companion: GenericCompanion[MyQueue] = MyQueue
def peek: (A, MyQueue[A]) = out match {
case Nil if !in.isEmpty => val rev = in.reverse ; (rev.head, new MyQueue(Nil, rev))
case x :: xs => (x, this)
case _ => throw new NoSuchElementException("dequeue on empty queue")
}
override def tail: MyQueue[A] =
if (out.nonEmpty) new MyQueue(in, out.tail)
else if (in.nonEmpty) new MyQueue(Nil, in.reverse.tail)
else throw new NoSuchElementException("tail on empty queue")
override def enqueue[B >: A](elem: B) = new MyQueue(elem :: in, out)
// This ought to be override, but scalac doesn't think so!
def enqueue[B >: A](iter: Iterable[B]) =
new MyQueue(iter.toList.reverse ::: in, out)
override def dequeue: (A, MyQueue[A]) = out match {
case Nil if !in.isEmpty => val rev = in.reverse ; (rev.head, new MyQueue(Nil, rev.tail))
case x :: xs => (x, new MyQueue(in, xs))
case _ => throw new NoSuchElementException("dequeue on empty queue")
}
override def toString() = mkString("MyQueue(", ", ", ")")
}
object MyQueue extends SeqFactory[MyQueue] {
implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, MyQueue[A]] = new GenericCanBuildFrom[A]
def newBuilder[A]: Builder[A, MyQueue[A]] = new ListBuffer[A] mapResult (x => new MyQueue[A](Nil, x.toList))
override def empty[A]: MyQueue[A] = EmptyQueue.asInstanceOf[MyQueue[A]]
override def apply[A](xs: A*): MyQueue[A] = new MyQueue[A](Nil, xs.toList)
private object EmptyQueue extends MyQueue[Nothing](Nil, Nil) { }
}