Currently the only stack I know anything about is Vector, I normally use this in place of an array but I understand that there is other types of stacks and they all suit different jobs.
The project I am currently working on requires me to be inserting objects in a certain position inside a stack, not always the front of the stack and I am under the impression that a Vector may not be the best class for this job.
Could somebody please give me a brief description of the other types of stacks available to me with the J开发者_StackOverflowava language and their advantages and disadvantages? Are these names homogeneous? E.g. Are they only used in the Java language or are they used as general terms in Computer Science?
Thank you
- A stack is an abstract data type characterized by LIFO behaviour or push/pop operations
- A list is an abstract data type characterized by having its elemets accessible through a numerical index.
- An array is a low-level implementation of a list
java.util.List
is the list type represented as a Java interfacejava.util.Deque
is a Java interface that provides both LIFO and FIFO queue behaviour (and thus stack behaviour as a subset)java.util.Vector
is an obsolete implementation of a list (based on an auto-resizing array) that should not be used anymorejava.util.ArrayList
is its modernized replacementjava.util.Stack
is an obsolete implementation of a stack that consists of adding some stack-like methods to a Vector, which is not a good way to do it.java.util.ArrayDeque
is a modern implementation of the Deque interfacejava.util.LinkedList
is a different implementation of a list (that also implements the Deque interface) that has a number of big disadvantages and should only be used in very specific cases (it is better when you need to insert or remove elemnts in the list very often).
Basically, if you want a stack, use the Deque
interface and ArrayDeque
as implementation class (except in the rare case where LinkedList
is better). If you want a list, use ArrayList
You mention that you are inserting things into the middle of your 'Stack.' Then I would recommend using LinkedList
.
If you have already found the position that you need to enter a new element, the time to insert it is O(1)
. For a vector it is O(n)
because you need to copy the backing array.
LinkedList
also supports stack-like operations like adding onto the end, or popping off the end of the stack.
Take a look at the javadocs for the data structure to see what it all offers.
To answer your last question. The LinkedList
is a very common data structure throughout computer science. It is also very commonly used to implement stacks because the push and pop operations are constant time, O(1)
.
I suggest taking a look at this tutorial on the Java Collections Framework, which refers to all of the main datatypes in the java.util
package that you would use for things like this (Lists, Vectors, Maps, Trees, etc).
The API documentation of java.util.Stack
advises you to use one of the implementations of interface java.util.Deque
, for example java.util.ArrayDeque
or java.util.LinkedList
.
A LinkedList
is efficient for inserting elements in the middle and removing an element from the head or tail (but it's inefficient for looking up a random element).
精彩评论