1

我正在研究像优先队列这样的排序队列。我已经用 List 做到了，而且效果很好。现在我想用一个数组来做。但是我在添加一个新元素并将其插入排序数组时遇到了一点逻辑问题。

最终输出应该是这样的：
优先级：5 值：x
优先级：4 值：iso
....（等等）
所以具有最高优先级的元素应该在索引 = 0 上。
我只是不知道（是的，我知道切换它真的很简单，但我就是做不到:/) 怎么做...

我已经尝试了一些事情，但我被困住了......：/可以请任何人帮忙吗？

这是我的代码：

public class Queue {

private QueueElem[] a;

public Queue(int capacity) 
{
    QueueElem[] tempQueue = new QueueElem[capacity];
    a= tempQueue;
}

public void enqueue(int p, String v) 
{
    QueueElem neu = new QueueElem(p,v);
    int i=0;

        while(i<a.length) 
        {
            if (a[i] == null) 
            {
                a[i] = neu;
                break;
            }   
            i++;
        }
}

public void writeQueue()
{
    int i=0;
    while((i< a.length) && (a[i] != null))
    {
        System.out.println("Priority: " + a[i].priority + " Value: " + a[i].value);
        i++;
    }
}

public static void main(String args[])
{
    Queue neu = new Queue(10);
    neu.enqueue(4,"iso");
    neu.enqueue(2,"abc");
    neu.enqueue(5,"x");
    neu.enqueue(1,"abc");
    neu.enqueue(4,"bap");
    neu.enqueue(2,"xvf");
    neu.enqueue(4,"buep");  
}
 }//end class Queue


class QueueElem {
int priority;
String value = new String();

public QueueElem(){ }

public QueueElem(int p, String v)
{
    this.priority = p;
    this.value = v;
}

public int getPrio()
{
    return this.priority;
}

public String getValue()
{
    return this.value;
}   
}
4

2 回答 2

0

我不明白为什么有人会想要使用原始数组......尤其是现在你已经用 List 实现了它。

如果您想了解如何在原始数组中插入元素，请查看 ArrayList 的代码，因为它下面使用原始数组。您必须将所有元素移动到插入点的右侧，您可以在循环中复制，或者使用 System.arraycopy()。但是最讨厌的部分是您可能必须创建一个新数组，因为当您添加一个元素时数组大小会增加一（这取决于您使用的是与数据大小完全相同的数组，还是更大的数组，就像在 ArrayList 中所做的那样）。

于 2013-05-16T20:04:48.680 回答
0

如果您将数组解释为最大堆会更好。这是实现优先队列的典型方式。

如果您要为优先级队列维护一个排序数组，那么您正在寻找的是实现插入排序（有点；您没有一个未排序的数组开始。您有一个空数组只需添加到，同时保持排序顺序）。每次插入一个新元素时，您将遍历数组以找到正确的位置，然后将其插入到该位置，然后将当前位于该位置的元素移到该位置，并将其后的所有内容向下移动一个位置。请注意，这不如使用堆实现它的性能好，因为在最坏的情况下，O(n)每次插入时你都有性能，而使用堆你有O(logn).

于 2013-05-16T19:21:09.120 回答