优先队列(从零开始)和链表

Question

我试图从一些无序的原始数据(String1…Priority10 String2相等…IntPriority2等)，并且在概念化如何排序时遇到了麻烦，编写了优先级队列的好方法。我需要让每个对象排队的方法，在最后的链表上不使用排序算法，或使用任何LinkedList或PriorityQueue本身。

我的enqueue方法，这里没什么难的:

    public class ObjectQueue{
Object front = null;           //points to first element of the queue
Object prev = null;            //points to last element of the queue 
  /**
 * Creates an object of Object and adds to the class queue
 * @param name of object
 * @param rank of priority sort
 */
public void enQueue(String name, int rank)
{
    Object current = new Object(name, rank);  //uses current entry String as name, int as rank
    if(isEmpty())               //if empty, add element to front
    {
        front = current;
    }
    else                        //if elements exist, go to end and create new element
    {
        prev.next = current;
    }
    prev = current;

和优先排序和添加方法我有麻烦:

/**
 * Adds each object and rank on a ascending rank basis
 * @param filename name of data file
 * @throws exc in case of missing file
 */
public void addPriority(String filename) throws IOException
{
    try
    {
    File inFile = new File(filename);           //inst. file import
    Scanner read = new Scanner(inFile);         //inst. scanner object
    String name1 = read.next();              //scanner reads next string, primes at front
    int rank1 = read.nextInt();              //reads next int, assigns to rank
    while (read.hasNext())                      //reads until end of text
    {
        String name2 = read.next();              //next string of next Object to be tested
        int rank2 = read.nextInt();              //rank to test rank1 against
        if (rank1 > rank2)                      //if current is higher priority than test
        {
            enQueue(name1, rank1);              //enqueue the current object
            name1 = name2;                      //move test name down to current
            rank1 = rank2;                      //move test rank down to current
        }
        else
        {
            enQueue(name2, rank2);              //enqueue the current object
        }
    }
    read.close();                               //ends read when empty
    }
    catch(Exception exec)
    {
        System.out.println("Error: file not found.");
    }
}

我需要得到这一个单一的方法来预排序对象而不将它们发送到列表，或者正确地排序它们，一次，而在飞行中，我已经没有主意了。

Answer 1

概念上(忽略实现)优先级队列非常简单。它需要能够添加具有优先级的项，并且需要能够获得具有最高优先级(或者在某些实现中是最低优先级)的项。有时还包括一个附加约束，对于两个具有相同优先级的项，必须首先检索先添加的项。

这就是概念。为了帮助我们，您可能需要提供更多关于您的优先队列应该如何工作的详细信息。对于以下注释，我假设:-优先检索最高优先级-同等优先级应按插入顺序检索

看一下实现，只要允许插入并且保持插入顺序，底层结构可以是任何集合。传统的实现是堆，因为它们有效地使用内存并且非常快，但是链表(单链表或双链表)在功能上很好。

显然，优先级队列暗示了检索的顺序。这可以在插入或检索时实现。同样，这个决定将由使用情况决定，并且您的实现似乎也可以忽略这些因素。

所以我的建议是，为了保持简单，在插入时排序，而不是在检索时排序。在不提供实际代码的情况下(我假设这是你的任务)，这里有一个基本算法，可以实现插入时间优先队列。

class PriorityItem {
    private final Item item;
    private final int priority;
}
Collection<PriorityItem> queue;
void insert(Item item, int priority) {
    PriorityItem element = new PriorityItem(item, priority); 
    if queue is not empty {
        step through queue {
            if current.priority < priority {
                insert element here
                return
            }
        }
    }
    add element to end queue
}

那么检索是微不足道的:它只是队列中的第一个项目。