The Java Course provides a general introduction to programming in Java. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.

Stacks

The Java Stack Object

Java provides a built-in object type called Stack that implements the Stack ADT. You should make some effort to keep these two things---the ADT and the Java implementation---straight. Before using the Stack class, we have to import it from java.util.

Then the syntax for constructing a new Stack is

Stack stack = new Stack ();

Initially the stack is empty, as we can confirm with the empty method, which returns a boolean:

System.out.println (stack.empty ());

A stack is a generic data structure, which means that we can add any type of item to it. In the Java implementation, though, we can only add object types. For our first example, we'll use Node objects, as defined in the previous chapter. Let's start by creating and printing a short list.

LinkedList list = new LinkedList ();
list.addFirst (3);
list.addFirst (2);
list.addFirst (1);
list.print ();

The output is (1, 2, 3). To put a Node object onto the stack, use the push method:

stack.push (list.head);

The following loop traverses the list and pushes all the nodes onto the stack:

for (Node node = list.head; node != null; node = node.next) {
stack.push (node);
}

We can remove an element from the stack with the pop method.

Object obj = stack.pop ();

The return type from pop is Object! That's because the stack implementation doesn't really know the type of the objects it contains. When we pushed the Node objects, they were automatically converted to Objects. When we get them back from the stack, we have to cast them back to Nodes.

Node node = (Node) obj;
System.out.println (node);

Unfortunately, the burden falls on the programmer to keep track of the objects in the stack and cast them back to the right type when they are removed. If you try to cast an object to the wrong type, you get a ClassCastException.

The following loop is a common idiom for popping all the elements from a stack, stopping when it is empty:

while (!stack.empty ()) {
Node node = (Node) stack.pop ();
System.out.print (node + " ");
}

The output is 3 2 1. In other words, we just used a stack to print the elements of a list backwards! Granted, it's not the standard format for printing a list, but using a stack it was remarkably easy to do.

You should compare this code to the implementations of printBackward in the previous chapter. There is a natural parallel between the recursive version of printBackward and the stack algorithm here. The difference is that printBackward uses the run-time stack to keep track of the nodes while it traverses the list, and then prints them on the way back from the recursion. The stack algorithm does the same thing, just using a Stack object instead of the run-time stack.

Home

Stacks

The Java Stack Object

Last Update: 2011-01-24