You can do this using two stacks
---------------------------------------------------------------------------------------------------------------------------
Stack s, m;
Push(x):
s.push(x)
if(x > m.top())
if(x > m.top())
m.push(m.top())
else
m.push(x)
Pop():
m.pop()
return s.pop()
FindMin():
return m.top()
---------------------------------------------------------------------------------------------------------------------------
On 4/5/06, Kevin <[EMAIL PROTECTED]> wrote:
Can we design a data structure that has
O(1) time for push(), pop() and min()?
Using stack, we can not get min() in O(1).
Using heap, we can not get push() in O(1).
So any idea?
, 133470973390.236450, 270};
int main(){m[2]--?m[0]*=4,m[1]*=5,main():printf(m);}
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
- [algogeeks] Linear for push, pop and min()? Kevin
- [algogeeks] Re: Linear for push, pop and min()? Mohammad Moghimi
