Xóa phần tử đuôi của hàng đợi ưu tiên

Question

Làm cách nào để xóa phần tử đuôi của hàng đợi ưu tiên? Tôi đang cố gắng thực hiện tìm kiếm chùm bằng hàng đợi ưu tiên và khi hàng đợi ưu tiên đầy, tôi muốn xóa phần tử cuối cùng (phần tử có mức độ ưu tiên thấp nhất).

Cảm ơn!

Answer 1

Không có cách nào dễ dàng. Sao chép các phần tử từ gốc sang mới ngoại trừ phần tử cuối cùng.

PriorityQueue removelast(PriorityQueue pq) 
{ 

    PriorityQueue pqnew; 

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

    pq.clear(); 
    return pqnew; 
} 

gọi là

pq = removelast(pq); 

Answer 2

Bạn có thể có thể sử dụng ổi của MinMaxPriorityQueue để làm điều này. Nó cung cấp xem trước, bỏ phiếu và loại bỏ các phương thức cho cả hai đầu của hàng đợi.

Tùy chọn khác là viết trình bao bọc hàng đợi thực thi giới hạn, tương tự như this answer. Bạn cần triển khai offer, add và addAll để kiểm tra dung lượng. Một cái gì đó như:

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' 
} 

Answer 3

Sử dụng bộ so sánh đảo ngược và loại bỏ khỏi đầu. Nếu bạn cần cả đầu và đuôi bạn đang sử dụng cấu trúc dữ liệu sai.

Answer 4

Nếu bạn quan tâm đến thời gian chạy, tôi khuyên bạn nên triển khai hàng đợi của riêng mình. Tôi đã làm như sau và làm việc trong dự án của tôi.

1) sao chép dán mã từ PriorityQueue -> CustomQueue.java 2) Thêm một removeLast() phương pháp 3) Đây là việc thực hiện tôi đã sử dụng (rất ít)

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

}

Lý do này hoạt động là việc thực hiện PriorityQueue sử dụng một mảng để giữ đối tượng. Vì vậy, "kích thước" là infact một con trỏ đến vị trí có sẵn tiếp theo trong mảng. Bằng cách giảm nó, kích thước của mảng/hàng đợi bị giảm, như thể bạn đang thả phần tử cuối cùng.

Answer 5

Tôi nghĩ, trường hợp sử dụng của PR là, rằng anh ta cần đầu, nhưng cũng muốn có một PQ nhỏ, vì vậy ý ​​tưởng là để loại bỏ đuôi.

Khi PQ được thực hiện dưới dạng cây nhị phân được ánh xạ tới một mảng, đầu luôn là phần tử đầu tiên của mảng sao lưu (queue[0]), nhưng đuôi không phải lúc nào cũng ở cuối mảng, bạn phải tìm kiếm nó.

Tôi nghĩ một cách tốt đẹp là để phân lớp PQ và viết hai phương pháp sau đây:

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; 
    } 
    } 

Answer 6

Có một giải pháp tốt hơn trong trường hợp bạn có một lý do để không tạo ra một yếu tố vào bộ nhớ.

bạn có thể nhận kích thước của Hàng đợi và chạy qua nó với một trình lặp trong khi đếm các phần tử bạn đang đi qua, khi bạn đến phần tử cuối cùng HOẶC cái bạn đang tìm kiếm, bạn có thể sử dụng PriorityQueue.remove (Đối tượng o)

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