java.util.Stack extends Vector, and uses it to maintain the Stack.
Why (of all things) is Vector used?
ArrayList would perform better wouldnt it?
And using LinkedList, or custom Link objects would be a better design, no? Is this a leftover from the days that people had no faith in Java's garbage collection?
Any illumination is helpful.
-Mark
> java.util.Stack extends Vector, and uses it to
> maintain the Stack.
>
> Why (of all things) is Vector used?
> ArrayList would perform better wouldnt it?
> And using LinkedList, or custom Link objects would be
> a better design, no? Is this a leftover from the days
> that people had no faith in Java's garbage
> collection?
Stack uses Vector because it predates the Collections API. There is generally no reason that you would need to implement a Stack using a LinkedList as Stacks usually have (somewhat) fixed sizes. It would probably be better to have the Stack us an ArrayList since the methods aren't synchronized but if this is a problem for you, it is relatively trivial to implement your own Stack using an ArrayList.
> Stack uses Vector because it predates the Collections
> API. There is generally no reason that you would need
> to implement a Stack using a LinkedList as Stacks
> usually have (somewhat) fixed sizes. It would probably
> be better to have the Stack us an ArrayList since the
> methods aren't synchronized but if this is a problem
> for you, it is relatively trivial to implement your
> own Stack using an ArrayList.
Well, I'm working on implementing a Lisp-ish interpreter.
My Symbol objects (which point to values and functions), are held in Stacks which are held in a Hashmap.
That way, during function calls I can transaprently push/pop values into this datastructure, and always have the appropriately scoped value of a symbol at hand.
Due to the nature of recursive functions, these stacks can be highly dynamic in size. During one recursive function call, they could grow by thousands of elements, and shrink by thousands of elements and then never be used again.
I've done some testing. The time-hog in the array based stack is growing the array. Due to the nature of the capacity incrementation function (double the size, when more capacity is needed), the results vary depending on the stack size. However the array based implementation almost always outperforms the stack-based implementation by roughly a factor of 3.
> I've done some testing. The time-hog in the array
> based stack is growing the array. Due to the nature of
> the capacity incrementation function (double the size,
> when more capacity is needed), the results vary
> depending on the stack size. However the array based
> implementation almost always outperforms the
> stack-based implementation by roughly a factor of 3.
If this is your use case, then it makes sense for you to create a LinkedList based stack. Simply extend LinkedList and add the stack methods (push, pop, peek).
I think, there is actualy no reason to implement Stack or Queue, if you have LinkedList, because its methods addFirst/addLast, removeFirst/removeLast and getFirst/getLast let you use it as Stack and Queue right away.
It might be usefull to derive your own class just to make the code more readable (to make it clear, you are using it as stack).
M.