Finding the maximum
Posted on 2004-11-30
Got a bit of a nasty one here... I'm implementing a custom stack with a few methods:
void push(String a);
Push and pop do what they say on the tin. Largest returns the longest string that is in the stack. The problem I have is that they all have to be in O(1) time. I'm not wanting a solution here. Is this actually possible??? I've thought about a few things:
1) Pushing and popping normally, but largest does a linear search, which of course then isn't O(1) time.
2) I sort the elements in a seperate stack as they are pushed, and then largest string is always at the bottom of this seperate stack. But, I cannot sort without breaking the O(1) time.
3) I've tried finding the largest as elements are pushed, but when the element with the lowest value is popped then I don't know what the next largest String is.
I've had a look at priority queues. But from what I gather they appear to do some sorting as well, which would break the O(1) time rule. Can anybody point me in the right direction please?