建stack时，用Stack<>和Linkedlist<>的区别?

请见下面的代码，这道题目需要用到的是stack，用Stack<TreeNode> stack = new Stack<TreeNode>()来建是最标准的，这个没错~
不过请问，如果是用LinkedList<TreeNode> stack = new LinkedList<>();来建的话，对于这道题目会有多大的区别呢？面试中用linkedlist来建栈的话，会很糟糕吗？只是好奇，谢谢！

Inorder Traversal

1. public List<Integer> inorderTraversal(TreeNode root) {
   
2.     List<Integer> list = new ArrayList<Integer>(); // LinkedList<Integer> p = new LinkedList<>();
   
3.     Stack<TreeNode> stack = new Stack<TreeNode>(); // LinkedList<TreeNode> stack = new LinkedList<>()
   
4. TreeNode cur = root;
   
5.     while(cur!=null || !stack.empty()){
   
6.         while(cur!=null){
   
7.             stack.add(cur);
   
8.             cur = cur.left;
   
9.         }
   
10.         cur = stack.pop();
    
11.         list.add(cur.val);
    
12.         cur = cur.right;
    
13.     }
    
14. 
    
15.     return list;
    
16. }

复制代码

其实实际应用中用stack不是特别好、
https://stackoverflow.com/questi ... se-deque-over-stack
LinkedList只是一种实现方式，并不是一个interface，感觉可能还不如stack。最好还是用Deque，这是JAVA的官方doc推荐的用法。

不知道小帅 发表于 2020-9-13 04:35
你说的是对的，确实是尽量远离实现细节。不过ArrayDeque和LinkedList都是实现的方式。

的确 我糊涂了

这里应该说的是
ArrayDeque（几乎专门是） 实现的是Deque 这个接口， linkedlist 本身是更加底层的实现List 接口的，它还实现了很多Deque 用不上的东西，封装的比较底层，不够前者那么抽象

不知道小帅 发表于 2020-9-12 09:55
其实实际应用中用stack不是特别好、
https://stackoverflow.com/questions/12524826/why-should-i-use-deq ...

原来如此，请问下面这两种写法哪种更好呢？
Deque<> deque = new ArrayDeque<> ();
Deque<> deque = new LinkedList<>();

liuzz10 发表于 2020-9-13 02:34
原来如此，请问下面这两种写法哪种更好呢？
Deque deque = new ArrayDeque ();
Deque deque = new Link ...

第一种

有个原则就是你在用一个数据结构的时候，应该忘掉里面的实现细节（你知道但是你在调用接口的时候不用管
显然前者的调用比后者要远离实现细节

肥颓 发表于 2020-9-13 03:27
第一种

有个原则就是你在用一个数据结构的时候，应该忘掉里面的实现细节（你知道但是你在调用接口的时 ...

你说的是对的，确实是尽量远离实现细节。不过ArrayDeque和LinkedList都是实现的方式。

liuzz10 发表于 2020-9-13 02:34
原来如此，请问下面这两种写法哪种更好呢？
Deque deque = new ArrayDeque ();
Deque deque = new Link ...

https://stackoverflow.com/questi ... o-implement-a-stack
ArrayDeque的performance会更好一些。虽然你声明的是一个Deque，但是你需要用到的是单端的stack。
这样子其实可以写成Deque<Integer> stack = new ArrayDeque<>();
我会习惯这样写、

不知道小帅 发表于 2020-9-12 12:37
https://stackoverflow.com/questions/29583171/arraydeque-vs-arraylist-to-implement-a-stack
ArrayDe ...

谢谢你的链接~！原来还可以implement ArrayList。。所以是根据具体需要来选择的吗？感觉还有点复杂
以及，声明类型和implement类型原来不是一一对应的啊><学到了。

肥颓 发表于 2020-9-12 11:27
第一种

有个原则就是你在用一个数据结构的时候，应该忘掉里面的实现细节（你知道但是你在调用接口的时 ...

谢谢大神！是说最好要选择更远离实现细节的吗？可以请你具体解释一下实现细节是什么意思吗？

liuzz10 发表于 2020-09-12 14:32:04
谢谢你的链接~！原来还可以implement ArrayList。。所以是根据具体需要来选择的吗？感觉还有点复杂
以及，声明类型和implement类型原来不是一一对应的啊><学到了。

嗯，interface的话只要一个class implement了这个interface就可以声明这个interface，然后instantiate这个class。interface只能声明，不能实例化。可以去看一下Java util的source code，会对理解有不小帮助。