# Scala algorithm: Make a queue using stacks (Lists in Scala)

Published

## Algorithm goal

Make a pure-functional queue using stacks (Lists). It would have the following methods: isEmpty: Boolean, enqueue(T), dequeue: Option[(T, Queue[T])].

Try to make it efficient, where possible.

## Test cases in Scala

assert(Queue.empty.isEmpty)
assert(Queue.empty.enqueue("A").dequeue.contains("A" -> Queue.empty))
assert(
Queue.empty.enqueue("A").enqueue("B").dequeue.map(_._1).contains("A")
)
assert(
Queue.empty
.enqueue("A")
.enqueue("B")
.dequeue
.map(_._2)
.flatMap(_.dequeue)
.map(_._1)
.contains("B")
)
assert(
Queue.empty
.enqueue("A")
.enqueue("B")
.dequeue
.map(_._2)
.flatMap(_.dequeue)
.map(_._2)
.flatMap(_.dequeue)
.isEmpty
)
assert(
Queue.empty
.enqueue("A")
.enqueue("B")
.dequeue
.map(_._2.enqueue("C"))
.flatMap(_.dequeue)
.map(_._1)
.contains("B")
)
assert(
Queue.empty
.enqueue("A")
.enqueue("B")
.dequeue
.map(_._2.enqueue("C"))
.flatMap(_.dequeue)
.map(_._2)
.flatMap(_.dequeue)
.map(_._1)
.contains("C")
)
assert(
Queue.empty
.enqueue("A")
.enqueue("B")
.dequeue
.map(_._2.enqueue("C"))
.flatMap(_.dequeue)
.map(_._2)
.flatMap(_.dequeue)
.map(_._2)
.flatMap(_.dequeue)
.isEmpty
)


## Algorithm in Scala

20 lines of Scala (compatible versions 2.13 & 3.0), showing how concise Scala can be!