arraylist - ArrayList 和 LinkedList 堆栈实现

Question

我已经基于下面的接口编写了 Stack 的两个实现

public interface Stack<T>{
   public void push(T t);
   public T pop();
   public boolean isEmpty();
}

第一个实现使用 ArrayList 作为元素的容器，而第二个实现使用 LinkedList。是为每个底层容器分别实现还是只有一个独立于容器的堆栈实现更好？

谢谢。

Answer 1

在回答您的问题之前，当您使用接口时，请在您的接口名称前添加“I”，例如：IStack

当你为每个类使用interface的时候，你要注意哪些实现，当然你必须为每个类重写interface的方法。因为，接口没有实现那里的方法，直到接口被某些类继承，更不用说容器的实现有不同的 .

例子：

class YourStackOne<T>: IStack<T>
{
//Container
LinkedLink<T> ContainElement;

public void push(T t){//implementation for YourStackOne..}
public T pop(){//implementation for YourStackOne..}
public boolean isEmpty{//implementation for YourStackOne..}
}

class YourStackTwo: IStack<int>
{
//Container
ArrayList ContainElement;

public void push(int t){//implementation for YourStackTwo..}
public int pop(){//implementation for YourStackTwo..}
public boolean isEmpty{//implementation for YourStackTwo..}
}

顺便说一句，如果您使用 .NET 编写代码，为什么不使用 Stack 类呢？

Answer 2

如果一种实现在不同情况下比另一种更好，那么您应该同时拥有两种实现。

但是，在堆栈的情况下，如果您只有 push()、pop() 和 isEmpty()，则 LinkedList 或 ArrayList 在时间复杂度方面不会优于另一个。因此，您可以只选择一种实现方式。

push()、pop() 和 isEmpty() 的恒定时间复杂度：

使用 ArrayList：总是添加到列表的底部，并从底部删除。

使用 LinkedList：始终添加到列表的前面并从前面删除。