我正在使用priorityQueue 来实现BFS。
我想在插入时和弹出后在优先级相同的情况下保持插入顺序。
我重写了 equals 方法,如下所示,并且插入顺序在插入时按预期保持。
但,
一旦我进行删除或民意调查,
元素的顺序发生变化。
即使在轮询中如何保持插入顺序?
class Cell implements Comparable<Cell>{
int v;
int dis;
public Cell(int v, int dis) {
this.v = v;
this.dis = dis;
}
public int compareTo(Cell c2) {
if((this.dis > c2.dis)) {
return 1;
} else if(this.dis < c2.dis) {
return -1;
}
return 0;
}
public boolean equals(Object o) {
if(!(o instanceof Cell)) {
return false;
}
Cell c = (Cell) o;
if(this.dis == c.dis) {
return true;
}
return false;
}
public String toString() {
return v+" ";
}
}
PriorityQueue<Cell> pq = new PriorityQueue<Cell>();
pq.offer(new Cell(0,0));
vis[0] = true;
while(!pq.isEmpty()) {
Cell c = pq.peek();
int adj;
//let's suppose getAdjVertex method will return 1,2,3
while((adj = getAdjVertex(c.v,list.get(c.v),vis)) != -1) {
vis[adj] = true;
pq.offer(new Cell(adj, c.dis+1));
}
System.out.println("pq1 = " + pq); //Here the order is correct
//pq1 = [0 , 1 , 2 , 3 ]
pq.remove(c);
System.out.println("pq = " + pq); // Here the order is changed
//pq = [3 , 1 , 2 ]
}
在上面的代码片段中,
我预计pq
为 [1 , 2 , 3]。