Implementing a Stack is a common problem that computer science students are asked to do while learning about data structures. Stacks are a data structure that implemenet the LIFO (last in, first out) principle. We can implement stacks using a linked list methodology or an array backed list.
In the real world, Python’s built in list object is one of many production tested objects that can and should be used for stacks. Our stack is a linked list implementation of a simple stack.
Here is the example code that we will work with followed by an explanation about how it works.
import unittest
class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node
def __str__(self):
if self.element:
return self.element.__str__()
else:
return 'Empty Node'
def __repr__(self):
return self.__str__()
class EmptyStackException(Exception):
pass
class Stack:
def __init__(self):
self.top = None
self.size = 0
def push(self, data):
self.top = Node(data, self.top)
self.size += 1
def pop(self):
if self.top:
val = self.top.element
self.top = self.top.next_node
self.size -= 1
return val
else:
raise EmptyStackException
def peek(self):
if self.top:
return self.top.element
else:
raise EmptyStackException
def empty(self):
return self.size == 0
def __str__(self):
elements = []
curr = self.top
while curr is not None:
elements.append(curr.element)
curr = curr.next_node
return elements.__str__()
def __repr__(self):
return self.__str__()
class TestStack(unittest.TestCase):
def __init__(self, method_name='runTest'):
super().__init__(method_name)
self.names = ['Bob Belcher',
'Linda Belcher',
'Tina Belcher',
'Gene Belcher',
'Louise Belcher']
def test_init(self):
stack = Stack()
self.assertIsNone(stack.top)
self.assertEqual(stack.size, 0)
def test_push(self):
stack = Stack()
for name in self.names:
stack.push(name)
names = list(self.names)
names.reverse()
self.assertEqual(names.__str__(), stack.__str__())
self.assertEqual(len(names), stack.size)
def test_pop(self):
stack = Stack()
for name in self.names:
stack.push(name)
self.assertEqual(stack.pop(), 'Louise Belcher')
self.assertEqual(stack.size, 4)
self.assertEqual(stack.pop(), 'Gene Belcher')
self.assertEqual(stack.size, 3)
self.assertEqual(stack.pop(), 'Tina Belcher')
self.assertEqual(stack.size, 2)
self.assertEqual(stack.pop(), 'Linda Belcher')
self.assertEqual(stack.size, 1)
self.assertEqual(stack.pop(), 'Bob Belcher')
self.assertEqual(stack.size, 0)
with self.assertRaises(EmptyStackException):
stack.pop()
def test_peek(self):
stack = Stack()
for name in self.names:
stack.push(name)
self.assertEqual(stack.peek(), 'Louise Belcher')
self.assertEqual(stack.size, 5)
stack = Stack()
with self.assertRaises(EmptyStackException):
stack.peek()
def test_empty(self):
stack = Stack()
self.assertTrue(stack.empty())
for name in self.names:
stack.push(name)
self.assertFalse(stack.empty())
if __name__ == '__main__':
unittest.main()
Node
Since this is a linked list implementation of a stack, we are going to begin with the Node class. The Node does the work of holding the data in the stack and contains a reference to the next item in the stack.
class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node
def __str__(self):
if self.element:
return self.element.__str__()
else:
return 'Empty Node'
def __repr__(self):
return self.__str__()
There isn’t a lot going on in this class in terms of methods. It has an __init__ method which takes optional element and next_node parameters that default to None. This class also implements __str__ and __repr__ so that debuggers such as PyCharm print out user readable information.
EmptyStackException
The EmptyStackException class is a custom exception that gets raised when client code attempts to remove items from an empty stack.
class EmptyStackException(Exception):
pass
This class doesn’t do anything other than subclass the Exception base class. For this reason, it’s implemented with a pass statement.
Stack
Stack is our main class the implements a Stack. We begin with the code for this class followed by an explanation about how it works.
class Stack:
def __init__(self):
self.top = None
self.size = 0
def push(self, data):
self.top = Node(data, self.top)
self.size += 1
def pop(self):
if self.top:
val = self.top.element
self.top = self.top.next_node
self.size -= 1
return val
else:
raise EmptyStackException
def peek(self):
if self.top:
return self.top.element
else:
raise EmptyStackException
def empty(self):
return self.size == 0
def __str__(self):
elements = []
curr = self.top
while curr is not None:
elements.append(curr.element)
curr = curr.next_node
return elements.__str__()
def __repr__(self):
return self.__str__()
__init__
The __init__ method intializes the data structure to an empty stack.
def __init__(self):
self.top = None
self.size = 0
We have two class variables in our stack. The first variable, self.top, is a Node that represents the last item inserted into the Stack. It’s next_node property points to the next item in the stack, and so one. The other class variable is self.size, which represents the number of items that are placed in the stack.
push
The push method is used to add items to the stack.
def push(self, data):
self.top = Node(data, self.top)
self.size += 1
Whenever we add items to a Stack, the newest Node becomes the top of the stack. If you remember back from our Node class, it’s __init__ method has an optional next_node argument we can use to initialize the new Node with it’s next_node. This works well for us here because we can pass self.top as the next_node of the new Node and then immediatly assign the new Node to self.top. In this way, the last item in the Stack get’s shifted right and the new item becomes the top of the Stack. The next line of code simply increments the size of the stack by one, thus completing the operation of adding (or pushing) an item onto the Stack.
pop
The pop method is opposite operation to the push method. This method removes an item from the Stack.
def pop(self):
if self.top:
val = self.top.element
self.top = self.top.next_node
self.size -= 1
return val
else:
raise EmptyStackException
The pop method needs to consider two possible cases. The fist case involves a Stack that has items on it and needs an item removed. The other case involves an empty stack. Let’s begin with the first case.
We start by checking if the stack has items. If the stack is empty, self.top is None. Assuming that self.top is not None, we begin by storing the data contained in self.top.element in a variable called val. Our next job is to delete that Node from the Stack by changing self.top to point at self.top.next_node. The original Node will get garbage collected by the Python runtime. Now that we have removed the Node, we need to shrink the size of the stack by one. After we decrease self.size, we can return val to the caller thus completing the pop operation.
If it turns our that the stack is empty, we need to notify the caller. I think it would be a very bad practice to simply return None, since calling pop() on an empty Stack would indicate a programming error. Thus, we raise EmptyStackException. The client code will either need to handle the Exception or allow the program to crash.
peek
The peek operation lets client code take a look at the first element in the Stack without removing the item.
def peek(self):
if self.top:
return self.top.element
else:
raise EmptyStackException
In this case, we just just need to return self.top.element if the stack has an item, or raise an EmptyStackException if the stack is empty.
empty
Clients of this class need to check if the Stack is empty prior to calling pop() or peek()
def empty(self):
return self.size == 0
This method simply returns True if self.size == 0 or False if self.size is non-zero.
__str__ and __repr__
We don’t need these methods to represent a Stack, but if you choose to implement them, debuggers such as the on found in PyCharm will use these methods to print more user friendly data to the debugger window.
def __str__(self):
elements = []
curr = self.top
while curr is not None:
elements.append(curr.element)
curr = curr.next_node
return elements.__str__()
def __repr__(self):
return self.__str__()
We are going to leverage Python’s list object to get a reader friendly String representation of our Stack. We start by making an empty list called elements. Then we create a curr variable that points at self.stop. Now, we are going to loop until the end of the Stack by checking if curr is None.
During each iteration of the while loop, we add curr.element to elements. Then we advance to the next node by assigning curr = curr.next_node. When we are done, we will return elements.__str__() which creates a String for us. The __repr__ method works by calling self.__str__().
Conclusion
This article is a simple linked list implementation of a Stack. Stacks are useful in cases where you need a LIFO data structure to track the order of which items are added to the stack. As you can see, a Stack is a much simplier data structure to implement than a linked list.
Stone Soup Programming 