This week's giveaway is in the Android forum.
We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line!
See this thread for details.
The moose likes Java in General and the fly likes Find max element in Stack Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Find max element in Stack" Watch "Find max element in Stack" New topic
Author

Find max element in Stack

Birel Chowdhury
Greenhorn

Joined: Nov 03, 2010
Posts: 8
Hi,

I want to implement a function max() which will find the max number in Stack without traversing the whole list. I should track of max number every time I push or pop. I used Linkedlist for implementation. Please give me the java code. The idea is max() function should not be expensive if there are millions of elements in the stack. Your help will be greatly appreciated.

Thanks.
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3603
    
  14

Why can't you do this yourself?
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4344
    
    8

Birel Chowdhury wrote:Please give me the java code.

We don't work like that here. We're more interested in helping people find their own solutions, as they'll learn better that way. So, presumably you've tried to think about how you'd do this. How far did you get?
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

do you think that is possible without traversing the whole list ?
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4344
    
    8

Seetharaman Venkatasamy wrote:do you think that is possible without traversing the whole list ?

Yes
Birel Chowdhury
Greenhorn

Joined: Nov 03, 2010
Posts: 8
Hi all,

My implementation was as follows:

[Added code tags - see UseCodeTags]

Instead of using for loop, should I call max method in push and pop method. So everytime I can check what is the max number. Please help me.

Thanks.

Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4344
    
    8

Your initial statement said you should
track of max number every time I push or pop

So think about that. You have a stack, and you know the maximum value in it is 99. If I give you another number to add to the stack, do you need to traverse the whole stack to know what the new maximum is?

Popping's going to be a bit trickier, though - I'd start by getting it to work with just push to begin with.

By the way - if and when you do need to traverse the whole list...don't use a for loop. Use an enhanced for loop - the for(int n : stackList) syntax. The code will be much cleaner, and it will be far more efficient when you have a large list (LinkedLists are not good for random access!)
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11169
    
  16

I'm not sure how you CAN do it on a pop without traversing...

you have a stack with a max value of 84...if you pop off a value of 17, you're still good. But what is the max value after popping off the 84? unless you maintain a sorted list, I don't see a way to do it.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Birel Chowdhury
Greenhorn

Joined: Nov 03, 2010
Posts: 8
Hi Matthew,

Thank you for your reply. Should I keep track of maximum for each node? Can I have a variable called maxsofar and it gets updated everytime I push.

[Added code tags]

Does this code look ok? For pop, if I can expose the second next element's max after popping that may work. Please help.
Thanks.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4344
    
    8

fred rosenberger wrote:unless you maintain a sorted list

Which would work . But would be more trouble than it's worth. I'd have thought occasional traversal would be OK - you'd only have to do it on the occasions you popped the current maximum value. On a large stack that would be very infrequent unless the data was tending to increase.
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Okay, you can think in another direction: create an Object say, IntWrap which holds integer of value, max and min...
Birel Chowdhury
Greenhorn

Joined: Nov 03, 2010
Posts: 8
Hi,

I am only allowed to pass int primitives in my push or pop method in driver class. How can I implement object here? Does my previous max() method look ok for push? Please help.

Thanks
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4344
    
    8

You're on the right lines, but you seem to be trying to use one method to do two things.

- Update the variable that keeps track of the maximum value
- Returns the maximum value outside the class

I'd keep these separate. The method used from outside the class really ought to be public int max(), like your original code.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11169
    
  16

Birel Chowdhury wrote: Does my previous max() method look ok for push?

The best way to tell if it is ok is to TEST IT.

Seriously.

Write some test cases. put values on your stack. Pay attention to what you put in. you should therefore know what the MAX should be - see if it is.

then, do it again. Make sure you test what happens if your stack is empty.

I'm not sure you need the "else" branch in the maxforPush() method. And why does the method return something if you don't bother to save it? I would think you could make it a void method.
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Birel Chowdhury wrote:
I am only allowed to pass int primitives in my push or pop method in driver class. How can I implement object here?

Hmmm. but you can assemble an object inside push.

edit: If you only concern about max, you can ignore/remove int min from IntWrap...
Birel Chowdhury
Greenhorn

Joined: Nov 03, 2010
Posts: 8
Give me some thoughts for pop method. Some code or psuedocode please. Thanks
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

Birel Chowdhury wrote:Give me some thoughts for pop method. Some code or psuedocode please. Thanks


Here's some thoughts (or at least, one thought): Explain what the pop method is supposed to do. That's the first step required in the process of implementing it, so start there. The second step would be to write the code to do that, but don't start with the second step.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3003
    
    9
What happens if you pop() the maximum element? How would you find the new maximum, without scanning everything again? And what if you later manage to pop() the new max? And later, yet again?

I would say that it's not enough to just remember the current maximum. You really need a data structure that you can use to retrieve the second, third, and fourth maxima. All of them really, if needed.

frosenberger wrote:unless you maintain a sorted list

This is what I would advocate as the simplest approach, assuming this is a problem the student needs to code for themselves. If they're allowed to use standard libraries, I would suggest a PriorityQueue instead, as that is probably the optimal data structure for this. And if they're not allowed to use PriorityQueue, it might still be useful to read about priority queues and code it oneself.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11169
    
  16

Mike Simmons wrote:I would suggest a PriorityQueue instead

I guess that is another question that needs to be answered. As I understand, a PriorityQueue will always return the least element. That may not work if you need the elements popped off in the order they were pushed, but ALSO need to know the maximum buried in there...somewhere...

If you always want to pop the max (or minimum - same thing, really), then to find the max, wouldn't you just peek at the top element to find the max?
Birel Chowdhury
Greenhorn

Joined: Nov 03, 2010
Posts: 8
Hi all,

What happens if I take the following approach:

> when I pop off an element, I will expose the element in the stack one step below the top, which already has the maximum and minimum values in the rest of the stack stored alongside it.
I think this is the key step that makes the answer possible. You are essentially trading memory for speed. Given the requirement that speed was top priority, this is the right way to go. (It should be noted that memory is relatively cheap these days, compared to faster processors.)
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3003
    
    9
fred rosenberger wrote:
Mike Simmons wrote:I would suggest a PriorityQueue instead

I guess that is another question that needs to be answered. As I understand, a PriorityQueue will always return the least element.

Well, you can pass it a Comparator to make it return the largest element. Whichever you like.

fred rosenberger wrote:That may not work if you need the elements popped off in the order they were pushed, but ALSO need to know the maximum buried in there...somewhere...

Mmmm, I should have clarified, I was assuming we were talking about maintaining a sorted list or PriorityQueue in addition to a conventional stack structure. You'd still use the conventional stack for maintaining the stack-lick properties you want. You'd just use the list or PriorityQueue to find the maximum. With each push() and pop(), you insert or remove elements from both data structures, maintaining them in parallel.

However, I've now realized that this would also require a pq.remove(element) as part of each pop() operation. This, unfortunately, is a linear-time operation, as a PriorityQueue is not optimized to retrieve arbitrary members. If the original objective was to avoid a linear scan of the Stack, having a linear remove() doesn't seem much better. Drat.

Maybe it would be better to use a TreeSet instead of the PriorityQueue or List. Then you'd have most operations be logarithmic, not linear. That should do well. If you need to support duplicate elements, well, there are a couple ways to work with that too. Maybe use a TreeMap<Foo,Integer> to keep track of how many identical instances of Foo are present? Yeah, that's the ticket.

If you always want to pop the max (or minimum - same thing, really), then to find the max, wouldn't you just peek at the top element to find the max?
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3003
    
    9
However I like Birel's latest answer much better.
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4446
    
    5

This is a very interesting problem

Here are some thoughts:
1. The stack element doesn't have to be a number. I would use a private object that tracks the value being pushed/popped from the stack and the index (the stack height) of maximum value below or at that particular stack height. This seems to be what the OP is getting at with his last post.
2. Edit: see reason for flip-flop below - The stack structure itself should definitely not be a LinkedList. It should be something that gives efficient performance when accessing by with an index. ArrayList would fit the bill here. I think the requirement to find the maximum value means that I need to be able to get that value at any time.
3. You would track the current maximum value and the stack position of that value with instance variables.
4. When you push a value, you need to evaluate whether it is greater than, equal to, or less than, the current maximum, then set the stack element index accordingly before you push it into the stack structure.
5. When you pop a value, you peek at the new top of stack and update the current max value and stack position. You probably could do away with one or both instance variables if you just peek at the top stack element. I would probably keep the current maximum value just so I don't have to access the appropriate stack element every time I push a new element. I'd update the current max value when I pop an element, if necessary.

This is the most efficient performance-wise strategy I can think of right now but you're more than welcome to point out holes in this logic. Sure, you end up using more memory but that concern has been deprioritized.

The other alternative is to have a separate stack structure for the max values and corresponding index in the actual stack structure. Every time you see a new max value, you push it on the max stack along with the current value stack height. This will save a little bit more memory if the values are random but uses up most memory if the values being pushed are always increasing.


Junilu - [How to Ask Questions] [How to Answer Questions]
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3003
    
    9
Junilu, are you thinking that the structure needs to be able to remove the max element, not just know what it is? Because some of your comments seem more complex than they need to be, unless you're addressing an additional requirement that I don't think was present. Then again, my previous comments were also more convoluted than they needed to be. Anyway, I now believe it's sufficient if the things in the stack are instances of a class with two fields: (a) the value being pushed, and (b) the overall max after that value was pushed. To me, that seems sufficient to handle everything that is asked for. And I don't believe there's any need for random access into the stack, so LinkedList is just fine. But perhaps we're interpreting some requirements differently.
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4446
    
    5

Mike, it's a difference in interpretation of "find". I interpreted "find the max value" as not only knowing what the max value is but also knowing where on the stack it is. I didn't consider any requirement to remove that element either. Considering that it might mean that you only need to know what the maximum value is at a given stack height regardless of where that value is on the stack, then I would agree that a stack element only needs to track the maximum value at its particular height. On the other hand, the explicit mention of emphasizing speed still makes me think that the "value+height" interpretation of "find" was what the instructor had in mind.

I guess only Birel can help us resolve that ambiguity by asking the instructor what exactly "find the maximum" means.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4344
    
    8

Junilu Lacar wrote:On the other hand, the explicit mention of emphasizing speed still makes me think that the "value+height" interpretation of "find" was what the instructor had in mind.

My interpretation of that was simply that it was intended to prevent the straightforward approach of traversing the entire stack every time in the max() method.
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4446
    
    5

Yeah, now that I think about it, you guys are probably right. After all, stack is a LIFO structure so why would there be a need to get directly at anything other than the top element. I concede that there's nothing wrong with using a LinkedList for this
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Find max element in Stack
 
Similar Threads
Fetching Multiple Records Through Functions
HOw can we find Max stack size of thread in java??
help in solving recursive problems??
generating colors
on checking validity of input. problem on my if-else.