堆栈入栈和出栈操作的时间复杂度是否比linkedList的removeFromLast和add操作的时间复杂度更高？

Question

当我在 LeetCode 上使用堆栈操作（push、pop 和 peek）解决 java 语言问题时，时间复杂度为 2888 毫秒。但是当我将 stack 替换为 linkedList 并将 (push(),pop()) 替换为 (add(),removeFromLast()) 时，时间复杂度降低到 188 毫秒。如何？

堆栈push()和pop()时间复杂度是O(1)，但是使用linkedList操作后它会产生巨大的差异。

Answer 1

时间复杂度不能是“2888 ms”，因为复杂度不是绝对时间的度量。时间复杂度仅告诉您算法的运行时间如何随输入大小变化。现在，不同的实现可以具有相同的复杂性，但以不同的（绝对）速度运行。对于中小输入，甚至 O(1) 也可能比 O(n) 慢得多（但 O(1) 总是花费相同的时间）。

Javajava.util.Stack是一个非常古老的类，不应该再使用了。它构建在其之上Vector，并且对其方法的每次调用都是同步的。这意味着对于每个方法调用，您都需要在调用该方法时执行锁定，并在离开该方法时执行解锁。这会增加相当大的运行时开销。

一个现代的替代方案Stack是ArrayDeque，它甚至是由JavaDocStack本身建议的：

Deque 接口及其实现提供了一组更完整且一致的 LIFO 堆栈操作，应优先使用该接口而不是此类。例如：

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