Stack Implementation with o(1)

Question

I am trying to implement kind of Stack, which has push(), pop(), getMaxSoFar(). It should be executed o(1) time. However, I got an error in push(T value), and I don't know why. The error message said the operator ">=" is not defined in the type of T. I just wanted to check the code so I put int type instead of then it worked.

class FastMaxStack<T>
{    
private Stack<T> stack;
private Stack<T> maxStack;

public FastMaxStack()
{
    stack = new Stack();
    maxStack = new Stack();
}

public void push(T value)
{
    if(maxStack.isEmpty())
    {
        maxStack.push(value);
    }
    else if(value >= maxStack.peek()) 
    {
        maxStack.push(value);
    }

    stack.push(value);
}

public T pop()
{
    maxStack.pop();
    return  stack.pop(); 
}

public T getMaxSoFar()
{
    return maxStack.peek(); 
}
}

Look into Comparable. You want your T to be `T extends Comparable`, which basically means "a type T that's comparable to itself." — yshavit, Dec 08 '18 at 00:34
If you want to compare any `T` value, you need `T` to implement `Comparable`, so you can call `compareTo()`, instead of trying to use the numeric only `>=` operator on objects. — Andreas, Dec 08 '18 at 00:34
As an aside I’m not sure it will work. What happens if I push 5 and 3 and then pop both again? — Ole V.V., Dec 08 '18 at 01:27

score 0 · Accepted Answer · answered Dec 08 '18 at 00:33

0

Your push method is assuming that the >= operator is supported for every conceivable type T. However, that operator is only supported for numeric types.

Perhaps you should define your class to operate for integers only, and not any data type.

On the other hand, perhaps you could implement your class for all Comparables.

class FastMaxStack<Comparable<T>>
{
   //etc...  
}

answered Dec 08 '18 at 00:33

Jonathan Wilson

4,138
1
24
36

You are right. I amended my code only for the case dealing with int type. Thank you so much! I did not realize that my push() method above is not valid. I fixed it! – Sangmin Choi Dec 08 '18 at 20:36
public void push(int value) { int max = 0; if(maxStack.isEmpty()) { max = value; } else { max = (int) maxStack.peek(); } if(max > value) { maxStack.push(max); } else { maxStack.push(value); } stack.push(value); } – Sangmin Choi Dec 08 '18 at 20:37

score 0 · Answer 2 · 2018-12-08T10:19:01.457

0

(too long for a comment)

There is another problem.

push always pushes on stack, but only pushes on maxStack if the value is at least as large as the top. So far, so good.

But pop always pops from both. Two problems:

Even if you pop as many times as you push, there can be an EmptyStackException if maxStack does not have enough elements (which will happen if you don't push values in increasing order).
Even if there is no exception, the value of getMaxSoFar won't be correct. As I understand what you are trying to do, maxStack is supposed to hold in top the max element of the stack in its current state. But imagine you push a value smaller than top, maxStack is not updated, and if you pop (from both then), the max is lost in maxStack. But it's still here in stack.

edited Dec 08 '18 at 10:19

answered Dec 08 '18 at 00:55

1

I think you could be raising some valid points here but it doesn't address the question. – ChiefTwoPencils Dec 08 '18 at 01:39
@ChiefTwoPencils I know. I'm aware that this might downvoted, but I think it's worth letting the OP know the syntax is not the only problem in this program. – Dec 08 '18 at 01:45
The points are certainly valid. I tried to add the same in a comment, but of course it is not as clear as this — I hesitate to call it answer, sorry. – Ole V.V. Dec 08 '18 at 06:06
@OleV.V. Indeed, I intended to write a comment but it's too long. – Dec 08 '18 at 10:19
Thanks for the comments guys! All the help from you guys is truly helpful. I fixed the push() method and it seems that it works! – Sangmin Choi Dec 08 '18 at 20:35
@Jean-ClaudeArbaut public void push(int value) { int max = 0; if(maxStack.isEmpty()) { max = value; } else { max = (int) maxStack.peek(); } if(max > value) { maxStack.push(max); } else { maxStack.push(value); } stack.push(value); } – Sangmin Choi Dec 08 '18 at 20:39
1

@OleV.V. With this both stacks have the same number of elements (the max is duplicated if necessary). So the two bugs mentioned above are solved. The price to pay is there are twice as many elements as in a standard stack. – Dec 09 '18 at 10:16
I see it now. It’s just because code pasted into a comment is unreadable, sorry. – Ole V.V. Dec 09 '18 at 10:18

Stack Implementation with o(1)

2 Answers2