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.
I just came here to post that Matt is pretty awesome. Also, that's a clever solution.
ReplyDeleteAww. You guys are awesome too.
ReplyDeleteOne thing to note is that the standard solution is actually amortized constant time, while the "one stack" solution will always dequeue in linear time.
So, this solution is really only good for being cheeky on weirdly phrased programming tests.