We will be implementing a stack using an ArrayList<E>
. An array is a random access data structure. This means
that each element can be accessed directly and in constant time. An ArrayList
is not necessarily the perfect data
structure, in fact a LinkedList
might be better. However, the mapping of a stack onto an ArrayList
will help you
understand the function of a stack.
A stack is considered a limited access data structure - elements can be added and removed from the stack only at the top.
Used in situations where you want to process the most recent additions to the stack before processing the previous entries.
-
The simplest application is to reverse a word. You push a given word to stack, one letter at a time, and then pop letters from the stack.
-
An "undo" mechanism in text editors; this operation is accomplished by keeping all text changes in a stack.
The following image shows a conceptual image of a stack: