A fun twist on Queues from Stacks

Hey! Thanks for reading! Just a reminder that I wrote this some years ago, and may have much more complicated feelings about this topic than I did when I wrote it. Happy to elaborate, feel free to reach out to me! 😄

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 it's 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.