二叉树前序遍历迭代代码中为何用LinkedList实现Deque？

Great question! Let's unpack this clearly:

1. Deque is an Interface, Not a Concrete Class #

In Java, you cannot directly instantiate an interface using the new keyword. Interfaces like Deque only define a set of method contracts (what methods should exist) but don't provide any actual implementation code for those methods. If you tried writing Deque<TreeNode> stack = new Deque<TreeNode>();, your compiler would throw an error right away: "Cannot instantiate the type Deque".

2. LinkedList is a Valid Implementation of Deque #

LinkedList is one of the standard classes in Java's Collections Framework that implements the Deque interface. It provides concrete code for all the methods defined by Deque—including the ones you're using here: offerFirst(), pollFirst(), and isEmpty(). Since LinkedList is built on a doubly linked list, it's naturally efficient for the head/tail operations required by a deque (which you're using as a stack here).

3. This is "Programming to an Interface" #

Even though your code doesn't use any LinkedList-specific methods, this is a best practice called programming to an interface. By declaring your variable as the Deque type instead of LinkedList, you decouple your code from the specific implementation.

For example, if later you decide ArrayDeque (another Deque implementation, backed by a resizable array) would be more efficient for your use case, you only need to change one line:

Deque<TreeNode> stack = new ArrayDeque<TreeNode>();

All your existing logic (the while loop, adding elements to the list) will work exactly the same—no other changes needed. This makes your code more flexible and easier to maintain.

To confirm, let's look at your code again: every method you call on stack (offerFirst, pollFirst, isEmpty) is defined in the Deque interface, so any valid Deque implementation will work here.

内容的提问来源于stack exchange，提问作者Patrick