Stack data structure in Python 3

Question

I have implemented a stack in Python 3, and it works well. If anything needs to be improved, I would appreciate the criticism.

class Stack:

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

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

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

        def pop(self):
            data = self.stack[-1]
            del self.stack[-1]
            return data

        def peek(self):
            return self.stack[-1]

        def sizeStack(self):
            return len(self.stack)

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.sizeStack())
print("Popped: ", stack.pop())
print("Popped: ", stack.pop())
print(stack.sizeStack())
print("Peek:", stack.peek())
print(stack.sizeStack())

Answer 1

From a pure Python standpoint, a list is already a stack if you narrow its methods down to only pop and append. l.append(x) will put x at the end of the list, and l.pop() will remove the last element of the list and return it.

So generally speaking, when you need a stack in Python, you'll just make a list and use append and pop. The same goes for queues, but you'd use l.pop(0) instead of l.pop().

Considering this, I would say it's just plain unpythonic to implement a stack structure; instead, just use a list, that really is a dequeue and thus can be used as both a stack and a queue.

---

That said, I understand that append is not the common naming for the stack structure, and that push makes the intent of the method more clear. Therefore, I would implement a stack as a direct subclass of list, and just "rename" the append method:

class Stack(list):
    def push(self, x):
        super().append(x)

If I wanted to make it more fool-proof, I'd also override pop so that it cannot take a parameter, unlike list.pop

class Stack(list):
    ...
    def pop(self):
        return super().pop()

Now the operation performed by the peek method can usually be done by stack[-1] (where stack is an instance of Stack), but it could be implemented just as follows:

class Stack(list):
    ...
    def peek(self):
        return self[-1]

---

Addendum

Some comments advising against subclassing list came out, notably mentioning the "composition over inheritance" principle. That was an enriching discussion, and I'd like to amend my answer accordingly.

I'm no expert in design patterns, but as I understand it, this principle advocates the use of composition instead of inheritance to provide more flexibility. One benefit of composition here is clearly to provide a cleaner API, with only the common stack methods and not insert, remove and so on that come from list and have no sense for stacks.

On the other hand, the inheritance I suggested happens to violate Liskov's substitution principle. Although there's no problem with adding push and peek methods with respect to this principle, my implementation changes the signature of the pop method, which is not allowed by this principle.

From this perspective, I think that not only composition is valid here and adds in the benefit of a clean API, but also that inheritance is plain incorrect here. Therefore, if I were forced to implement a stack class in Python, I'd go with composition and do as follows:

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

    def push(self, x):
        self._data.append(x)

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

    def peek(self)
        return self._data[-1]

    def __len__(self):
        return len(self._data)

But again, as I said, I would never do that in real life because a list can already serve as a stack, and stack = [] would perfectly convey how stack would be intended to be used.

---

References:

On the Liskov substitution principle:

• https://en.wikipedia.org/wiki/Liskov_substitution_principle
• https://stackoverflow.com/q/56860/7051394

On composition over inheritance:

• https://en.wikipedia.org/wiki/Composition_over_inheritance
• https://stackoverflow.com/a/53354/7051394 (also happens to mention Liskov principle)

Answer 2

On the whole the code is good, but I would look for three improvements:

1. Information-hiding: I would change self.stack to self._stack to indicate to readers of the code that this is an implementation detail that should not be accessed directly. Reasons:
   1. Mutating self.stack directly, for example self.stack.insert(2, 42) could break the expectations a client would have of the stack.
   2. You might choose to use a different data structure in the future, so clients that depended on self.stack being a list would fail.
2. Error handling: popping or peeking on an empty stack will raise an IndexError. It might be friendlier to raise a custom EmptyStackError, although a bare IndexError could still be ok, depending on ...
3. Documentation: ideally the code would have docstrings in accordance with PEP-257. Failing that, comments in the pop and peek methods explaining that an exception will occur on an empty stack are helpful to the reader, and document that the behaviour is intentional rather than a bug.

Answer 3

The code is clean. My major concern with how it looks is that your naming doesn't follow PEP8. Names should be snake_case, not camelCase. So isEmpty should be is_empty.

With how it works, I'd work on giving it consistent behavior with other collections.

Right now, you have a sizeStack method for returning the size. This should really be __len__ instead:

def __len__(self):
    return len(self.stack)

Why? Because now you can do this:

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(len(stack))  # Prints 3

You can now check the length using len like you can with list and other built-ins. __len__ and other methods that start and end with two underscores are ""magic""; they have special meanings behind the scenes. Here for example, len just delegates to a classes's __len__ method. I'd recommend looking over that page I linked to.

isEmptys could also be made a little more idiomatic by making use of the fact that empty lists are falsey:

def is_empty(self):
    return not self.stack

The major advantage here is nearly all collections are falsey when empty. With how you have it now, if you change what underlying structure your class uses, you'll need to remember to update the is_empty method, or self.stack == [] will always fail.

And instead of having an is_empty method, it's more idiomatic to just have a __bool__ method so your stack can be treated as a boolean value. See this answer to see how that can be done.

---

And list actually already has a pop method that does what you want. Your pop can just be:

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

Answer 4

One suggestion I didn't see is that you can replace isEmpty with __bool__. Then, you can check whether the stack is empty with if not stack. This is more in line with other python collections.

Answer 5

Overall looks good. Your code does assume the user is keeping accurate track of the state of the stack. I don't know the domain you're in here but that's something to keep in mind.
Some stack implementations throw a specific exception for this scenario.

Answer 6

Pop and peek will crash with IndexError if applied to an empty stack. This may be acceptable (and is the only thing to do if you regard None as stack-able data), but otherwise you could add the lines

if not stack: # or, if stack == [] 
    return None

and in push

if data is None:
    raise ValueError( "Attempt to push data=None onto the stack" )

Answer 7

There are a three improvements I can think of:

• self.stack == [] should be not self.stack
• Save the length of the list as you use the stack. That way, you can access the length in O(1)
• Make the variables private

This is what the code would look like at the end:

class Stack:
    def __init__(self):
        self.stack = []
        self.length = 0

    def isEmpty(self):
        return not self.stack

    def push(self, data):
        self.length += 1
        self.stack.append(data)

    def pop(self):
        self.length -= 1
        return self.stack.pop()

    def peek(self):
        return self.stack[-1]

    def sizeStack(self):
        return self.length