A Stack interface is defined to formalize the stack methods. See Handout H.A.38.1, Stack Interface for the details.
public interface Stack
{
boolean isEmpty();
void push(Object obj);
Object pop();
Object peekTop();
}
The Stack
interface above specifies the push
and pop
methods, the boolean
method isEmpty
, and an additional method peekTop
that returns the value of the top element without removing it from the stack.
The following listing shows the Stack
interface implemented in the ArrayStack
class:
public class ArrayStack implements Stack
{
private java.util.ArrayList array;
public ArrayStack()
{ array = new java.util.ArrayList(); }
public boolean isEmpty() { return array.size() == 0; }
public void push(Object obj) { array.add(obj); }
public Object pop() { return array.remove(array.size() - 1); }
public Object peekTop() { return array.get(array.size() - 1); }
}
The data structure used in the ArrayStack
class is an ArrayList
. This allows for resizing of the stack as needed to make it larger.
Here is a short program illustrating usage of the ArrayStack
class.
// Example program using the ArrayStack class
public static void main(String[] args)
{
ArrayStack stack = new ArrayStack();
for (int k = 1; k <= 5; k++)
stack.push(new Integer(k));
while (!(stack.isEmpty()))
{
System.out.print(stack.pop() + " ");
}
}
Another approach would be to use a linked list that would support true dynamic resizing. As you push data onto the stack another node is added to the appropriate end of the linked list. When data is popped from the stack, the linked list would be reduced in size. The following listing shows the Stack
interface implemented in the ListStack
class as a java.util.LinkedList
:
public class ListStack implements Stack
{
private java.util.LinkedList list;
public ListStack() { list = new java.util.LinkedList(); }
public boolean isEmpty() { return list.isEmpty(); }
public void push(Object obj) { list.addFirst(obj); }
public Object pop() { return list.removeFirst(); }
public Object peekTop() { return list.getFirst(); }
}