Solved

# Finding the maximum

Posted on 2004-11-30
202 Views
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!
0
Question by:Unimatrix_001

LVL 3

Accepted Solution

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

LVL 3

Author Comment

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

LVL 3

Expert Comment

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

LVL 3

Expert Comment

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

LVL 3

Author Comment

Thanks very much! So that's how it works! :) Thanks again! Points and feedback left (-:

Uni
0

## Featured Post

### Suggested Solutions

For customizing the look of your lightweight component and making it look opaque like it was made of plastic.  This tip assumes your component to be of rectangular shape and completely opaque.   (CODE)
This was posted to the Netbeans forum a Feb, 2010 and I also sent it to Verisign. Who didn't help much in my struggles to get my application signed. ------------------------- Start The idea here is to target your cell phones with the correct…
The viewer will learn how to implement Singleton Design Pattern in Java.
This video teaches viewers about errors in exception handling.