Visualizing Stacks
source link: https://alysivji.github.io/quick-hit-visualizing-stacks.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Siv Scripts
Solving Problems Using Code
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()
-True
if 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()
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.
Additional Resources
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK