Scala: Konvertieren der rekursiven Funktion in Iterativ mit Stack

Question

Der folgende Code ist der rekursive Code zum Aufteilen einer Liste in zwei Teile.

def split(lst:List[Int],lst1:List[Int],lst2:List[Int]): (List[Int],List[Int])= 
lst match{ 
    case Nil => (lst1,lst2) 
    case hd::Nil => (lst1,hd::lst2) 
    case hd::tail => split(tail.init,lst1:::List(hd), tail.last::lst2) 
} 

Ich möchte diese rekursive Funktion zu einem iterativen mit einem Stapel konvertieren.

Answer 1

Ich habe versucht, das Problem mit Stapel

aber es bringt in dem Code

Falls Sie nur eine einfache Lösung wollen ein Chaos und Komplexität nur zu lösen, ist dies die Antwort

def split(lst: List[Int], lst1: List[Int], lst2: List[Int]): (List[Int], List[Int]) = 
(lst1 ::: lst.take(lst.length/2), lst.drop(lst.length /2) ::: lst2) 

Answer 2

Hier ist eine Version mit Warteschlangen.

def iSplit(xs: List[Int]) = { 
    val first = scala.collection.mutable.Queue[Int]() 
    val second = scala.collection.mutable.Queue[Int]() 

    xs.grouped(2).foreach { e => 
     e match { 
     case List(a, b) => 
      second.enqueue(a, b) 
      first.enqueue(second.dequeue) 
     case List(a) => 
      second.enqueue(a) 
     } 
    } 
    (first.toList, second.toList) 
    } 

Wir first auf einen Stapel, auf Kosten eines ist aber das Problem für second

def iSplit(xs: List[Int]) = { 
    val first = scala.collection.mutable.Stack[Int]() 
    val second = scala.collection.mutable.Queue[Int]() 

    xs.grouped(2).foreach { e => 
    e match { 
     case List(a, b) => 
     second.enqueue(a, b) 
     first.push(second.dequeue) 
     case List(a) => 
     second.enqueue(a) 
    } 
    } 
    (first.toList.reverse, second.toList) 
} 

Reverse ändern können, dass wir die Dinge zu einem Ende hinzufügen möchten, und entfernen Sie die Dinge aus dem anderen Ende . Dies ist kein Stapel, sondern eine Warteschlange.

Also ich denke, Sie sollten Ihrem Professor sagen, es funktioniert besser mit Warteschlangen :)