java - 队列作为链表实现

Question

这个问题不太可能对任何 future 的访客有帮助；它只与一个较小的地理区域、一个特定的时间点或一个非常狭窄的情况相关，通常不适用于全世界的互联网受众。如需帮助使此问题更广泛适用， visit the help center 。

已关闭 10 年前。

这是我在数据结构中的分配程序，用于实现 QueueAsArray。我希望有人指导我解决这个问题，因为我在 Java 编程方面没有很强的背景。

我希望有人指导我如何在我的主程序中编译和使用此代码。

public class QueueAsLinkedList extends AbstractContainer implements Queue
{
    protected LinkedList list;

    public QueueAsLinkedList ()
    { list = new LinkedList (); }

    public void purge ()
    {
    list.purge ();
    count = 0;
    }

    public Object getHead ()
    {
    if (count == 0)
        throw new ContainerEmptyException ();
    return list.getFirst ();
    }

    public void enqueue (Object object)
    {
    list.append (object);
    ++count;
    }

    public Object dequeue ()
    {
    if (count == 0)
        throw new ContainerEmptyException ();
    Object result = list.getFirst ();
    list.extract (result);
    --count;
    return result;
    }

    public Enumeration getEnumeration()
    {
        return new Enumeration()
        {
            protected LinkedList.Element position = list.getHead();

            public boolean hasMoreElements()
            {
                return position != null;
            }

            public Object nextElement()
            {
                if (position == null)
                    throw new NoSuchElementException();
                Object result = position.getDatum();
                position = position.getNext();
                return result;
            }
        };
    }

    protected int compareTo (Comparable object)
    {
        AbstractContainer arg = (AbstractContainer) object;

        long diff = (long) getCount() - (long) arg.getCount();
        if (diff < 0)
            return -1;
        else if (diff > 0)
            return +1;
        else
            return 0;
    }

    public boolean equals(Object object) {
        LinkedList list_object = (LinkedList)object;
        if(list_object.length != this.length) {
            return false;
        }
        Element ptr = this.head;
        Element list_object_ptr = list_object.head;
        for(int i = 0; i < this.length; i++) {          
            if(list_object_ptr.getDatum () != ptr.getDatum ()) {
                return false;
            }
            ptr = ptr.getNext ();
            list_object_ptr = list_object_ptr.getNext ();
        }
        return true;
    }
}

Answer 1

我对您的建议是阅读现有的 LinkedList 库源代码，您可以轻松找到这些内容。我建议您还阅读 ArrayList 的源代码，因为您将包装一个数组。最后看一下ArrayBlockingQueue，因为这是一个包装数组的队列。最后一个类最接近您想要的，但也是最复杂的，因为它是并发且线程安全的。

当你开始编写一个类时，我建议你从一些非常简单的东西开始，然后对其进行编译。使用 IDE，它会在您键入代码时显示代码是否可以编译并建议更正。

然后我会编写一个非常简单的单元测试来测试您非常简单的代码。您只需使用一种方法即可做到这一点。 (有些人建议先编写测试用例，但我发现这非常困难，除非您之前编写过此类类，在这种情况下，您并不是真正先编写单元测试，而只是第一次编写该代码库)

然后添加第二个或第三个方法并对其进行测试。

当它执行您不理解的操作时，请使用调试器单步执行代码以查看每一行的作用。

<小时/>

我会使用 Netbeans、Eclipse 或 IntelliJ CE 等 IDE。我更喜欢 IntelliJ，但 Netbeans 可能最适合初学者。

• 下载 IDE。
• 开始一个新项目。
• 创建一个类并将代码复制并粘贴到该类中。
• 创建另一个使用该类的类。这是你的课。

顺便说一句，这个类是你写的还是因为它有很多不寻常的编码选择而给你的。

<小时/>

代码注释

• 它是一个队列，它包装了一个实现队列的类，因此委托(delegate)看起来很自然，但它似乎并没有这样做，这表明 LinkedList 和 Queue 不是标准的 LinkedList 和 Queue 令人困惑。
• 它使用未定义的字段 count 来代替 LinkedList.size()。
• 出队访问 LinkedList 两次，一次会更有效(就像标准库那样)
• 当 Iterator 自 Java 1.2 (1998) 起成为标准时，它支持 Enumeration 而不是 Iterator
• 当 equals 为 false 时，compareTo 为 0，这是一个错误。
• 它不支持内置泛型。
• compareTo 仅检查长度，因此具有“A”的队列和具有“Z”的队列compareTo == 0
• equals 使用的 this.head 和 this.length 不是字段。