I was doing some simple algorithm questions and playing around with ArrayDeque.
For example this one:
https://leetcode.com/problems/maximum-depth-of-binary-tree/submissions/
When using BFS, I noticed that offerLast & pollFirst / offerFirst & pollLast both give the same (correct) answer.
Is there a best practice for when to use which? Since this is supposed to be a queue, I think we should offerLast and use pollFirst. But why does offerFirst / pollLast also work?
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;
}
Also, Im aware that we dont need the queue to be of type ArrayDeque. Just a simple Queue would work and a Queue only provides offer/poll which default to the FIFO implementation (offerLast, pollFirst)
But why does offerFirst / pollLast also work?
Because the "start" and "end" of the queue are really just arbitrary decided.
You can call the first element the "start" and the last element the "end". In that case, offerLast enqueues, and pollFirst dequeues.
Since array deques are linear data structures, you can "flip it around" and say, I'll call the first element the "end" of the queue, and the last element the "start" of the queue. If you think like this, then you would enqueue by calling offerFirst and dequeue by pollLast.
Another way to explain this is to show that these are just two perspectives:
Let's say we are at standing at two ends of the deque. We both think that the element closest to us is the "first element" of the deque.
the deque;
a b c d e f g h
^ ^
| |
you me
You put down a new element right next to a. From your perspective, this is offerFirst. From my perspective, you would be doing offerLast!
Now let's say you removed h. From your perspective, this is pollLast. From my perspective, that would look like pollFirst - you are removing your "last element", but it's my "first element".
However, note that officially, it is decided that the first element is the start of the queue, and the last element is the end - this is how ArrayDeque implements the Queue interface - so if you call methods from Queue, like offer, it will call offerLast.
Although it still works if you have your own notion of start and end, it is still a good habit to follow the official definitions of "start" and "end" (actually just use offer and poll!). If you use pollLast and offerFirst, your code might not work if you pass your deque to another piece of code expecting a Queue.