AlexKVal

Let’s implement ‘Stack’ in Python

 Data structures/Tutorial  801  4 mins 
a = Stack()     # []
a.push('one')   # ['one']
a.push('two')   # ['one', 'two']
a.top()         # 'two'
a.push('three') # ['one', 'two', 'three']
a.top()         # 'three'
a.size()        # 3
a.pop()         # 'three'  ['one', 'two']
a.pop()         # 'two'    ['one']

This is the API I want to have for the ‘Stack’ data structure.

Let’s implement it in Python step by step.

The official documentation recommends using ’list’ when you need ‘Stack’.

I prefer to have a dedicated class with all the treats under the hood instead of just list and its append instead of push.

So let’s define the class

class Stack:
  __list = []

An alternative way of defining and instantiating the instance variable would be with constructor like this

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

But at this point, this looks like overkill, so let’s stick to the first variant.

Two _ in the __list name are there to make it kind of “private” and prevent accessing it directly like this

a = Stack()
a.__list # AttributeError: 'Stack' object has no attribute '__list'

First things first, I want this class to be a bit more user-friendly. Currently, it looks like this

Stack()
# <__main__.Stack object at 0x10df87fd0>

which is not helpful of course.

In Python this is done with the help of __str__() method that should return string. It would be logical to show the string representation of the __list content.

For this to happen there is str() builtin function which is just the instantiation of the str class. Isn’t that clever?

Here is what it looks like

class Stack:
  __list = []

  def __str__(self):
    return str(self.__list)

That’s it.

Now it behaves a bit more user friendly

a = Stack()
print(a)
# []

But without print, it is still cryptic

Stack()
# <__main__.Stack object at 0x10df87fd0>

For this to “fix” there is __repr__()

  # <skipped>
  def __repr__(self):
    return str(self)

Let’s check it out

Stack()
# []

Yay! 🎉

Next, let’s implement the stack’s push method.

class Stack:
  # <skipped>
  def push(self, el):
    return self.__list.append(el)

Yep. Our stack grows to the right and “pops” back to the left. The appending and removing values from the end of the list are O(1) operations in Python.

Check

a = Stack() # []
a.push('one')
a # ['one']

Now to the pop.

Luckily, the list already has the pop method that removes and returns the last item in the list; exactly what we need.

class Stack:
  # <skipped>
  def pop(self):
    return self.__list.pop()

Check

a = Stack() # []
a.push('one') # ['one']
a.push('two') # ['one', 'two']

a.pop() # 'two'
a # ['one']
a.pop() # 'one'
a # []

So far so good. There are two top and size methods left.

The size is the same as len() builtin function and the top is just a reading of the first element.

class Stack:
  # <skipped>
  def size(self):
    return len(self.__list)

  def top(self):
    return self.__list[0]

But here is a catch. If the list is empty, the top will raise the IndexError error

a = Stack()
a.top() # IndexError: list index out of range

So we need some kind of a fallback to None value. This is the null in Python.

Here is the adjusted version of the top method

class Stack:
  # <skipped>
  def top(self):
    return None if self.size() == 0 else self.__list[0]

It looks like we have everything in place. Here is the full code of the Stack class

class Stack:
  __list = []

  def push(self, el):
    self.__list.append(el)
    return self

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

  def size(self):
    return len(self.__list)

  def top(self):
    return None if self.size() == 0 else self.__list[0]

  def __str__(self):
    return str(self.__list)
  def __repr__(self):
    return str(self)

And it works as expected

a = Stack()     # []
a.push('one')   # ['one']
a.push('two')   # ['one', 'two']
a.top()         # 'two'
a.push('three') # ['one', 'two', 'three']
a.top()         # 'three'
a.size()        # 3
a.pop()         # 'three'  ['one', 'two']
a.pop()         # 'two'    ['one']

Let’s add the cherry 🍒 on the top 😊. Let’s allow for initial values.

To make it happen we need a constructor method, which is __init__() in Python.

class Stack:
  # __list = [] <= delete this line
  def __init__(self, initial=[]):
    self.__list = list(initial)

The initial=[] is the nice “trick” to provide a default value, so we still can initialize it empty a = Stack().

But when we need to provide an initial collection of values, we could do it as Stack([1,2,3]).

Also, the use of the list() class instantiator allows for any collection-like type to be used. E.g.

a = Stack( [1,2,3] )
a = Stack( (1,2,3) )

At this point, we have a pretty “full-fledged” Stack class at our disposal 🎉

I am using this not so complex example on purpose.

This way it is easier to learn bit by bit the different idioms along the way, and at the same time not being bored and overwhelmed by a complex problem at hand.

See Also: