Implementing a stack and a queue in Python

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

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

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)

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:

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

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.

One thought on “Implementing a stack and a queue in Python

  1. 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

Leave a Reply

Your email address will not be published. Required fields are marked *