Skip to content
loading...

re: Finding Max in a Stack VIEW POST

FULL DISCUSSION
 

Some stack implementations or definitions have a peek() methos that reads the last element without popping it.

You could just have a single variable that holds the maximum value where when an element is pushed to the stack, you check if its greater than the existing, if so replace, and when an element is popped, peek the stack to check if the max value is still higher than the last.

This of course is through a modified stack implementation. I also interpreted the problem to be creating a function that takes in a stack (data set already) and returns a max value.

I'd still try to use the idea I mentioned above of a max value variable, but traversing a stack is the interesting part here, I believe.

My flow would be as follows:

  • Create a holding stack
  • Create max value, initialise it with min possible value
  • loop on given stack size is greater that zero then
    • pop value
    • if higher that current max, set to max
    • push to holding stack
  • end loop
  • loop on holding stack size is greater tha zero
    • pop value, set it to origional stack
  • end loop
 

Hi Beautus,

Thank you for reading!

I did implement the peek method in my stack to see the last value in the array.

I'm not sure if I am understanding your implementation right, but I think the way you're thinking about the problem is the way I originally thought of it as well. However say you have this stack [1, 2, 1, 3]. In this case, 3 would be your current stored Max. Now if you pop 3 off and just peek the last element, your code would assume the new max is 1, however it's actually 2.

This is why using another stack is helpful. With my code, the max stack would look like this `[1, 2, 2, 3]'. Now when 3 is popped off the stack, my code will also pop the last value of the max stack. Now we have:


//current stack
[1, 2, 1]
//max stack
[1, 2, 2]

Now all we have to do is peek the last element of the max stack and know that the current max is 2.

Thanks for your input and let me know if I cleared it up a bit.

 

No no, I do understand your solution fully. What I didn't make clear though is that my solution assumes that a stack is already hydrated when it gets the max value, and your solution is perfect for getting the max value without traversing the stack each time max is required. I'm not sure if you get me

Oh I see. I did misunderstand at first, I apologize for that. So your solution is a loop, but with pushing to a holding stack while comparing values? This also assumes that no new values are added to the stack. Am I understanding it correctly?

code of conduct - report abuse