Реализация стека с помощью o (1) - PullRequest
Новая
       6

Реализация стека с помощью o (1)

0 голосов
/ 08 декабря 2018

Я пытаюсь реализовать вид стека, который имеет push (), pop (), getMaxSoFar ().Это должно быть выполнено o (1) раз.Тем не менее, я получил ошибку в push (значение T), и я не знаю, почему.В сообщении об ошибке говорится, что оператор "> =" не определен в типе T. Я просто хотел проверить код, поэтому я поставил тип int вместо того, чтобы он работал.

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(); 
}
}

Ответы [ 2 ]

0 голосов
/ 08 декабря 2018

(слишком долго для комментария)

Существует еще одна проблема.

push всегда вызывает stack, но только maxStackесли значение по крайней мере так же велико, как вершина.Пока все хорошо.

Но pop всегда появляется у обоих.Две проблемы:

  • Даже если вы выталкиваете столько раз, сколько нажимаете, может быть EmptyStackException, если maxStack не имеет достаточно элементов (что произойдет, если вы не выдвигаете значенияв порядке возрастания).
  • Даже если исключений нет, значение getMaxSoFar не будет правильным.Как я понимаю, что вы пытаетесь сделать, maxStack должен удерживать сверху элемент max стека в его текущем состоянии.Но представьте, что вы нажимаете значение меньше вершины, maxStack не обновляется, и если вы вытолкнете (из обоих, то), максимум будет потерян в maxStack.Но это все еще здесь в stack.
0 голосов
/ 08 декабря 2018

Ваш метод push предполагает, что оператор >= поддерживается для всех возможных типов T.Однако этот оператор поддерживается только для числовых типов.

Возможно, вы должны определить свой класс для работы только для целых чисел, а не для любого типа данных.

С другой стороны, возможно, вы могли бы реализовать свой класс для всех Comparables. 

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