A fun twist on Queues from Stacks
Tuesday, March 16, 2010 :: Tagged under: pablolife. ⏰ 2 minutes.
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.
Thanks for the read! Disagreed? Violent agreement!? Feel free to join my mailing list, drop me a line at , or leave a comment below! I'd love to hear from you 😄