Implementing Stack with Python

Question

I am trying to implement a simple stack with Python using arrays. I was wondering if someone could let me know what's wrong with my code.

class myStack:
     def __init__(self):
         self = []

     def isEmpty(self):
         return self == []

     def push(self, item):
         self.append(item)

     def pop(self):
         return self.pop(0)

     def size(self):
         return len(self)

    s = myStack()
    s.push('1')
    s.push('2')
    print(s.pop())
    print s

Solution 1

I corrected a few problems below. Also, a 'stack', in abstract programming terms, is usually a collection where you add and remove from the top, but the way you implemented it, you're adding to the top and removing from the bottom, which makes it a queue.

class myStack:
     def __init__(self):
         self.container = []  # You don't want to assign [] to self - when you do that, you're just assigning to a new local variable called `self`.  You want your stack to *have* a list, not *be* a list.

     def isEmpty(self):
         return self.size() == 0   # While there's nothing wrong with self.container == [], there is a builtin function for that purpose, so we may as well use it.  And while we're at it, it's often nice to use your own internal functions, so behavior is more consistent.

     def push(self, item):
         self.container.append(item)  # appending to the *container*, not the instance itself.

     def pop(self):
         return self.container.pop()  # pop from the container, this was fixed from the old version which was wrong

     def peek(self):
         if self.isEmpty():
             raise Exception("Stack empty!")
         return self.container[-1]  # View element at top of the stack

     def size(self):
         return len(self.container)  # length of the container

     def show(self):
         return self.container  # display the entire stack as list


s = myStack()
s.push('1')
s.push('2')
print(s.pop())
print(s.show())

Solution 2

Assigning to self won't turn your object into a list (and if it did, the object wouldn't have all your stack methods any more). Assigning to self just changes a local variable. Instead, set an attribute:

def __init__(self):
    self.stack = []

and use the attribute instead of just a bare self:

def push(self, item):
    self.stack.append(item)

Also, if you want a stack, you want pop() rather than pop(0). pop(0) would turn your data structure into a(n inefficient) queue.

Solution 3

I left a comment with the link to http://docs.python.org/2/tutorial/datastructures.html#using-lists-as-stacks, but if you want to have a custom type that gives you push, pop, is_empty, and size convenience methods, I'd just subclass list.

class Stack(list):
    def push(self, item):
        self.append(item)
    def size(self):
        return len(self)
    def is_empty(self):
        return not self

However, as I said in the comments, I'd probably just stick with a straight list here, as all you are really doing is aliasing existing methods, which usually only serves to make your code harder to use in the long run, as it requires people using it to learn your aliased interface on top of the original.

Solution 4

A stack is a container (linear collection) in which dynamic set operations are carried out as per the last-in first-out (LIFO) principle. There is only one pointer - top, which is used to perform these operations

CLRS implementation of stack using array:

class Stack:
    """
    Last in first out (LIFO) stack implemented using array.
    """
    def __init__(self, capacity=4):
        """
        Initialize an empty stack array with default capacity of 4.
        """
        self.data = [None] * capacity
        self.capacity = capacity
        self.top  = -1

    def is_empty(self):
        """
        Return true if the size of stack is zero.
        """
        if self.top == -1:
            return True
        return False

    def push(self, element):
        """
        Add element to the top.
        """
        self.top += 1
        if self.top >= self.capacity:
            raise IndexError('Stack overflow!')
        else:
            self.data[self.top] = element

    def pop(self):
        """
        Return and remove element from the top.
        """
        if self.is_empty():
            raise Exception('Stack underflow!')
        else:
            stack_top = self.data[self.top]
            self.top -= 1
            return stack_top

    def peek(self):
        """
        Return element at the top.
        """
        if self.is_empty():
            raise Exception('Stack is empty.')
            return None
        return self.data[self.top]

    def size(self):
        """
        Return the number of items present.
        """
        return self.top + 1

Testing the implemetation:

def main():
    """
    Sanity test
    """
    stack = Stack()

    print('Size of the stack is:', stack.size())
    stack.push(3)
    print('Element at the top of the stack is: ', stack.peek())
    stack.push(901)
    print('Element at the top of the stack is: ', stack.peek())
    stack.push(43)
    print('Element at the top of the stack is: ', stack.peek())
    print('Size of the stack is:', stack.size())
    stack.push(89)
    print('Element at the top of the stack is: ', stack.peek())
    print('Size of the stack is:', stack.size())
    #stack.push(9)    # Raises IndexError
    stack.pop()
    print('Size of the stack is:', stack.size())
    stack.pop()
    print('Size of the stack is:', stack.size())
    stack.pop()
    print('Size of the stack is:', stack.size())
    print('Element at the top of the stack is: ', stack.peek())
    stack.pop()
    #print('Element at the top of the stack is: ', stack.peek())    # Raises empty stack exception

if __name__ == '__main__':
    main()

Solution 5

The proper implementation would include __iter__ also since Stack needs to be LIFO order.

class Stack:
    def __init__(self):
        self._a = []

    def push(self, item):
        self._a.append(item)

    def pop(self):
        return self._a.pop()

    def isEmpty(self):
        return len(self._a) == 0

    def __iter__(self):
        return reversed(self._a)

    def __str__(self):
        # return str(list(reversed(self._a)))
        return str(list(iter(self)))

def main():
    stack = Stack()
    stack.push('a')
    stack.push('b')
    stack.push('c')
    stack.pop()
    print(stack)
    if stack:
        print("stack not empty")
    stack.pop()
    stack.pop()
    if stack.isEmpty():
        print("stack empty")

if __name__ == '__main__':
    main()

View more solutions

Comments

[user2357112]

That's not the main problem. The bigger issue is trying to assign to self.

[user2357112]

is_empty should return not self. Of course, doing this at all is probably a bad idea; it's trying to make the Python collection interfaces look like some other language.

[Silas Ray]

My mistake on the is_empty thing, I fixed that. As to your other point, I'd agree that you should probably just use the standard list interface in this case, but creating a subclass to implement an additional interface on an existing type is entirely reasonable, if you have legitimate need.

[user2687481]

how would you define pop? pop(self, item) : self.pop(item)?

[user2687481]

Thank you for your help.

[user2687481]

Thank you for your help.

[Silas Ray]

You don't need to, because list already has a pop that works exactly as you need it to without any arguments.

[Silas Ray]

You really should just use the list interface directly though, unless you need to have the aliased method names for some sort of homework assignment.

[skjoshi]

To make it a stack, the pop function should be def pop(self): return self.container.pop(-1)

[bgusach]

@Sanju or just self.container.pop().

[Raksha]

why does the last print output "<__main__.myStack object at 0x006C39D0>" ?

[Divakar Rajesh]

That’s what I too felt..everything the code does is already available as methods in List in python.. more info on how to use list as stack is available in the documentation docs.python.org/3/tutorial/datastructures.html

[Yahya]

AttributeError: 'Stack' object has no attribute 'stack' .. check your show(self) function

[Enis Arik]

self.size() does not work. It should either be self.container == [] or len(self.container) == 0

[Brionius]

@EnisArik Works for me - what error or unexpected behavior are you getting?

[Enis Arik]

@Brionius, ah it is my bad! I did not include the size method :) That was the issue.