views:

36

answers:

4

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?

A: 

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.

Mark Byers
Linked List is a List
Woot4Moo
I realize now that the question is tagged with C#. However, from the data structure point of view a Linked List is a List.
Woot4Moo
A: 

List,Array,Tree,Graph

Woot4Moo
A: 

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.
AngeDeLaMort
A: 

Haha yes! I know you must be from Dr. Nordstrom's class because your question is word for word from the test. I am correcting that same test question too.

JRhodesy