0

目前我正在编写 ArrayDeque 的实现。我正在研究 pollFirst、pollLast、removeFirst 和 removeLast 方法。我不完全确定我写的方法是否正确。我编写了一个驱动程序来测试这些方法，但我不确定输出是否正确。

驱动程序可以在这里找到：https ://pastebin.com/bH0D78jG

以下是以下方法：

民意调查：

T result = (T) deque[head]; // Element is null if deque empty
    if (result == null)
        return null;
    deque[head] = null;     // Must null out slot
    head = (head + 1) & (deque.length - 1);
    return result;

投票最后：

    int t = (tail - 1) & (deque.length - 1);
    T result = (T) deque[t];
    if (result == null)
        return null;
    deque[t] = null;
    tail = t;
    return result;

删除优先

    T x = pollFirst();
    if (x == null)
        throw new NoSuchElementException();
    return x;

删除最后一个

    T x = pollLast();
    if (x == null)
        throw new NoSuchElementException();
    return x;

这是示例输出的图片

我最关心的是方法以及它如何在 pollFirst 和 pollLast 之后输出数组。双端队列的每一端不应该有一个空值吗？

4

1 回答 1

0

问题出在你的pollLast方法上。在peekLast方法中，您tail用作双端队列中最后一个元素的索引，但在pollLast方法中，您tail - 1用作此元素的索引。这意味着您正在删除（并清空）倒数第二个元素而不是最后一个元素。

要修复该错误，请将行更改T result = (T) deque[t];为T result = (T) deque[tail];.

于 2019-10-31T15:10:38.807 回答