Python Stack Implementation

Question

This is my Stack implementation in Python.

class Stack:
    def __init__(self):
        self.head = None
        self.size = 0

    def push(self, item):
        node = Node(item)
        if not self.head:
            self.head = node
        else:
            node.next = self.head
            self.head = node
        self.size += 1

    def pop(self):
        if self.size == 0:
            raise ValueError('Popping off an empty stack!')
        item = self.head.val
        self.head = self.head.next
        return item

    def peek(self):
        if self.size == 0:
            raise ValueError('Peeking into an empty stack!')
        return self.head.val

    def __iter__(self):
        return self

    def __next__(self):
        if self.head:
            curr = self.head
        else:
            raise StopIteration()
        self.head = self.head.next
        return curr.val

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

Need comments on primarily 3 aspects -

1. Is there anything, just plain wrong?
2. How to improve efficiency of this design?
3. What more can I add to make it an actually usable data structure beyond the ADT specification?

Answer 1

In terms of implementation, and making it more efficient, I don't think the linked list adds any particular value. I would rather see you implement the stack using a built-in list, which will improve both memory performance and speed.

So far, you have implemented push, pop, peek and iteration. Why iteration? I'm glad that it's destructive, but I don't understand why you felt you needed that.

I would suggest that you look at Python's Common Sequence Operations to see which you can implement. If you choose not to make the stack transparent, that's okay, but it might limit applicability. A transparent stack should be able to support in, count, maybe indexing, etc.

Likewise, have a look at the Mutable Sequence Types section and common operations. Also, check out the Abstract Base Classes for collections, and add whatever parent class(es) you implement.

Keep in mind that Python is a "consenting adult language." There is not a great regard for private data and access control. Instead, the expectation is that you will implement as much as you can, and not be surprised if someone wants to peek. So, I'd suggest trying to build as transparent and well-integrated a class as possible: allow accessing items on the stack via s[i] notation, support things like .find() and .count(), and inherit from whatever ABCs you support. If your stack is iterable, make sure you implement an Iterable abc. (Or Sequence, or Collection, or ...)

Answer 2

Your pop function has an error in it. Nevermind that this is using a linked list implementation - I think that Austin Hastings does a good job at explaining that you might want to use an in-built list, but as-is, if I try and pop from the list, it isn't adjusting the stack size, so it doesn't get to the proper error-handling case for an empty stack.

Consider the following test program, executed in the Python shell directly (for my purposes, I made stack become Stack since I use a local stack variable to hold the stack. I suggest you make the class name called Stack as such.):

>>> stack = Stack()
>>> stack.size
0
>>> stack.push("Test1")
>>> stack.size
1
>>> stack.push("Test2")
>>> stack.size
2
>>> stack.push("Test3")
>>> stack.size
3
>>> stack.pop()
'Test3'
>>> stack.pop()
'Test2'
>>> stack.pop()
'Test1'
>>> stack.size
3
>>> stack.pop()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/teward/pytmp/stackimplementation.py", line 18, in pop
    item = self.head.val
AttributeError: 'NoneType' object has no attribute 'val'
>>> 

As you can see, when you pop an object, it's not properly decreasing the value of the size of the stack, so we never hit '0' and therefore your error case.

Add a self.size -= 1 to your pop function so we actually can hit your error case.

As I said before, I also don't see any value to the linked list implementation here. That being said, you should make your capitalization match everywhere, so class stack: should become class Stack:, so my test program above works. And to be 'normalized' with how you're naming your classes.

---

An implementation using a built-in List Object within the Class:

Now, this is a better implementation, in my opinion. It correctly implements some of the concerns by myself and Austin in that it uses an in-built list function in Python3, and some other fun bits to implement everything you individually handle. It also properly handles iteration over the stack, so you can do something like object in stack to determine if an object is present in the stack. This can obviously be improved, of course, but helps to implement things with an internal list, and some python magic to actually get a valid stack size without having to track it as a separate value. Up to you if you want to take some inspiration here, but meh.

class Stack:

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

    @property
    def size(self):
        return len(self._stack)

    @property
    def count(self):
        return self.size

    def __len__(self):
        return self.size

    def pop(self):
        if self.size == 0:
            raise IndexError("Cannot pop from an empty stack.")

        item = self._stack[self.size - 1]
        self._stack.remove(item)
        return item

    def peek(self):
        if self.size == 0:
            raise IndexError("Cannot peek into an empty stack.")

        return self._stack[self.size - 1]

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

    def __iter__(self):
        return iter(self._stack)

Answer 3

A list (with the default operations) is already a stack

• append > push
• pop > pop (with the default value of -1 which pops the last appended/pushed element
• It does already implement len for you
• And it will already deliver the appropriate exceptions

You can simply subclass list and add an alias

class Stack(list):
    push = list.append

For the extra methods/properties you seem to need

class Stack(list):
    push = list.append

    @property
    def size(self):  # if you really need size rather than `len(mystack)`
        return len(self)

    count = size

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

You may always avoid the temptation of people manipulating your stack as a pure list with additions like:

class Stack(list):
    push = list.append

    def pop(self):  # no arguments
        return super().pop()  # will always pop(-1)

You would of course also need to control slicing.

Answer 4

I agree that you should use list if you're doing this in industry. However, I think you are doing this as a learning exersise, and so will review your code.

• You should use __len__ to return the length. This allows you to then use bool on the object to get if there are items in it.

  This allows you to standardize the checks to just if not self: raise ValueError().

  Rather than:

  def pop(self):
      if self.size == 0:
          raise ValueError('Popping off an empty stack!')
  
  ...
  
  def __next__(self):
      if self.head:
          curr = self.head
  

• Your functions __next__ and pop are the same, just with different errors. You may want to make them use either the same function, or the same code.

• If you change Node to take next, then you can drastically simplify push. This is as self.head defaults to None, and will be the next node if it's not.
• I don't think __iter__ should consume the stack. Instead I'd recomend making it return a copy of the stack.
• I think you should make head and size protected variables. And so re-name them to _head and _size.

This can get:

from collections import namedtuple


Node = namedtuple('Node', 'val next')


class Stack:
    def __init__(self):
        self._head = None
        self._size = 0

    def __iter__(self):
        node = self._head
        while node is not None:
            yield node.val
            node = node.next

    def __len__(self):
        return self._size

    def push(self, item):
        self._head = Node(item, self._head)
        self._size += 1

    def pop(self):
        if not self:
            raise ValueError('Popping off an empty stack!')
        node = self._head
        self._head = self._head.next
        self._size -= 1
        return node.val

    def peek(self):
        if not self:
            raise ValueError('Peeking into an empty stack!')
        return self._head.val