efficient Queue vs Stack Implementation

Hello,

I've been thinking of implementing a Queue and a Stack data structure using either an Array / LinkedList (single /Double). Any one has any thoughts on which one might be a better choice. A reasoning would be great too.

Thanks a bunch!
_SM

a = ArrayList
l = LinkedList

random access: a
reverse the list: l
inserting and deleting: l

more info: http://java.sun.com/developer/JDCTechTips/2002/tt0910.html

(Don't forget there are already implementations of both a stack (java.util.Stack, I think it's not recommended for general use) and queues (several, off of AbstractQueue), if you care.)

Array - Pro: You can access the whole stack or queue whenever you want.
Con: You can only have a fixed size. The size you originally declare it with.

LinkedList - Pro: you can have unlimited size, at least until your memory runs out.
Con: You have to search through the entire list to find something, because each part of the list (node) only knows where the next node is; it can't see the entire list.

Both have good uses. Which one you choose depends on what you need your program to do.

-Hunter

Nothing wrong with the existing Stack for general use, apart from the design problem that it extends Vector.

The fastest Stack and Queue implementation is probably ArrayDeque .

The Stack class says that a Deque impl should be used in preference to Stack; I just go by that since it's in the javadocs.

I had never noticed that it says to use a Deque instead of java.util.Stack. As I said, ArrayDeque says it is the fastest stack implementation.

If you are implementing them for the first time, I think doing it without the built in methods is a really good idea. Gives you a sense of what is really going on.

-Hunter

You are correct, Hunter McMillen; that did appear to be the theme of the original post.