Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

Finding the maximum

Posted on 2004-11-30
5
Medium Priority
?
243 Views
Last Modified: 2010-03-31
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
Comment
Question by:Unimatrix_001
  • 3
  • 2
5 Comments
 
LVL 3

Accepted Solution

by:
udo_borkowski earned 2000 total points
ID: 12705204
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

by:Unimatrix_001
ID: 12705350
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

by:udo_borkowski
ID: 12705695
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

by:udo_borkowski
ID: 12705773
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

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

Uni
0

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

An old method to applying the Singleton pattern in your Java code is to check if a static instance, defined in the same class that needs to be instantiated once and only once, is null and then create a new instance; otherwise, the pre-existing insta…
Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
Suggested Courses
Course of the Month13 days, 9 hours left to enroll

581 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question