Exercise: Queues: A Tale of Two Stacks
Just got back to my daily programming exercises and start with this nice question on implementing a queue with 2 stacks.
So the requirements are simply having a Queue with these methods:
- put(value) //add another element to the queue
- pop() //returns the first element
- peak() //previews the first element
Of course, I’m not suppose to use the built-in queue for any language I use, and Im suppose to do it with 2 Stacks.
First I need to have myself a “Stack” object, so I create one quickly:
class MyStack(object): def __init__(self): self.holder =  def getAll(self): return self.holder def size(self): return len(self.holder) def pop(self): return self.holder.pop(0) def put(self, value): self.holder.append(value)
this simply uses python list object for storage, and I push to the end and pop from the start.
Now let’s create our Queue
class MyQueue(object): def __init__(self): self.pushes = MyStack() self.pops = MyStack() def peek(self): pops = self.pops.getAll() if (len(pops) > 0): return pops pushes = self.pushes.getAll() if (len(pushes) > 0): return pushes return None def pop(self): if self.pops.size() == 0: for i in xrange(self.pushes.size()): self.pops.put(self.pushes.pop()) return self.pops.pop() def put(self, value): self.pushes.put(value)
The idea: I have one stack for pushes and one stack for pops. All pushes go to the first and when I pop I first check for the pops stack if it’s not empty I pop from it if its empty I fill it with the elements from the pushes stack.
put: nothing much here, just adding a value to my “pushes” stack.
pop: check if something in the pops stack if so take it out. If not then empty the pushes stack into the pops stack and then pop it from there.
peek: I simply return the first element of pops if it exists and if not the first from pushes.