Java ArrayDeque 删除和轮询方法错误

Question

目前我正在编写 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;

this is a picture of the sample output

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

Answer 1

问题出在您的 pollLast 方法中。在 peekLast 方法中，您使用 tail 作为双端队列中最后一个元素的索引，但在 pollLast 方法中，您使用 tail - 1 作为该元素的索引。这意味着您要删除(并清空)倒数第二个元素而不是最后一个元素。

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