minHeapを使用して優先度キューを使用して実装されたスタックの期待される動作

Question

ヒープとPQの概念が初めてです。だから私はミニヒープを使ってPQを使ってスタックを実装しようとしていました。私は、次のメソッドを実装しようとしています ：

1. ポップ
2. ポップ
3. のisEmpty
4. トップ
5. 以下のサイズを

はコードです：

import java.util.*; 
import java.lang.System; 
public class StackUsingMinPriorityQueue{ 
    static int a[] = {3,7,2,11,9,4}; 
    int size = 0; 
    PriorityQueue<Integer> pq; 
    static StackUsingMinPriorityQueue obj; 
    public static void main(String args[]){ 

     obj = new StackUsingMinPriorityQueue(a.length); 
     for(int i=0;i<a.length;i++){ 
      obj.push(a[i]); 
     } 


     System.out.println("Value popped: "+obj.pop()); 
     System.out.println("Value at Top: "+obj.top()); 
     System.out.println("PQ size: "+obj.size()); 
     System.out.println("PQ IsEmpty: "+obj.isEmpty()); 

    } 
    public StackUsingMinPriorityQueue(int size){ 
     this.size = size; 
     pq = new PriorityQueue<Integer>(); 
    } 

    /** 
    * 1. PUSH 
    * **/ 
    public void push(int data){ 
     obj.insert(-System.currentTimeMillis(),data); 
    } 

    public void insert(long time, int data) { 
      pq.offer(data); 
    } 


    /** 
    * 2. POP 
    */ 
    public int pop(){ 
     return obj.extractMin(); 
    } 

    public int extractMin() { 
     return pq.poll(); 
    } 

    /** 
    * 3.TOP 
    */ 
    public int top(){ 
     return pq.peek(); 
    } 

    /** 
    * 4. SIZE 
    */ 
    public int size(){ 
     return pq.size(); 
    } 

    /** 
     * 5.IsEmpty 
     */ 
    public boolean isEmpty(){ 
     return pq.isEmpty(); 
    } 
} 

Output: 
Value popped: 2 
Value at Top: 3 
PQ size: 5 
PQ IsEmpty: false 

今、私のクエリはの値がトップ= 3です。これは正しいです ？入力した最後の値、4ではないはずですか？私が理解しているのは、積み重ねを実装する際に、スタックの最上部にある要素を4でなく3とすることです。

私の実装が間違っているか、 ？

Answer 1

pq.poll()とpq.peek()popとtopが最後に挿入された要素を返す必要がありながら、pqにおける最小要素上で動作します。

優先度キューを使用してスタックを実装するには、各値にキー-<insertion time>を追加する必要があります。単純な増加カウンターを「タイマー」として使うことができます。この実装は非常に非効率的であることに注意してください。