Name three strategies for internal data storage when implementing a Stack ADT

This was a question my Data Structures teacher put on our recent test. I immediately thought of a List and an Array but I cannot for the life of me think of a third ADT t开发者_StackOverflow社区hat could be used as internal storage for a Stack. Any help?

List,Array,Tree,Graph

A linked list is a third option.

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;
    }
}

It's also possible (but not generally useful) to implement a stack using two queues.

I think there is only 2 possible way to implement a queue:

• array
• linked list

A third way would probably be a mix of the 2:

• linked list of arrays.