#=====================================================================
# 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 whether this stack is empty.
#
# Technical Details: either primary.empty() or minimums.empty()
# is sufficient.
#
# Notice that the minimums stack will never be empty unless
# the primary stack is also empty; vice versa.
#
#=====================================================================
def isEmpty( self ):
return self.primary.empty()
import unittest
from algorithms.StackWithGetMin import StackWithGetMin
class StackWithGetMinTest( unittest.TestCase ):
#=====================================================================
# Test of isEmpty method, of class StackWithGetMin.
#=====================================================================
def testIsEmpty( self ):
stack = StackWithGetMin()
self.assertTrue( stack.isEmpty() )
self.assertEquals( 0, stack.size() )
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() )
