# //Used in call stack, undo/redo, routing # //Array implenentation (just use pop/push or shift/unshift) # //Recall that pop/push is more efficient than shift/unshift # //Indexes take up memory so linked list implenetation will be better # //Single linked implenetation of stack: class Node: def __init__(self, value, next=None): self.value = value self.next = next class Stack: def __init__(self, first=None, last=None, size=0): self.first = first self.last = last self.size = size #Similar to shift or insert(0, value). Adds to stack and returns size. Recall stack is LIFO def push(self, value): new_node = Node(value) if self.first == None: self.first = new_node self.last = new_node else: #stores current 1st property on stack temp = self.first #reset 1st property to be newly created one self.first = new_node #set new next property self.first.next = temp #increment stack self.size += 1 return self.size #in python, this would be pop(0). Similar to unshift. Removes first element on stack def pop(self): #special case if stakc is empty if self.first == None: return None temp = self.first #if there is only 1 node, set 1st node and last property to be None if self.first == self.last: self.last = None #self.first = None will be set in next line #for all scenarios except empty stack self.first = self.first.next self.size -= 1 return temp.value #useful to visualize reverse() or any other function works def print_stack_to_list(self): result = [] current = self.first while current: result.append(current.value) current = current.next print(result) s = Stack() s.push(1) s.push(2) s.push(3) s.print_stack_to_list() # [3, 2, 1] s.pop() s.print_stack_to_list() #[2, 1] # //these methods deal with 1st node bc thats what stacks do (LIFO) # // Big O: # // Insertion and Removal: O(1) **this is mainly what stacks are good for # // Access and Search: O(N)
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter