#
Peek

#===================================================================== # 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: # Look at the element at the top of the stack without removing it # # Time Complexity of Solution: # Best = Average = Worst = const. # # Technical Details: The self.primary stack is the real (i.e. # representative) stack. The self.minimums stack exists only for the # getMinimum function. If getMinimum were not important, all # operations could as well be performed on the self.primary stack # alone. # #===================================================================== def peek( self ): return self.primary.queue[self.primary.qsize() - 1]

import unittest from algorithms.StackWithGetMin import StackWithGetMin class StackWithGetMinTest( unittest.TestCase ): #===================================================================== # Test of peek method, of class StackWithGetMin. #===================================================================== def testPeek( 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() ) self.assertEquals( inputs[len( inputs ) - 1], stack.peek() ) self.assertEquals( inputs[len( inputs ) - 1], stack.peek() ) self.assertFalse( stack.isEmpty() ) self.assertEquals( len( inputs ), stack.size() )