删除优先级队列的尾部元素

如何删除优先级队列的尾部元素？我试图使用优先级队列来实现波束搜索，一旦优先级队列已满，我想删除最后一个元素（具有最低优先级的元素）。删除优先级队列的尾部元素

谢谢！

2013-02-27 P R

您可以创建一个新的'PriorityQueue'实例并将所有元素从初始队列移动到除尾部之外的所有元素。 – 2013-02-27 16:34:26

http：// stackoverflow。com/questions/7878026/is-there-a-priorityqueue-implementation-with-fixed-capacity-and-custom-comparato – NPE 2013-02-27 16:37:36

没有简单的方法。除最后一个外，将元素从原始复制到新元素。

PriorityQueue removelast(PriorityQueue pq) 
{ 

    PriorityQueue pqnew; 

    while(pq.size() > 1) 
    { 
     pqnew.add(pq.poll()); 
    } 

    pq.clear(); 
    return pqnew; 
}

称为

pq = removelast(pq);

来源

2013-02-27 16:44:55 user93353

你也许可以利用番石榴的MinMaxPriorityQueue做到这一点。它为队列的两端提供peek，poll和remove方法。

另一种选择是编写一个强制边界的队列封装，类似于this answer。您需要执行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' 
}

来源

2013-02-27 17:13:59 matts

使用反转比较器并从头上移除。如果你需要使用错误的数据结构的头部和尾部。

来源

2013-02-27 22:17:35 EJP

-2

如果你关心运行时，我建议实现你自己的队列。我做了以下工作，并在我的项目中工作。

1）复制粘贴的PriorityQueue代码 - > CustomQueue.java 2）添加的方法removeLast（） 3）这是我所使用的实现（非常小）

public void removeLast() { 
    if(size == 0) { 
     return; 
    } 
    queue[size - 1] = null; 
    size--;

}

这个工作的原因是PriorityQueue的实现使用一个数组来保存对象。所以“大小”实际上是指向数组中下一个可用点的指针。通过减少它，数组/队列的大小会减少，就像删除最后一个元素一样。

来源

2014-03-12 22:06:43 Ehsan

我觉得，PR的用例是，他需要头部，但也想要一个小PQ，所以想法是去掉尾巴。由于PQ是作为映射到数组的二叉树实现的，因此头始终是后备数组的第一个元素（queue[0]），但尾部并不总是在数组的末尾，必须搜索它。

我觉得一个很好的方式是继承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; 
    } 
    }

来源

2015-02-02 15:16:23 max

你的else块的缩进关闭 – manonthemat 2016-09-20 17:16:54

没有的情况下，更好的解决方案，你有充分的理由不产生另一元素的内存。

你可以获得队列的大小并用迭代器运行它，同时计算你要去的元素，一旦你到达最后一个或你正在寻找的元素，你可以使用PriorityQueue.remove（对象o）

Iterator<E> it = Queue.iterator(); 
while (it.hasNext()) { 
    temp<E> = it.next(); 
    counter++; 
    if (counter == Queue.size()) { 
     Queue.remove(temp); 
    } 
}

来源

2017-11-06 07:36:49

删除优先级队列的尾部元素

回答

相关问题