Queue In Scala, используя список в scala

Question

Мы можем реализовать очередь в java, просто используя ArrayList, но в случае Scala списки являются неизменяемыми, так как я могу реализовать очередь с помощью List в Scala.Somebody, дайте мне некоторый намек на это.

Answer 1

С неизменными списками, вы должны вернуть новый список после любой операции модифицирования. Как только вы это поняли, это просто. Минимальный (но неэффективный) реализации, где очередь также может быть неизменны:

class Queue[T](content:List[T]) { 
    def pop() = new Queue(content.init) 
    def push(element:T) = new Queue(element::content) 
    def peek() = content.last 

    override def toString() = "Queue of:" + content.toString 
} 

val q= new Queue(List(1)) //> q : lists.queue.Queue[Int] = Queue of:List(1) 
val r = q.push(2)   //> r : lists.queue.Queue[Int] = Queue of:List(2, 1) 
val s = r.peek()   //> s : Int = 1 
val t = r.pop()   //> t : lists.queue.Queue[Int] = Queue of:List(2) 

Answer 2

Если мы говорим о mutable списках, они не были бы эффективная структура для реализации очереди по следующей причине: Добавление элементов в начало списка работает очень хорошо (занимает постоянного время), но появляются элементы с конца неэффективен (занимает больше времени, чем больше элементов в списке).

У вас, однако, есть Массивы в Скале. Доступ к любому элементу массива занимает постоянное время. К сожалению, массивы не имеют динамического размера, поэтому они не будут делать хорошие очереди. Они не могут расти по мере роста вашей очереди. Однако ArrayBuffers действительно растут по мере роста вашего массива. Так что это будет отличное место для начала.

Также обратите внимание, что Scala уже имеет класс очереди: scala.collection.mutable.Queue.

Единственный способ реализации очереди с immutable Список должен состоять в использовании var. Удачи!

Answer 3

Это из immutable Queue в Scala:

Очередь реализован в виде пары списков, одна из которых в элементах, а другой элементы из. Элементы добавляются в список и удаляются из списка. Когда список out запущен, очередь поворачивается, заменяя out-out на in.reverse и в Nil.

Итак:

object Queue { 
    def empty[A]: Queue[A] = new Queue(Nil, Nil) 
} 
class Queue[A] private (in: List[A], out: List[A]) { 
    def isEmpty: Boolean = in.isEmpty && out.isEmpty 

    def push(elem: A): Queue[A] = new Queue(elem :: in, out) 

    def pop(): (A, Queue[A]) = 
    out match { 
     case head :: tail => (head, new Queue(in, tail)) 
     case Nil => 
     val head :: tail = in.reverse // throws exception if empty 
     (head, new Queue(Nil, tail)) 
    } 
} 

var q = Queue.empty[Int] 
(1 to 10).foreach(i => q = q.push(i)) 
while (!q.isEmpty) { val (i, r) = q.pop(); println(i); q = r }