在java中維護堆棧的算法

Question

如何維護堆棧，以便每當從堆棧彈出時知道堆棧中的最小元素？該算法應該有一個恆定的複雜性

在此先感謝

Answer 1

好吧，這裏就是你需要做的..

你需要保持一定的data structure包含插入關於每個元素的信息，究竟是什麼minimum並在當你插入的元素時second minimum值..

所以，你想擁有的信息是這樣的： -

每個元素推 - 插入後>

• 最小值插入前
• 最小值

將需要此信息時，您pop從堆棧中的元素。所以，你就知道不管你是否是popping最小值或不是。如果是的話，那麼你可以在推送這個元素之前用minimum value替換當前的minimum值。如果沒有，那麼在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， 和minimum_after_insertion爲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同時推動。而比較current_minimum_value比較，當你pop ..

您可以嘗試進行作何感想data structure能你有..

Answer 2

使用其他例如minStack，當按下一個元素val時，檢查是否val < minStack.peek()，如果是，則將val也推到minStack;當從stack彈出時，檢查彈出的值，如pop_val，如果pop_val == minStack.peek()是minStack.pop()。

現在我們有一個minStack在特定的時間點保持所有的local-min-element（直到下一次按minStack時），我們可以通過檢查堆棧的頂端是local-min-element，已經在上面介紹過了。

但是，只有當所有的元素都是唯一的時候，這個方法才能正常工作，否則，這樣做會更困難，提示，使用計數器:)。

Answer 3

聲明：禁止使用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());