Java ArrayDeque - offerLast & pollFirst 与 offerFirst & pollLast

Question

我在做一些简单的算法题，并在玩 ArrayDeque。

例如这个：

https://leetcode.com/problems/maximum-depth-of-binary-tree/submissions/

当使用 BFS 时，我注意到 offerLast & pollFirst / offerFirst & pollLast 都给出相同（正确）的答案。

是否有关于何时使用哪个的最佳实践？由于这应该是一个队列，我认为我们应该提供最后一个并使用 pollFirst。但为什么 offerFirst / pollLast 也有效？

 public int maxDepth(TreeNode root) {
        // do BFS
        if (root == null) return 0;
        
        int depth = 0;
        ArrayDeque<TreeNode> queue = new ArrayDeque();
        queue.offerLast(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++){
                TreeNode curr = queue.pollFirst();
                if (curr.left != null) queue.offerLast(curr.left);
                if (curr.right != null) queue.offerLast(curr.right);
            }
            depth++;
        }
        
        return depth;
    }

另外，我知道我们不需要队列是 ArrayDeque 类型。只需一个简单的队列就可以工作，并且队列仅提供 offer/poll 默认为 FIFO 实现 (offerLast, pollFirst)

Answer 1

But why does offerFirst / pollLast also work?

因为队列的“开始”和“结束”真的只是随意决定的。

您可以将第一个元素称为“开始”，将最后一个元素称为“结束”。在这种情况下，offerLast 入队，pollFirst 出队。

由于数组双端队列是线性数据结构，您可以“反过来”说，我将第一个元素称为队列的“末端”，将最后一个元素称为队列的“开始”。如果您这样想，那么您将通过调用 offerFirst 入队并通过 pollLast.

出队

另一种解释方式是表明这只是两个观点：

假设我们站在双端队列的两端。我们都认为离我们最近的元素是双端队列的“首元素”

   the deque;
  a b c d e f g h
^                 ^
|                 |
you               me

您在 a 旁边放置了一个新元素。从您的角度来看，这是 offerFirst。在我看来，你会做 offerLast!

现在假设您删除了 h。从您的角度来看，这是 pollLast。从我的角度来看，这看起来像 pollFirst - 你正在删除你的“最后一个元素”，但它是我的“第一个元素”。

不过注意，官方是规定第一个元素是队列的开头，最后一个元素是队列的结尾——这就是ArrayDeque实现Queue接口的方式——所以如果你从 Queue 调用方法，比如 offer，它会调用 offerLast.

虽然如果您有自己的开始和结束概念它仍然有效，但遵循“开始”和“结束”的官方定义仍然是一个好习惯（实际上只需使用 offer 和 poll！）。如果您使用 pollLast 和 offerFirst，如果您将 deque 传递给另一段期望 Queue.

的代码，您的代码可能无法正常工作