在java中维护堆栈的算法

如何维护堆栈，以便无论何时从堆栈中弹出，都知道堆栈中的最小元素？该算法应具有恒定的复杂度

提前感谢

好的，下面是您需要做的。

您需要维护一些data structure，其中包含插入的每个元素的相关信息，即插入该元素时的minimum和second minimum值是多少。。

所以，你想要这样的信息：-

对于推送的每个元素->

插入后的最小值
插入前的最小值

当您从堆栈中pop该元素时，将需要此信息。。所以，你会知道，无论你是否是popping的最小值。。如果是，则可以在推送此元素之前将当前minimum值替换为minimum value。。如果不是，则此时minimum值不会发生变化。。

例如：-

假设当前堆栈中有以下元素：-

[3, 5, 7, 9, 2, 4]

然后您推送值8。。那么你有两个值需要维护。。(推送中8之前的最小值，即2，以及8之后的最小值插入，即2)：-
```
min_value_before_push = min(stack)
push 8
min_value_after_push = min(stack)
```
如果您推送值1，则minimum_before_insertion为2，CCD_ 10为1:-
```
min_value_before_push = 2
min_value_after_push = 1
```

现在您的堆栈是：-

[1, 8, 3, 5, 7, 9, 2, 4]

现在，如果pop，您将看到value 1：-

min_value_before_push = 2
min_value_after_push = 1

所以，弹出会改变最小值，所以，你用1的minimum_value_before_push来改变当前的最小值。所以，你的最小值也是2。

您当前的堆栈变为：-

[8, 3, 5, 7, 9, 2, 4]

现在，让我们检查这个算法是否适用于duplicate元素：-

假设您想再次推送value 2。。

min_value_before_push = 2
min_value_after_push = 2

然后你继续pop，你会看到对于value 2，min_value_after_push是2，所以这意味着弹出它会改变最小值。。所以你用min_value_before_push替换这个值，它也是2。这就是我们想要的。。

注意：-此算法的一个好处是，您不需要进行太多比较。。只是推送时与current_minimum_value的比较。。并与CCD_ 21在CCD_。。

你可以试着继续思考你能拥有什么data structure。。

免责声明：禁止使用null值(就像ArrayDeque一样)，并且未经过严格测试

import java.util.ArrayDeque;
public class PessimisticStack<T extends Comparable<? super T>> {
private class Entry {
private Entry(T t, T minNow) {
this.t = t;
this.minNow = minNow;
}
private final T t;
private final T minNow;
}
private final ArrayDeque<Entry> deque;
public PessimisticStack() {
deque = new ArrayDeque<Entry>();
}
public PessimisticStack(int initialCapacity) {
deque = new ArrayDeque<Entry>(initialCapacity);
}
public void push(T t) {
if (t == null) throw new NullPointerException();
Entry entry = null; 
if (deque.isEmpty()) {
entry = new Entry(t, t);
}
else {
T prevMinimum = deque.peek().minNow;
T newMinimum = null;
if (t.compareTo(prevMinimum) < 0) {
newMinimum = t;
}
else {
newMinimum = prevMinimum;
}
entry = new Entry(t, newMinimum);
}
deque.push(entry);
}
public T pop() {
return deque.pop().t;
}
public T getMinimum() {
Entry entry = deque.peek();
return (entry == null ? null : entry.minNow);
}
}

示例用法

PessimisticStack<String> stack = new PessimisticStack<String>();
stack.push("Zebra");
stack.push("Elephant");
stack.push("Bryan");
stack.push("Adam");
stack.push("Calvin");
String calvin = stack.pop();
// "Adam"
System.err.println(stack.getMinimum());
stack.push("Aaron");
// "Aaron"
System.err.println(stack.getMinimum());
String aaron = stack.pop();
// "Adam"
System.err.println(stack.getMinimum());
String adam = stack.pop();
// "Bryan"
System.err.println(stack.getMinimum());

使用另一个堆栈，比如minStack，当推送一个元素val时，检查val < minStack.peek()，如果是，也将val推送到minStack；当从stack弹出时，检查弹出值，比如pop_val，如果是pop_val == minStack.peek()，则执行minStack.pop()。

现在我们有了一个minStack，它可以将所有local-min-element保持在特定的时间点(直到下一次推送minStack时为止)，我们只需检查堆栈的顶部是否是local-min-element就可以很容易地确定何时从minStack弹出，这在上面已经介绍过了。

然而，只有当所有元素彼此唯一时，该方法才能正常工作，否则，它将更难做到，提示，使用计数器：)。

相关内容

最新更新

热门标签：