Hackerrank – Queues: A Tale of Two Stacks

Tue Feb 27 2018

Exercise: Queues: A Tale of Two Stacks

Site: Hackerank

Link: hackerrank

Language: Python

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.

I love changing languages while solving all those exercises between javascript, python, PHP, and ruby but this time I used python.

Let’s start {#letsstart}

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[0]
        pushes = self.pushes.getAll()
        if (len(pushes) > 0):
            return pushes[0]
        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.