8 Stacks: Piling up data before processing it

 

In this chapter

  • introducing the stack abstract data type
  • applying the LIFO policy in the real world and in computer science
  • implementing a stack with arrays and linked lists
  • why do we need stacks

In the previous chapter, you familiarized yourself with containers, a class of data structures whose main purpose is to hold a collection of objects, and with the simplest of all containers—the bag. Bags are simple data structures that require few resources. They can be useful when we want to hold data on which we only need to compute some statistics, but overall, they aren’t widely used.

Now it’s time to look at containers that are crucial to computer science: we start with the stack. You’ll find stacks everywhere in computer science, from the low-level software that makes your applications run to the latest graphics software available.

In this chapter, we learn what a stack is, see how stacks work, and look at some of the kinds of applications that use stacks.

Stack as an ADT

As I mentioned for bags, I start our discussion of each container at the abstract data type (ADT) level. So, this is when we define what a stack is, how a stack works at a high level, and the interface a stack provides for us to interact with it.

Stack and LIFO

A stack is a container that allows elements to be added or removed according to precise rules: you can’t just add a new element anywhere like with arrays and lists.

Operations on a stack

Stacks in action

Stack as a data structure

Static array for storing a stack’s data

Dynamic array

Linked lists and stacks

Linked list implementation

Push

Pop

Peek

Theory vs. the real world

More applications of a stack

The call stack

Evaluating expressions

Undo/redo

Retracing your steps

Recap