**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

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.

## Leave a Reply