La norma immutable.Queue en Scala se puede adaptar para funcionar así, para una complejidad amortizada. Sin embargo, tenga en cuenta que la operación peek devolverá una nueva cola o, de lo contrario, las llamadas consecutivas a peek bien podrían hacerse en O (n).
Puede ampliar Queue o crear una clase totalmente nueva adaptándola. Aquí hay una versión extenderla:
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) { }
}
O (1) costo amortizado de _what_? No tiene sentido hablar de la complejidad de una operación sin decir cuál es esa operación. En este caso, la operación es dequerante, que es similar pero no es igual a mirar a escondidas. –
Es O (1) costo amortizado por agregar y eliminar elementos. Al mirar, ¿te refieres a ver el elemento en la parte superior de la cola sin quitarlo? Esto se implementa fácilmente como una operación O (1): por ejemplo, se puede agregar trivialmente un campo adicional a la estructura de datos que recuerda el elemento superior. Mantener el tamaño funciona de la misma manera, como lo menciona Alex. –
@Daniel, ahora me doy cuenta de que se refería a echar un vistazo al elemento al final de la cola. En mi respuesta, este es solo el encabezado de la lista "de nuevo", así que de nuevo O (1) vez. Si uno necesita echar un vistazo a múltiples valores al final de la cola, uno puede asegurarse de que la lista "atrás" sea siempre lo suficientemente grande. –