在實現堆棧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的混合：

• 鏈接的數組列表。