@Jun: Where is the constant complexity?? You gonna push and pop every element or do you have any specific algo :P

keep track of the highest value when you do a pop and push into the stack. simple.