Prep 4: Abstract Data Types

This prep will introduce you to writing code using abstract data types. When you have completed it, you will be able to:

• understand the concept of an abstract data type (ADT)
• name several common ADTs
• write code that uses a stack
• distinguish between an abstract data type and a data structure

Readings to complete

• 3.1 Introduction to Abstract Data Types
  
• 3.2 Stacks and Queues
  

Comprehension questions

Complete the Prep 4 quiz: ADTs quiz on Quercus.

Synthesize (submit on MarkUs)

In this programming exercise, you will complete several functions that operate on either a stack or a queue. The starter code and some sample tests are available here:

• Handout
• Starter Code (zip)
  • adts.py This is a stack and queue implementation. We’ve deliberately used a very confusing implementation because you should only be using the public interface of the Stack and Queue ADTs described in the readings. Do not modify or submit this file.

Don’t forget to write and run additional tests to make sure that your code works in all cases. When you’re done, submit on MarkUs.