Get Minimum
by Isai Damier, Android Engineer @ Google

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#=====================================================================
# Author: Isai Damier
# Title: Stack With Get-Min
# Project: geekviewpoint
# Package: datastructure
#
# Description: Normally, only the top of a stack is available for
#    peeking and popping. Here, however, the requirement is to make
#    the minimum value on the stack always viewable in O(1).
#    To that end, in addition to the primary stack of operation
#    (called primary), a separate stack (called minimums) must be
#    used to track the minimum value on the primary stack. The point
#    is not to pop the minimum value in O(1) that would require a
#    bit more work. Rather, the getMinimum function allows peeking
#    into the stack, as it were, to see the minimum value on the
#    stack.
#
#    Throughout the implementation it should be clear that the
#    primary stack is the real (i.e. representative) stack and that
#    the minimums stack is an auxiliary stack that exists only so
#    the getMinimum() function may exist.
#=====================================================================
  
  
 
from Queue import LifoQueue
class StackWithGetMin( object ):
 
  def __init__( self ):
      self.primary = LifoQueue()
      self.minimums = LifoQueue()
  #=====================================================================
  # Statement:
  #   Indicate the minimum value on the stack.
  #
  # Time Complexity of Solution:
  #   Best = Average = Worst = const.
  #
  # Technical Details: This one-line function is the reason for this
  #     whole datastructure. Notice how the minimums stack is not
  #     maintained here. minimums is maintained by the push and the
  #     pop functions. The only operation in getMinimum is peeking
  #     into the minimums stack. Nonetheless, the minimums stack
  #     exists entirely for this function.
  #
  #=====================================================================
  def getMinimum( self ):
    return self.minimums.queue[self.minimums.qsize() - 1]