Introduction to Stacks

A stack is an abstract data type that stores and gives us the ability to manipulate a collection of objects.

As with most collection types, it provides us a means to:

insert an object (in the context of stacks this is called "pushing" an object onto the stack),
remove an object,(in the context of stacks this is called "popping" an object off of the stack)
test the collection to determine if it is empty.

We will also find it advantageous to provide a way to iterate over all of the objects currently stored (e.g., through a "for-each" loop).

With stacks, insertions and removals are done in a very particular way known as "LIFO" -- that is "last in, first out". A simple real-world example of a stack would be a can of tennis balls. If you put balls numbered 1, 2, and 3 in that order into a tennis ball can. they can only be removed in the order 3, 2, 1.

As another example, suppose you are working on some task A and get interrupted to work on some task B. Then, you are interrupted a second time to work on some higher priority task C. Upon finishing task C, you return to task B, and then finally to task A.

Indeed, this last example is not too dissimilar from how java deals with method calls in a program. Suppose you have a method A, which invokes method B, which in turn invokes method C. Memory for local variables in method A is allocated first, followed by memory for method B when it gets invoked, and then finally memory for method C is allocated when it is invoked. When method C is complete, the memory allocated to C is freed, and program control returns to method B. Then when method B finishes, its memory is freed, and program control returns to method A. Finally, when method A finishes, the memory it used is finally cleared.

Stacks are more often used as a tool for data manipulation and problem solving, than they are for storage. As examples, one often uses stacks to do things like:

handling program calls and returns
reversing arrays
evaluating expressions
determining a correct sequence of decisions

while ArrayLists and other data structures are more typically used as data structures for records, inventories, etc..

The `Stack` class in the Standard Java Libraries

The java.util package in the standard java libraries provides a Stack class as part of the Java Collection Framework that one can use "right-out-of-the-box", if so desired. This framework is a set of classes and interfaces that implement commonly reusable collection data structures, as can be seen below.

The stack class in this framework includes the requisite methods push(), pop(), and isEmpty(). However, it also provides a plethora of other methods -- some of which allow it to behave in ways that are decidedly not "stack-like".

We will soon build our own Stack class (in a couple of different ways), but it will be instructive to first see how the java.util version of the Stack class could be used to store, and then retrieve a few strings. Notice, that when run, this code ends up printing the elements pushed onto the stack in reverse order from the order in which they were pushed.

import java.util.Stack;

public class StackFun {

	public static void main(String[] args) {
		
		Stack<String> stack = new Stack<String>();
		
		stack.push("A");
		stack.push("B");
		stack.push("C");
		
		while (! stack.isEmpty()) {
			System.out.println(stack.pop());
		}
	}
}

When executed, this code prints the following:

C
B
A

Introduction to Stacks

The Stack class in the Standard Java Libraries

The `Stack` class in the Standard Java Libraries