标题: [google面试题] \"Find minimum\" returns the smallest element in the stack [打印本页] 作者: 亮 时间: 2013-7-30 16:45 标题: [google面试题] \"Find minimum\" returns the smallest element in the stack 作者: 邢城 时间: 2013-7-30 17:07
Describe a stack data structure that supports "push","pop",and " findminimum"operations."Findminimum" returns the smallest element in the stack.Good Answer:Store two stacks,one of which contains all of the items in the stackand one of which is a stack of minima.To push an element,push it on to the firststack.Check whether it is smaller than the top item on these condstack;if so,pushit onto these condstack.To pop an item,pop it from the firs tstack.If it is the top element of these condstack,pop it from these condstack.To find the minimumelement,simply return the element on the top of these condstack.Each operationtakes O(1) time.