代替Stack的究竟该是什么

众所周知,Java当中Stack的实现非常糟糕(至少截至Java 8为止),因为stack和vector的关系应当是composition的关系,而非inheritance的继承关系。在Oracle的官方文档中,也是推荐使用Deque去替代Stack类.

可问题是,所谓deque,就是double-ended queue,显然,尽管它实现了stack应该有的接口,但破坏了FIFO(先进先出)的原则。也就是说,它引入类一些其他操作。这也引起了一些人的不满。该文章指出,我们应当对deque再次进行一次封装——在逻辑上,这完全说得通,因为我们想要一个is a stack的Stack类。

但是在做题的时候我们可能没那么多时间去写一个漂亮的stack类。我的做法是,那就用deque吧,只要我不去使用那些超出stack允许的方法就行了。但问题在于,究竟用:

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

还是用:

Deque<Integer> stack = new LinkedList<>();

事实上ArrayDeque及LinkedList都实现了Deque的方法。有一种说法是说ArrayList:

This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

用作stack的时候ArrayList比Stack快,用作queue的时候比LinkedList快

这种说法很巧妙,因为我现在想知道的是,用作stack的时候,到底哪一种更好。而上述说法正好不包括这个比较。但,让我想一想。鉴于我们如果只是在结尾插入一个元素,在结尾移除一个元素,或许LinkedList更快。但是,空间上,LinkedList在内存上要多一个存储下一个元素的link,也就是那个.next,所以理论上说又比ArrayDeque要多耗费一些memory。

所以,我的结论就是(请不要盲目相信我的结论),it depends. 从做题上来说,我猜不会又太大区别。

Leave a Reply

Your email address will not be published. Required fields are marked *