A fun twist on Queues from Stacks

There's too, too much to write about, but I'm going to make a little diversion known, because it blew my mind. I have to give credit where its due: this comes to us from the peerless Matt Wilde (cs dept.,facebook).

The problem is this: our friend Josh was given some screening questions to qualify for a programming interview (to make sure he wasn't one of those programmers who couldn't program), and one of the questions was "Recall that the Stack ADT contains push(E), pop(), ... Implement a Queue using a Stack."

Now, this interview question is very common, if you disallow what was almost certainly an error in the problem phrasing; usually it's "Implement a Queue given Stacks" or "If you had a library that produced Stacks, how would you implement a Queue?" (answer at the end, for those who don't know and/or don't want to figure it out.)

But the problem was unclear: using a Stack? Only a single instance? Is it even possible? The common solution to the common problem uses two stacks. Mr. Wilde came up with the following solution, which does in fact use only one instance of a stack: use the program's call stack, along with recursion, to keep track of intermediate values. Shown algorithmically (in Ruby, since it looks the most like pseudocode):

 def enqueue(element)
     @stack.push element
 end

 def dequeue
     if @stack.size == 1
         return @stack.pop
     elsif @stack.size > 1
         tmp = @stack.pop
         value = self.dequeue
         @stack.push tmp
         return value
     else
         raise EmptyStackException
     end
 end

Amazing! Here's the standard solution with two stacks:

 def enqueue(element)
     @first.push element
 end

 def dequeue
     if not @second.empty
         return @second.pop
     elsif @first.empty
         raise EmptyStackException
     else
         while not @first.empty
             @second.push @first.pop
         end
         return @second.pop
     end
 end

The intuition in this case is that you use one stack for enqueueing and another for dequeueing. When the dequeue stack becomes empty, you remove all elements from the enqueue stack into the dequeue stack. This puts the enqueued elements in the dequeue stack in reverse order, meaning you can pop them in the order they were inserted in.

This gives you constant-time performance on most enqueues and dequeues, with an occasional O(n) for when the dequeue stack runs out.