优先级队列不维护队列属性

Question

我已经做了一个阻塞队列。插入是根据优先级正确完成的，当我删除队列的头部时，队列的最后一个元素成为队列的头部，过程重复。假设我在队列中插入了123456789。

First deleted : 1;  queue elements :92345678  
Second deleted:  9; queue elements :8234567  

等等。

我需要实现队列属性，该属性未得到维护。

即第一次删除：1个队列元素：23456789
第二次删除：2个队列元素：3456789

package com.block.ui;
import java.util.Iterator;
import android.app.Activity;
import android.os.Bundle;
import android.util.Log;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.EditText;
public class PriorityBlockQueSamplActivity extends Activity {
/** Called when the activity is first created. */
EditText et;
EditText et2;
Button b1;
Button b2;
Controller c ;
@Override
public void onCreate(Bundle savedInstanceState) {
    super.onCreate(savedInstanceState);
    setContentView(R.layout.main);
    et=(EditText)findViewById(R.id.editText1);
    et2=(EditText)findViewById(R.id.editText2);
    b1 =(Button)findViewById(R.id.button1);
    b2 =(Button)findViewById(R.id.button2);
    c= new Controller();

    Message m = new Message();
    m.mPriority=1;
    m.Subject="1";
    c.insert(m);
    Message n = new Message();
    n.mPriority=1;
    n.Subject="2";
    c.insert(n);
    Message p = new Message();
    p.mPriority=1;
    p.Subject="3";
    c.insert(p);
    Message q = new Message();
    q.mPriority=1;
    q.Subject="4";
    c.insert(q);

    b1.setOnClickListener(new OnClickListener() {
        @Override
        public void onClick(View v) {
            Iterator<Message> iter = c.getQueue().iterator();
            while(iter.hasNext()){
                Message m =iter.next();
                Log.i("MESSAGE", "Element "+m.Subject+" priority :"+m.mPriority);
            }
        }
    });
    b2.setOnClickListener(new  OnClickListener() {
        @Override
        public void onClick(View v) {
            Message m=c.getMessage();
            c.delete(m);
        }
    });
}

}

还有一堂课

 `public class Controller {
private int queueSize=300;
Comparator<Message> comparator = new PriorityComaparator();
PriorityBlockingQueue<Message> qu = new PriorityBlockingQueue<Message>(queueSize,comparator);
            public Controller() {
}
public void insert(Message msg) {
    boolean status = qu.add(msg);
    if (status)
        log("Added successfully " + msg.Subject + " priority "
                + msg.mPriority + " size :" + qu.size());
    else
        log("Failed to add " + msg.Subject + " with priority "
                + msg.mPriority);
}
public void delete(Message msg) {
    if (qu.contains(msg)) {
        boolean status = qu.remove(msg);
        if (status)
            log("deleted successfully " + msg.Subject + " priority " + msg.mPriority
                    + " size :" + qu.size());
        else
            log("Failed to delete " + msg.Subject + " with priority "+ msg.mPriority);
    }
}
public Message getMessage() {
    return qu.peek(); 
}
public PriorityBlockingQueue<Message> getQueue(){
    return qu;
}
void log(String msg) {
    Log.i("QUEUE", msg);
}
class PriorityComaparator implements Comparator<Message> {
    @Override
    public int compare(Message m, Message n) {
        int y = ((Message) m).mPriority; // 1 -highest 3-least
        int z = ((Message) n).mPriority;

        if (y < z) {
            return -1;
        }
        if (y > z) {
            return 1;
            }
            return 0;
            }
        }
}`

Answer 1

如果与示例中一样，所有插入的元素都具有相同的优先级，则检索顺序未明确定义。从 PriorityQueue（PriorityBlockingQueue 从中派生出相同的排序规则）：

此队列的头部是相对于指定排序的最小元素。如果多个元素被绑定为最小值，则头部是这些元素之一 - 连接被任意打破。

（着重号后加）

Answer 2

如果您使用的优先级队列是您的个人实现，请尝试使用堆数据结构。

正如维基页面所说：

堆是称为优先级队列的抽象数据类型的最高效实现。

这是该页面的链接。

请记住，在Java中你不需要实现它，如果你需要它在多线程程序中工作，你可以使用标准的PriorityQueue类或PriorityBlockingQueue。