java 删除优先队列的尾部元素
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15117246/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Removing tail element of priority queue
提问by P R
How can I remove the tail element of a priority queue? I am trying to implement beam search using a priority queue and once the priority queue is full, I want to remove the last element(the element with the least priority).
如何删除优先级队列的尾部元素？我正在尝试使用优先级队列实现波束搜索，一旦优先级队列已满，我想删除最后一个元素（优先级最低的元素）。
Thanks!
谢谢！
采纳答案by user93353
No easy way. Copy elements from original to new except the last.
没有简单的方法。将元素从原始元素复制到新元素，最后一个除外。
PriorityQueue removelast(PriorityQueue pq)
{
PriorityQueue pqnew;
while(pq.size() > 1)
{
pqnew.add(pq.poll());
}
pq.clear();
return pqnew;
}
called as
称为
pq = removelast(pq);
回答by matts
You could probably use Guava's MinMaxPriorityQueueto do this. It provides peek, poll, and remove methods for both ends of the queue.
您可能可以使用 Guava 的MinMaxPriorityQueue来执行此操作。它为队列的两端提供了 peek、poll 和 remove 方法。
Another option is to write a Queue wrapper that enforces bounding, similar to this answer. You'd need to implement offer, add, and addAllto check capacity. Something like:
另一种选择是编写一个强制边界的 Queue 包装器，类似于这个答案。你需要执行offer，add和addAll检查能力。就像是：
public class BoundedQueue<E> implements Serializable, Iterable<E>, Collection<E>, Queue<E> {
private final Queue<E> queue;
private int capacity;
public BoundedQueue(Queue<E> queue, int capacity) {
this.queue = queue;
this.capacity = capacity;
}
@Override
public boolean offer(E o) {
if (queue.size() >= capacity)
return false;
return queue.add(o);
}
@Override
public boolean add(E o) throws IllegalStateException {
if (queue.size() >= capacity)
throw new IllegalStateException("Queue full"); // same behavior as java.util.ArrayBlockingQueue
return queue.add(o);
}
@Override
public boolean addAll(Collection<? extends E> c) {
boolean changed = false;
for (E o: c)
changed |= add(o);
return changed;
}
// All other methods simply delegate to 'queue'
}
回答by user207421
Use an inverting Comparator and remove from the head. If you need both the head and the tail you are using the wrong data structure.
使用反相比较器并从头部移除。如果您同时需要头部和尾部，那么您使用的是错误的数据结构。
回答by max
I think, PR's use case is, that he needs the head, but also want to have a small PQ, so the idea is to remove the tail.
我认为，PR的用例是，他需要头部，但也想要一个小的PQ，所以想法是去掉尾部。
As a PQ is realized as a binary tree mapped to an array, the head is always the first element of the backing array (queue[0]), but the tail is not always at the end of the array, you had to search it.
由于 PQ 被实现为映射到数组的二叉树，因此头部始终是支持数组 ( queue[0])的第一个元素，但尾部并不总是在数组的末尾，您必须搜索它。
I think a nice way is to subclass PQ and write the following two methods:
我认为一个很好的方法是将 PQ 子类化并编写以下两个方法：
public class MyPriorityQueue<E> extends PriorityQueue<E>
{
// constructors
public E getTail()
{
// queue.length can be bigger than this.size() !!
Object[] queue = this.toArray();
E tail = (E)queue[0];
Comparator<? super E> comparator = this.comparator();
if (comparator !=null)
for(int i = 1; i < this.size(); i++)
if ( comparator.compare(tail, (E)queue[i]) < 0)
tail = (E)queue[i];
else
for(int j = 1; j < this.size(); j++)
if ( ((Comparable)tail).compareTo( ((Comparable)queue[j]) ) < 0 )
tail = (E)queue[j];
return tail;
}
public E removeTail()
{
E tail = this.getTail();
this.remove(tail);
return tail;
}
}
回答by Vanji
While you add the data into priority queue itself do the comparison;
当您将数据添加到优先级队列本身时进行比较；
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
回答by T-G
There is a better solution in case you have a reason not to generate another element to the memory.
如果您有理由不在内存中生成另一个元素，则有更好的解决方案。
you can get the size of the Queue and run over it with an iterator while counting the elements you are going over, once you get to the last one OR the one you are looking for, you can use PriorityQueue.remove(Object o)
您可以获取 Queue 的大小并使用迭代器运行它，同时计算您要遍历的元素，一旦到达最后一个或您要查找的元素，您可以使用 PriorityQueue.remove(Object o)
Iterator<E> it = Queue.iterator();
while (it.hasNext()) {
temp<E> = it.next();
counter++;
if (counter == Queue.size()) {
Queue.remove(temp);
}
}
回答by Ehsan
If you are concerned with the runtime, I suggest implementing your own queue. I did the following and worked in my project.
如果您关心运行时，我建议您实现自己的队列。我做了以下工作并在我的项目中工作。
1) copy paste the code from PriorityQueue -> CustomQueue.java 2) Add a method removeLast() 3) This is the implementation I used (very minimal)
1) 从 PriorityQueue -> CustomQueue.java 复制粘贴代码 2) 添加一个方法 removeLast() 3) 这是我使用的实现（非常少）
public void removeLast() {
if(size == 0) {
return;
}
queue[size - 1] = null;
size--;
}
}
The reason this works is that the implementation of PriorityQueue uses an array to hold object. So "size" is infact a pointer to the next available spot in the array. By reducing it, the size of the array/queue is reduced, as if you are dropping the last element.
这样做的原因是 PriorityQueue 的实现使用一个数组来保存对象。所以“大小”实际上是指向数组中下一个可用位置的指针。通过减少它，数组/队列的大小会减少，就好像您要删除最后一个元素一样。
