CSC300: Abstract Data Types and Data Structures

(Click here for one slide per page)

An Abstract Data Type (ADT) specifies

• A set of operations (syntax) with meaning
• How the operations affect the state of the ADT (semantics)

For example, a stack (think of a stack of plates) includes the operations to :

• create an empty stack s
• add an item
• remove the item that was added, assuming there is one
• tell whether or not the stack is empty

In Java we write this as follows (using Strings instead of plates):

package algs13;
public class StackOfStrings {
  public StackOfStrings          { /* ... */ }
  public boolean isEmpty ()      { /* ... */ }
  public void push (String item) { /* ... */ }
  public String pop ()           { /* ... */ }
}

We use the ADT as follows:

  StackOfStrings stack = new StackOfStrings();
  stack.push("a"); 
  if (! stack.isEmpty()) { String item = stack.pop(); }

Note that I've told you what the operations are, and how they should behave.

I've told you nothing about how the operations are implemented.

When we look at a specific implementation, this is what we call a data structure.

A data structure provides code to implement an ADT.

The most important choice is how to store data.

For stack, we will look at two choices:

• Array stack - items stored contiguously, in an array
• Linked stack - items stored separately, with links to connect them Later in the course...

The way we choose to store the data affects the performance of the operations!

A generic class has a type parameter. Type is not stored at runtime.

file:Stack.java [source]

01 02 03 04 05 06 07 08 09 10 package ds1.student.stack; /// An interface defining the Stack ADT. /// DO NOT CHANGE THIS INTERFACE. public interface Stack<T> extends Iterable<T> { void push(T t); T pop(); boolean isEmpty(); int size(); }

Some language features use special interfaces, such as Iterable.

An Iterator is a design pattern.

• You will learn about design patterns when you take a Software Engineering course (SE350 or SE450).

• For now: an Iterator allows you go through the elements of a data structure without imposing on the data sturcture itself.

• The idea here is that when we go through the elements of a data structure, the index pointing to where we are at in the data structure should not be stored in the structure.

• Java's Iterable is an interface that gives you access to an Iterator.

Abstract data types are implemented as data structures.

Data structures are realized in Java using classes.

We hold the data associated with a data structure using fields (aka member variables or instance variables).

Fields are different from local variables, which are stored in methods.