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?
views:
36answers:
4
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
2010-10-20 20:40:45
Linked List is a List
Woot4Moo
2010-10-20 20:45:57
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
2010-10-20 20:51:48
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
2010-10-20 20:56:03
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
2010-10-25 03:12:59