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 a data structures for records, inventories, etc..

Implementations: