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())

• Eric Duminil: You didn't implement a stack, you just delegate everything to a python list, which already implements a stack. See @rightleg answer.

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)

• Mees de Vries: Isn't l.pop(0) an O(n) operation?
• Voo: Inheriting from list to implement a stack is pretty awful. The point of APIs is to provide specific limited, documented functionality. I don't want users to be able to access or modify the middle of my stack or be confused why my stack class even has this functionality. Whether you actually need a stack is a different question.
• juhist: This suggestion to inherit completely fails "Composition over inheritance" principle.
• Right leg: Ok guys, thanks for the feedback! I updated my answer, taking all this discussion into account. That was truly enriching, and I defintely learnt things today.
• juhist: The argument is information hiding. By making the list a hidden implementation detail (preferably prefixed with underscore), a stack can be used only via its regular interface. The implementation is easier to change, too (for example, to linked list) if the implementation is not part of the interface.

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.

• Gloweye: You seem to believe that in Python, information hiding is a goal in itself. I would like to contest that.. If someone does (1), he's probably got a good reason for it, and otherwise deserves the exceptions he's gonna get. If someone wants (2), you can do exactly that with properties later on. Is there a place for _name in Python? Yes. But not for these reasons.
• snakecharmerb: @Gloweye If I don't want people to rely on an implementation detail of my code, I use the private variable convention to indicate that to readers of the code. As you say, it's up to them to respect the convention or not. On (2), I don't see how a property would help - if the replacement data structure's API differed from list code that relied on the list API would still break.
• Gloweye: A property can help because you can intercept the getting of obj.name and do whatever you want with it. Like return a proxy object with a list interface, if you care about that. But it's mostly that in basic python design, I think classes should be as simple as possible. Part of the beauty of python is that you don't -have- to make that sort of future considerations, because you don't lose any possibilities with NOT doing it. You're free to disagree, of course.

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()

• Graipher: instead of is_empty, one cane override the __bool__ method. Or just leave it out, because with __len__ implemented and no __bool__ defined, if stack will internally call if len(stack), which will call if stack.__len__() and use the fact that 0 is falsey.

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" )

• AlexV: Throwing IndexError is what I would expect and similar to what happens if you'd try to call pop() on an empty list ([].pop() -> IndexError: pop from empty list).
• nigel222: Sure, but the question says "a stack". A refectory stack doesn't error, it just continues to exist in a state of emptyness. Neither is more correct than the other. Seems pointless to precisely re-inplement what is already provided as a standard list object.

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