welcome to the 2nd part of the series of post on Data Structures. Topic is Stacks.
Stacks are a list-based data Structure. The idea is that we can keep putting elements on the top and they are easy to access. However, it is more difficult to acces the elements at the bottom.
Stacks are useful when you care more about the recent elements or the order in which you see and save elements.
push: insert an element
pop: remove an element
pop are constant time O(1).
- LIFO: Last In First Out
A stack can be implemented with a linked list:
One can use built-in functions to turn a python list into a stack:
- Add a few methods to the LinkedList class (check Quizz in Part I), and use that to implement a Stack.
There are 4 functions below to fill in:
class Element(object): def __init__(self, value): self.value = value self.next = None class LinkedList(object): def __init__(self, head=None): self.head = head def append(self, new_element): current = self.head if self.head: while current.next: current = current.next current.next = new_element else: self.head = new_element def insert_first(self, new_element): new_element.next = self.head self.head = new_element def delete_first(self): "Delete the first (head) element in the LinkedList and return it" if self.head: deleted_elt = self.head self.head = self.head.next deleted_elt = None # good practice to delete return deleted_elt else: return None def insert_first(self, new_element): new_element.next = self.head self.head = new_element class Stack(object): def __init__(self,top=None): self.ll = LinkedList(top) def push(self, new_element): self.ll.insert_first(new_element) def pop(self): "Pop (remove) the first element off the top of the stack and return it" return self.ll.delete_first() # Test cases # Set up some Elements e1 = Element(1) e2 = Element(2) e3 = Element(3) e4 = Element(4) # Start setting up a Stack stack = Stack(e1) # Test stack functionality stack.push(e2) stack.push(e3) print stack.pop().value print stack.pop().value print stack.pop().value print stack.pop() stack.push(e4) print stack.pop().value