Java ArrayDeque - offerLast & pollFirst与offerFirst & pollLast

Question

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

例如，这个：

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

在使用BFS时，我注意到offerLast & pollFirst / offerFirst和pollLast都给出了相同(正确)的答案。

在什么时候使用哪种方法有最佳实践吗？因为这应该是一个队列，所以我认为我们应该使用offerLast并使用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。只有一个简单的队列才能工作，而一个队列只提供默认为FIFO实现(offerLast，pollFirst)的提供/轮询。

Answer 1

，但为什么offerFirst / pollLast也能工作？

因为队列的“开始”和“结束”实际上是任意决定的。

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

因为数组deques是线性数据结构，所以您可以“翻转它”，并说，我将第一个元素称为队列的“结束”，而最后一个元素称为队列的“开始”。如果您这样想，那么您将通过调用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的代码，则代码可能无法工作。