Overview

We’ll start our exploration of ADTs with one of the simplest: the stack. The ability to simply place an item on a stack and remove items last-in, first-out can be used to elegantly solve many problems. Today, we’ll focus on how we can use the humble stack ADT.

Basic Learning Objectives

Before class, you should be able to:

  • Explain the difference between an ADT and a data structure
  • Explain what a stack is and how items are added and removed
  • Define LIFO
  • Explain the balanced parentheses problem

Advanced Learning Objectives

After class, you should be able to:

  • Implement your own version of a stack
  • Use a stack to solve a problem

Readings

Read the following in the online textbook Runestone:

Checks

Submit answers to the follows on Moodle:

 | “Teddy” |
 |  “Sam”  |
 | “Janine”|
 -----------
  1. Given the stack above,
    1. What will calling peek() on this stack return?
    2. What will the stack look like after calling peek()?
  2. Given the status of the stack after Step 1,
    1. What will calling pop() on this stack return?
    2. What will the stack look like after calling pop()?
  3. Given the status of the stack after Step 2,
    1. What will calling push(“Allison”) on this stack return?
    2. What will the stack look like after calling push(“Allison”)?