I want to show you a piece of code that looks perfectly fine on the surface. It's a classic implementation of a functional queue using two lists—the "inbox" and the "outbox." This is a pattern you'll see in almost every functional programming textbook. It's elegant, it's immutable, and if you look at the theory, the dequeue operation is $O(1)$ amortized.

case class PersistentQueue[A](inbox: List[A] = Nil, outbox: List[A] = Nil) {
  def enqueue(elem: A): PersistentQueue[A] = 
    PersistentQueue(elem :: inbox, outbox)

  def dequeue(): (A, PersistentQueue[A]) = outbox match {
    case head :: tail => (head, PersistentQueue(inbox, tail))
    case Nil => 
      // The "expensive" part: reversing the inbox
      val reversed = inbox.reverse 
      (reversed.head, PersistentQueue(Nil, reversed.tail))
  }
}

// A simulation of a high-frequency trading engine or a game loop
val q0 = PersistentQueue[Int]().enqueue(1).enqueue(2).enqueue(3).enqueue(4)
// The outbox is empty, so the next dequeue will trigger the O(n) reverse.
val (val1, q1) = q0.dequeue() 

// Here is where the bug happens: 
// We keep reusing q0 instead of the updated q1
val results = for (_ <- 1 to 1000) yield {
  q0.dequeue() 
}

The Performance Trap of the Two-Stack Queue

If this were a mutable queue, we'd be fine. We'd reverse the list once, and for the next $N$ operations, we'd be hitting the outbox in $O(1)$ time. That's how amortized analysis works: the expensive operation pays for the cheap ones that follow.

But we're in Scala, and this is a persistent data structure. When we call q0.dequeue() inside that loop, we aren't modifying q0; we are creating a new queue. Because we are reusing q0—the specific version where the outbox is empty—every single iteration of that loop triggers the inbox.reverse call. We've just turned an $O(1)$ amortized operation into a guaranteed $O(n)$ worst-case operation. In a production system, this is the kind of bug that passes unit tests but brings a server to its knees under a specific persistence pattern.

Breaking the Cycle with Memoized Laziness

To fix this, we need the "expensive" operation to happen only once, regardless of how many times we reference the state that triggered it. The secret is memoization. If we can make the reversal lazy, the first person to call dequeue will trigger the computation, and every subsequent call to dequeue on that same version of the queue will simply reuse the cached result.

In Scala, we can leverage LazyList (or lazy val) to achieve this. By ensuring the "rotated" version of the queue is computed lazily, the result is stored inside the object itself. Even if you hold onto a reference to the "pre-reversed" state, the runtime only performs the reversal once.

case class LazyQueue[A](inbox: List[A] = Nil, outbox: LazyList[A] = LazyList.empty) {
  def enqueue(elem: A): LazyQueue[A] = 
    LazyQueue(elem :: inbox, outbox)

  def dequeue(): (A, LazyQueue[A]) = {
    if (outbox.isEmpty) {
      // We create a LazyList from the reversed inbox.
      // The actual reverse doesn't happen until outbox.head is accessed.
      val newOutbox = LazyList.from(inbox.reverse)
      (newOutbox.head, LazyQueue(Nil, newOutbox.tail))
    } else {
      (outbox.head, LazyQueue(inbox, outbox.tail))
    }
  }
}

Now, when you call q0.dequeue() a thousand times, the first call computes the LazyList. The remaining 999 calls find that the LazyList is already evaluated and return the head immediately. We've restored our performance guarantees even in the face of persistence. I've seen developers spend days profiling "random" CPU spikes only to find exactly this: an amortized structure being used in a persistent way that triggers the worst case repeatedly.

📋 Practical Task

Implementing a Memoized Persistent Stack-Queue

Your task is to implement a PersistentDeque (Double-Ended Queue) that allows adding and removing from both ends. To prevent the amortized complexity trap we discussed, you must ensure that the internal "rebalancing" operation (moving elements from one list to another when one side is empty) is memoized.

Requirements:

• Implement pushFront[A](elem: A) and pushBack[A](elem: A).
• Implement popFront() and popBack().
• Use LazyList to ensure that if a user calls popFront() on the same version of the Deque multiple times, the rebalancing cost is only paid once.
• Ensure the pop methods return an Option[(A, PersistentDeque[A])] to handle empty queues gracefully.