Pages

Hackerrank Queues: A Tale of Two Stacks

This Hackerrank problem asks us to emulate a queue using two stacks. The rationale for this apparently weird data structure could be that we know for sure that we are going to have a data traffic in a sort of wave on the seaside fashion. We have a huge number of pushes with (about) no peek or pop, and then a huge number of peek or pop.
The architect should have calculate that it is not worthy to implement a proper queue, maybe memory comes at a premium on that environment. Or whatever.
Actually, the real sense of it is to see in an interview if a candidate knows about stacks and queue, and how to deal with them.

As usual, before starting writing my python code, I jotted down a few tests, so to clarify to myself what I am going to do. If I get on some soft spot during development, I can always get back here and fatten up the case.
def test_enqueue(self):
    queue = MyQueue()
    queue.put(42)
    self.assertEqual(42, queue.peek())

def test_enqueue_2(self):
    queue = MyQueue()
    queue.put(42)
    queue.put(2)
    self.assertEqual(42, queue.peek())

def test_dequeue(self):
    queue = MyQueue()
    queue.put(42)
    queue.put(2)
    queue.pop()
    self.assertEqual(2, queue.peek())
As often happens in this kind of coding, we can blissfully ignore the possible exception. Here letting our MyQueue crash in case the user try to pop when it is empty is a non-issue.

I have to use to stacks. One would emulate the head of the queue, form which pop and peek would operate, the other the tail, where push will add its values. So, I found it natural to name them head and tail:
class MyQueue(object):
    def __init__(self):
        self.head = []
        self.tail = []
Being in python world, the most obvious choice is using lists as their data type.

The push method (here called "put", as suggested by the template provided) is a no-brainer. I just append the passed value to tail.
def put(self, value):
    self.tail.append(value)

Peek and pop will substantially operate in the same way, getting the data from the other stack. There is only a question. How I should ensure that the head is populate with the correct data. Let's delegate it to another method, and just write their core functionality, for the moment.
def peek(self):
    self.refill_head()
    return self.head[-1]

def pop(self):
    self.refill_head()
    return self.head.pop()

And this is the point of the exercise, refill_head(). When we get the first call to pop or peek, we need to retrieve the first value stored in the tail queue. To do that, we can simply move all data stored in that stack to the head stack. As a bonus we have also all the other data ready to be used for pop and peek. Remember that the tail stack is accessed only for pushing data, so it won't mind at all of what there is inside it. We can safely empty it any time we need more data from head. But beware, we can move it only when head is empty, otherwise we would mess up with the elements' order.
def refill_head(self):
    if not self.head:  # 1
        while self.tail:  # 2
            self.head.append(self.tail.pop())
1. If the head is not empty we can (actually, we must) delay the refilling.
2. Otherwise we move all the data from tail to head. Being both stacks, the order is respected.

No need for extra testing, the solution got accepted, and I pushed unit test and python script to GitHub.

No comments:

Post a Comment