• Post Reply Bookmark Topic Watch Topic
  • New Topic

efficient Queue vs Stack Implementation  RSS feed

 
Steven Rodeo
Ranch Hand
Posts: 72
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
 
Leandro Coutinho
Ranch Hand
Posts: 423
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
David Newton
Author
Rancher
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
(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.)
 
Hunter McMillen
Ranch Hand
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 .
 
David Newton
Author
Rancher
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Hunter McMillen
Ranch Hand
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You are correct, Hunter McMillen; that did appear to be the theme of the original post.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!