Push
by Isai Damier, Android Engineer @ Google

#=====================================================================
# 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:
  #   Add the given element to the stack.
  #
  # Time Complexity of Solution:
  #   Best = Average = Worst = const.
  #
  # Technical Details: If the stack is empty, then the given element
  #     is perforce also the minimum element on the stack. Therefore
  #     mark the element as minimum by also pushing it into the
  #     minimums stack. On the other hand, if the stack (i.e. the
  #     primary stack) is not empty, check if the new element is less
  #     than the current minimum element. If it is, make the new
  #     element the new minimum.
  #
  #     The explanation is slightly different from the actual code
  #     to give the reader a different viewpoint.
  #
  #=====================================================================
  def push( self, e ):
    if self.primary.empty() or e < self.minimums.queue[self.minimums.qsize() - 1]:
      self.minimums.put( e )

    self.primary.put( e )
import unittest
from algorithms.StackWithGetMin import StackWithGetMin

class StackWithGetMinTest( unittest.TestCase ):

  #=====================================================================
  # Test of push method, of class StackWithGetMin.
  #=====================================================================

  def testPush( self ):
    e = 0
    stack = StackWithGetMin()
    inputs = [40, 65, 5, 6, 32, 4, 7, 1, 2, 84, 9, 10]
    for i in inputs:
      stack.push( i )

    self.assertFalse( stack.isEmpty() )
    self.assertEquals( len( inputs ), stack.size() )