Finding the maximum

Hi all!

Got a bit of a nasty one here... I'm implementing a custom stack with a few methods:

void push(String a);
String pop();
String largest();

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?

Thanks!
LVL 3
Unimatrix_001Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

udo_borkowskiCommented:
Try this approach:

Inside the "real" stack maintain a "helper stack" that always has the "largest" item of the real stack on top.

So when an item is pushed check if this is larger than the one on the helper stack and push it on the helperstack if yes.

If you pop an item check if it is the top of the helper stack and pop it, too (if yes).

This ways you implement largest by using  
         return helperStack.top()

And everything is O(1)  (no sorting required)

Udo
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Unimatrix_001Author Commented:
Thanks a lot udo! Hmm, I'm slightly confused:


1) If I put 4 on:

STACK              HELPER STACK
4                      4


2) If I then put 6 on:

STACK              HELPER STACK
6                      6
4                      4


3) If I then tried to put 2 on:

STACK              HELPER STACK
6                      6
4                      4

How do I do it, since it is lower than 6? Also what would I do if I pushed I on, since 5 is smaller than 6 but larger than 4? :-S
0
udo_borkowskiCommented:
It goes on like this

3) If I then tried to put 2 on:

STACK              HELPER STACK
2                      6
6                      4
4

(only on the real stack, not on helper since it is < 6)

4)  If I then tried to put 5 on:

STACK              HELPER STACK
5                      6
2                      4
6
4

(only on the real stack, not on helper since it is < 6)

Just keep in mind that I said that the help stack should always have the "largest" item of the real stack on top.
If you add a 5 to the real stack the largest item in the real stack is still 6, so the helper stack does not need to change.

If you now "pop" the stack (i.e. the 5) you leave the helper stack unchanged since it has not 5 on top.
Same when popping the 2.
When it comes to the 6 you also pop the 6 from the helper stack and the 4 becomes the "largest" item



0
udo_borkowskiCommented:
BTW: for your teacher (if there is one) you may need to "prove" that this is really doing the right thing. Key to this proof is that you prove that the "invariant":
- the help stack always has the "largest" item of the real stack on top

is true all the time, i.e. with the empty stack and after every operation performed in the stack (i.e. push, pop (, largest))

(The proof is left as an exercise to the reader ;-)
0
Unimatrix_001Author Commented:
Thanks very much! So that's how it works! :) Thanks again! Points and feedback left (-:

Uni
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.