Java and Different Types of Stacks

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 interface
• java.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 anymore
• java.util.ArrayList is its modernized replacement
• java.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 interface
• java.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).