Make a pure-functional queue using stacks (Lists). It would have the following methods:
Try to make it efficient, where possible.
Test cases in Scala
Algorithm in Scala
20 lines of Scala (compatible versions 2.13 & 3.0), showing how concise Scala can be!
The most straightforward implementation of a Queue would contain a single List, however in this case, we would have to choose between making
enqueue fast, or making
dequeue fast, because with a List, to get the tail element is an \(O(n)\) operation.
However, there is a more efficient way, which is to use an 'incoming' and an 'outgoing' List: so long as 'outgoing' is not empty, we can destructure it at O(1) cost, and we can enqueue to 'incoming' at O(1) cost. The only time where we would face a cost would be when 'outgoing' is empty, and 'incoming' is non-empty: then, we would have to convert the 'incoming' to 'outgoing' by reversal, which is an O(n) operation. However, amortized, it would be more efficient than the biased approach. (this is © from www.scala-algorithms.com)
Scala concepts & Hints
The 'Option' type is used to describe a computation that either has a result or does not. In Scala, you can 'chain' Option processing, combine with lists and other data structures. For example, you can also turn a pattern-match into a function that return an Option, and vice-versa!
Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.
Stack safety is present where a function cannot crash due to overflowing the limit of number of recursive calls.
This function will work for n = 5, but will not work for n = 2000 (crash with java.lang.StackOverflowError) - however there is a way to fix it :-)
In Scala Algorithms, we try to write the algorithms in a stack-safe way, where possible, so that when you use the algorithms, they will not crash on large inputs. However, stack-safe implementations are often more complex, and in some cases, overly complex, for the task at hand.
In Scala, tail recursion enables you to rewrite a mutable structure such as a while-loop, into an immutable algorithm.