在实现堆栈ADT时命名内部数据存储的三种策略

Question

这是我的数据结构老师在我们最近的测试中提出的一个问题。我立即想到了一个List和一个Array，但是我不能想象第三个ADT可以用作Stack的内部存储。任何帮助？

Answer 1

链接列表是第三个选项。

class MyStack<T> 
{ 
    LinkedList<T> linkedList = new LinkedList<T>(); 

    public void Push(T t) 
    { 
     linkedList.AddFirst(t); 
    } 

    public T Pop() 
    { 
     T result = linkedList.First.Value; 
     linkedList.RemoveFirst(); 
     return result; 
    } 
} 

也有可能（但不是非常有用），以implement a stack using two queues。

Answer 2

列表，数组，树，图

Answer 3

我觉得只有2种可能的方式来implement a queue：

• 阵列
• 链表

第三种方法很可能是2的混合：

• 链接的数组列表。