Chapter 4. Stacks: LIFO Collections

A stack is an abstract data structure that serves as a collection of objects that are inserted and removed based on a last-in first-out (LIFO) principle. Accordingly, the two operations that most clearly define a stack structure are push, which adds objects to the collection, and pop, which removes objects from the collection. Other common operations include peek, clear, count, empty and full, all of which will be examined in the Advanced topics section later in this chapter.

Stacks can be either array-based or linked list-based. And, similar to linked lists, stacks can be either sorted or unsorted. Considering the structure of a linked list, a linked list-based stack will be more efficient for sorting operations than an array-based stack.

A stack data structure is well suited for any application that requires the ability to add and remove objects only from the tail of a list. A good example of this is backtracking along a specified path or series...