• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Find max element in Stack

 
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Why can't you do this yourself?
 
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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?
 
Ranch Hand
Posts: 5575
Eclipse IDE Windows XP Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
do you think that is possible without traversing the whole list ?
 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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


Yes
 
Birel Chowdhury
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!)
 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Birel Chowdhury
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 5575
Eclipse IDE Windows XP Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Okay, you can think in another direction: create an Object say, IntWrap which holds integer of value, max and min...
 
Birel Chowdhury
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 13089
67
Chrome Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 5575
Eclipse IDE Windows XP Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Give me some thoughts for pop method. Some code or psuedocode please. Thanks
 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 13
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
However I like Birel's latest answer much better.
 
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Mike Simmons
Master Rancher
Posts: 4806
72
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic