Beginning Java Data Structures and Algorithms

Stacks

Stacks, typically also implemented using linked lists, work differently than queues. Instead of the FIFO ordering, they have a Last In First Out (LIFO) ordering (see Figure 2.9). They have two main operations called push, which adds an item on top of the stack, and pop, which removes and returns one item from the top of the stack. Like queues, stacks are heavily used in many algorithms, such as depth first search traversal, expression evaluations, and many others:

Figure 2.9: Pushing and popping operations on a stack of papers

To model a stack, it's enough to use a simple linked list. The head of the linked list can be used to reference ...