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.