Visualizing Stacks
Posted by Aly Sivji in Quick Hits
A stack is a linear data structure that holds a collection of items. We can define operations performed in a stack from the point of view of a user:
.push()- add item to top.pop()- remove and return item from top.peek()- return top most element.is_empty()-Trueif stack is empty, elseFalse
Elements inside of a stack follow a LIFO (last in, first out) order of operations. Stacks can be implemented as a linked list with a pointer to the top element.
In this post, we will explore the Stack ADT using the lolviz package that was featured in Episode 41 of the Python Bytes podcast.
Import the lolviz library to visualize data structures.
from lolviz import *
Create Node class. This will be the basis of the linked list.
class Node:
'''Holds data and pointer to next node'''
def __init__(self, value, next_node):
self.value = value
self.next_node = next_node
Create Stack class with a pointer to the top element and a variable with the number of elements.
class Stack:
'''Implement Stack as a linked list'''
def __init__(self):
self.head = None
self.count = 0
def is_empty(self):
return True if self.count == 0 else False
def size(self):
return self.count
def push(self, value):
'''Push item into stack'''
# point to where head is pointing
next_node = self.head
node = Node(value, next_node)
self.count += 1
self.head = node
def pop(self):
if self.is_empty():
raise IndexError('pop from empty stack')
node_to_pop = self.head
self.head = node_to_pop.next_node
self.count -= 1
return node_to_pop.value
def peek(self):
if self.is_empty():
raise IndexError('stack is empty')
return self.head.value
def draw(self):
'''Use lolviz to visualize data structure'''
return llistviz(self.head, valuefield='value', nextfield='next_node')
Let's create a new Stack and add elements to it.
stack = Stack()
stack.push(1)
stack.draw()
stack.push(2)
stack.draw()
stack.push(3)
stack.draw()
If we take a .peak() at the top most element, we should expect to get 3 back.
stack.peek()
3
Looks good!
Now we'll start to .pop() elements off the Stack.
stack.pop()
3
stack.draw()
stack.pop()
2
stack.draw()
stack.pop()
1
stack.draw()
The stack is now empty, we should get IndexError exception if we try to .pop().
stack.pop()
---------------------------------------------------------------------------
IndexError Traceback (most recent call last)
<ipython-input-15-50ea7ec13fbe> in <module>()
----> 1 stack.pop()
<ipython-input-3-3f28f4042a94> in pop(self)
24 def pop(self):
25 if self.is_empty():
---> 26 raise IndexError('pop from empty stack')
27
28 node_to_pop = self.head
IndexError: pop from empty stack
In this post we used lolviz to visualize a linked list implementation of a Stack. It seems like a great utility that can be used to teach introductory Computer Science concepts.
Comments