Implementing a Stack with min() in both O(N) and O(1)
Naive version, pops in O(N) if min is popped. Corner cases: you cannot pop an empty stack; and when you pop the last element, min must be hardset to None.
class Node(object): def __init__(self, value): self.value = value self.next = None class Stack(object): top = None min = None def push(self, value): new_node = Node(value) if self.top is None: self.top = new_node self.min = self.top.value else: new_node.next = self.top self.top = new_node if self.top.value < self.min: self.min = self.top.value def pop(self): # popping an empty stack: if self.top is None: print 'cannot pop an empty stack' # popping the last element: elif self.top.next is None: self.top = None self.max = None else: # overwrite max if self.max == self.top.value: n = self.top.next self.max = n.value while n is not None: if n.value > self.max: self.max = n.value n = n.next self.top = self.top.next def minim(self): print 'min is ' + str(self.min) def show(self): n = self.top while n is not None: print n.value, n = n.next print s = Stack() s.push(10) s.push(20) s.push(5) s.push(5) s.show() s.minim() s.pop() s.minim() s.pop() s.minim()
Better version using a second stack, runs in O(1)
class Stack(object): def __init__(self): self.top = None self.max = [] def push(self, value): new_node = Node(value) new_node.next = self.top self.top = new_node if len(self.max) == 0: self.max.append(self.top.value) else: if new_node.value > self.max[-1]: self.max.append(new_node.value) def pop(self): if self.top is None: return else: if self.top.value == self.max[-1]: self.max.pop() self.top = self.top.next