A friend of mine introduced me to the geeksforgeeks website. Today I was reading a couple of articles there and found an interesting brain teaser. By the way, if you have not seen that website you should definitely check it out. It contains interesting tips for implementing various algorithms.

**The question is:** “if you have an implementation of a stack how would you use it to implement a queue?”

This by itself is an interesting question, however let’s first implement a stack in Python. If you are familiar with python you might already know that one would usually use arrays when one needs a stack but implementing a stack in python is extremely easy. It is very similar to a linked list implementation. The only difference is the fact that push() writes to the head of the list and pop() takes the first element from the head. Below is my implementation of a stack in python

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class stack(object): def __init__(self, value = None, next = None): self.value = value self.next = next def push(self, value): oldstack = stack(self.value, self.next) self.value = value self.next = oldstack def pop(self): outputval = self.value self.value, self.next = self.next.value, self.next.next return outputval def isEmpty(self): if (self.value == None): return True else: return False |

I am interested to see if someone can simplify this even further. Let’s test our code now.

1 2 3 4 5 6 7 8 9 10 11 12 13 |
mystack = stack() mystack.push(10) mystack.push(9) mystack.push(15) print mystack.pop() print mystack.pop() print mystack.pop() print mystack.isEmpty() 15 9 10 True |

A more complete implementation of a stack structure with peek() and size is as following. The peek() method returns the last item without removing it. And size() returns the size of the stack by going through all elements so it is O(n)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
class stack(object): def __init__(self, value=None, next=None): self.value = value self.next = next def push(self, value): oldstack = stack(self.value, self.next) self.value = value self.next = oldstack def pop(self): outputval = self.value self.value, self.next = self.next.value, self.next.next return outputval def peek(self): return self.value def size(self): numelements = 0 nextval = self.next while (nextval != None): nextval = nextval.next numelements += 1 return numelements def isEmpty(self): if (self.value == None): return True else: return False if __name__ == "__main__": mystack = stack() mystack.push(10) print "Size = ", mystack.size() mystack.push(9) print "Size = ", mystack.size() mystack.push(15) print "Size = ", mystack.size() print mystack.pop() print mystack.pop() print mystack.peek() print mystack.pop() print mystack.isEmpty() |

Now that we have a stack, how can we use this data structure to implement a queue? The trick is you need two stacks. Let’s call these stack1 and stack2. You would push your data in stack1 and pop from stack 2 (if stack 2 is not empty). If stack2 is empty pop values from stack1 and push them one by one into stack2 until stack1 is empty. This logic can be implemented in various ways, one way that I can implement this is the following:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class queue(object): def __init__(self): self.stack1 = stack() self.stack2 = stack() def fillStack2(self): if (self.stack2.isEmpty()): while (not self.stack1.isEmpty()): self.stack2.push(self.stack1.pop()) def push(self, value): self.stack1.push(value) self.fillStack2() def pop(self): if (self.stack2.isEmpty()): raise NameError('Queue.Empty') outputval = self.stack2.pop() self.fillStack2() return outputval |

Now that we have implemented our queue using our stack structure let’s test it.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
a = queue() a.push(2) a.push(3) a.push(4) a.push(12) print a.pop() print a.pop() print a.pop() a.push(5) print a.pop() print a.pop() 2 3 4 12 5 |

This version of the queue is certainly not the best way to implement the queue (again you can build the queue on top of an array in Python) but it is certainly interesting.

The implementation of stack can be made to avoid multiple instantiations of the stack class:

#!/usr/bin/env python

class stack(object):

def __init__(self):

self.stack = []

def push(self, value):

self.stack.append(value)

def pop(self):

return self.stack.pop()

def is_empty(self):

return len(self.stack) == 0

if __name__ == '__main__':

mystack = stack()

mystack.push(10)

mystack.push(9)

mystack.push(15)

print mystack.is_empty()

print mystack.pop()

print mystack.pop()

print mystack.pop()

print mystack.is_empty()

`# False`

# 15

# 9

# 10

# True