When you first start thinking about queues in a functional language like Scala, there's a very tempting path you'll likely want to take. You'll think: "I'll just use a List and append new elements to the end using the :+ operator." It seems intuitive. It looks clean. But if you do this, you've accidentally built a performance time bomb.

The "Just Append to a List" Trap

Let's look at why that "simple" approach fails. In Scala, a List is a singly-linked list. Adding an element to the front (prepending) is a constant time $O(1)$ operation. But appending to the end requires the runtime to traverse the entire list to find the last element and then rebuild the list structure to maintain immutability.

// This looks fine, but it's O(n)
def enqueue(q: List[Int], item: Int): List[Int] = q :+ item 

If you have a queue with 10,000 elements, every single enqueue operation has to walk past those 10,000 elements. That's not a queue; that's a bottleneck. In a real production system, this would lead to an exponential slowdown as your data grows. I've seen this mistake land in code reviews more times than I can count because the syntax :+ hides the cost so effectively.

The Two-List Dance for Amortized Efficiency

To get the performance we actually need—amortized $O(1)$—we have to change how we store the data. Instead of one list, we use two. I like to think of them as the "In-box" and the "Out-box".

• The In-box: Where we push new elements. We always prepend here, so enqueue is always $O(1)$.
• The Out-box: Where we pull elements from. We take from the head, so dequeue is usually $O(1)$.

The "magic" happens when the Out-box becomes empty. Instead of failing, we take the entire In-box, reverse it, and make it the new Out-box. While reversing a list is an $O(n)$ operation, it only happens occasionally. If you spread that cost over all the elements that were pushed into the In-box, the average cost per operation remains constant. This is what we call "amortized" time complexity.

case class PersistentQueue[A](in: List[A] = Nil, out: List[A] = Nil) {
  def enqueue(elem: A): PersistentQueue[A] = 
    copy(in = elem :: in, out = out)

  def dequeue(): (A, PersistentQueue[A]) = out match {
    case head :: tail => 
      (head, copy(in = in, out = tail))
    case Nil => 
      // The "pivot" moment: reverse 'in' and move it to 'out'
      val reversed = in.reverse
      reversed match {
        case head :: tail => (head, copy(in = Nil, out = tail))
        case Nil => throw new NoSuchElementException("Queue is empty")
      }
  }
}

Notice how we never mutate anything. Each operation returns a new PersistentQueue. Because the underlying lists share tails, we aren't actually copying the whole data structure every time—we're just creating a few new nodes that point to existing ones. This is the core beauty of persistent data structures.

📋 Practical Task

Implementing a Purely Functional Persistent Queue

Your task is to implement a persistent queue from scratch. Instead of using a case class with default arguments, implement it using a sealed trait to handle the empty state more explicitly (avoiding the need to throw a NoSuchElementException).

Requirements:

• Create a sealed trait MyQueue[+A].
• Implement an Empty object that extends MyQueue.
• Implement a Queue case class that tracks the in and out lists.
• Implement an enqueue(elem: A): MyQueue[A] method.
• Implement a dequeue(): Option[(A, MyQueue[A])] method. It should return None if the queue is empty, and Some((value, nextQueue)) otherwise.
• Ensure that the dequeue logic correctly handles the transfer and reversal from the in list to the out list when the out list is exhausted.

Test your implementation with the following sequence:

val q0 = MyQueue.Empty
val q1 = q0.enqueue(1).enqueue(2).enqueue(3)
val (val1, q2) = q1.dequeue().get // Should be 1
val (val2, q3) = q2.dequeue().get // Should be 2
val q4 = q3.enqueue(4)
val (val3, q5) = q4.dequeue().get // Should be 3
val (val4, q6) = q5.dequeue().get // Should be 4