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

Question

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 that could be used as internal storage for a Stack. Any help?

Answer 1

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.

Answer 2

List,Array,Tree,Graph

Answer 3

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.