CSC300 / CSC402: 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

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

Local variables are stored in method invocations. Fields are stored in objects.

Fields are sometimes called member variables or instance variables.

file:XFixedCapacityStackOfStrings.java [source]

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 package algs13; import stdlib.*; public class XFixedCapacityStackOfStrings { private String[] a; // holds the items private int N; // number of items in stack // Invariant (after the constructor): // a[0]..a[N-1] are non null // a[N]..a[a.length-1] are null public XFixedCapacityStackOfStrings (int capacity) { this.a = new String[capacity]; this.N = 0; } public int size () { return N; } public boolean isEmpty () { return (N == 0); } public void push (String item) { if (item == null) throw new IllegalArgumentException (); if (N >= a.length) throw new RuntimeException ("Stack full"); a[N] = item; N++; } public String pop () { if (N <= 0) throw new RuntimeException ("Stack empty"); N--; String result = a[N]; a[N] = null; return result; } public static void main(String[] args) { //Trace.showObjectIdsRedundantly (true); Trace.showBuiltInObjects(true); //Trace.drawStepsOfMethod ("main"); Trace.drawSteps (); Trace.run (); XFixedCapacityStackOfStrings stack1 = new XFixedCapacityStackOfStrings (7); XFixedCapacityStackOfStrings stack2 = new XFixedCapacityStackOfStrings (3); stack1.push ("a"); stack2.push ("b"); stack1.push ("c"); stack2.push ("d"); stack1.push ("e"); stack2.push ("f"); stack1.push ("g"); while (!stack2.isEmpty()) { StdOut.println (stack2.pop ()); } StdOut.println(); while (!stack1.isEmpty()) { StdOut.println (stack1.pop ()); } } }

The keyword static changes the meaning of fields and methods.

file:XFixedCapacityStackOfStringsWithStaticMember.java [source]

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 package algs13; import stdlib.*; public class XFixedCapacityStackOfStringsWithStaticMember { private static int numStacks = 0; public static int numStacks() { return numStacks; } private int stackId; private int stackId() { return stackId; } private String[] a; // holds the items private int N; // number of items in stack // Invariant (after the constructor): // a[0]..a[N-1] are non null // a[N]..a[a.length-1] are null public XFixedCapacityStackOfStringsWithStaticMember (int capacity) { this.stackId = numStacks++; this.a = new String[capacity]; this.N = 0; } public int size () { return N; } public boolean isEmpty () { return (N == 0); } public void push (String item) { if (item == null) throw new IllegalArgumentException (); if (N >= a.length) throw new RuntimeException ("Stack full"); a[N] = item; N++; } public String pop () { if (N <= 0) throw new RuntimeException ("Stack empty"); N--; String result = a[N]; a[N] = null; return result; } public static void main(String[] args) { //Trace.showObjectIdsRedundantly (true); Trace.showBuiltInObjects (true); Trace.drawSteps(); //Trace.drawStepsOfMethod ("main"); //Trace.drawStepsOfMethod ("printPop"); Trace.run (); XFixedCapacityStackOfStringsWithStaticMember stack1 = new XFixedCapacityStackOfStringsWithStaticMember (7); XFixedCapacityStackOfStringsWithStaticMember stack2 = new XFixedCapacityStackOfStringsWithStaticMember (3); stack1.push ("a"); stack2.push ("b"); stack1.push ("c"); stack2.push ("d"); stack1.push ("e"); stack2.push ("f"); stack1.push ("g"); printPop(stack2); printPop(stack1); } private static void printPop (XFixedCapacityStackOfStringsWithStaticMember s) { int id = s.stackId(); int num = XFixedCapacityStackOfStringsWithStaticMember.numStacks(); StdOut.printf("Stack %d of %d:\n", id, num); while (!s.isEmpty()) { StdOut.println (s.pop ()); } } }

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

file:XFixedCapacityStack.java [source]

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 package algs13; import stdlib.*; public class XFixedCapacityStack<T> { private T[] a; // holds the items private int N; // number of items in stack @SuppressWarnings("unchecked") public XFixedCapacityStack (int capacity) { this.a = (T[]) new Object[capacity]; // no generic array creation this.N = 0; } public int size () { return N; } public boolean isEmpty () { return (N == 0); } public void push (T item) { if (item == null) throw new IllegalArgumentException (); if (N >= a.length) throw new RuntimeException ("Stack full"); a[N] = item; N++; } public T pop () { if (N <= 0) throw new RuntimeException ("Stack empty"); N--; T result = a[N]; a[N] = null; return result; } public static void main (String[] args) { //Trace.showObjectIdsRedundantly (true); Trace.showBuiltInObjects (true); //Trace.showBuiltInObjectsVerbose (true); Trace.drawStepsOfMethod ("main"); Trace.run (); XFixedCapacityStack<Integer> s1 = new XFixedCapacityStack<> (5); XFixedCapacityStack<String> s2 = new XFixedCapacityStack<> (3); s1.push (11); s1.push (21); s1.push (31); //s2.push (41); s2.push ("duck"); s2.push ("goose"); } }

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.

file:XFixedCapacityIterableStack.java [source]

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 package algs13; import stdlib.*; import java.util.Iterator; public class XFixedCapacityIterableStack<T> implements Iterable<T> { T[] a; // holds the items int N; // number of items in stack @SuppressWarnings("unchecked") public XFixedCapacityIterableStack (int capacity) { this.a = (T[]) new Object[capacity]; // no generic array creation this.N = 0; } public int size () { return N; } public boolean isEmpty () { return (N == 0); } public void push (T item) { if (item == null) throw new IllegalArgumentException (); a[N] = item; N++; } public T pop () { N--; T result = a[N]; a[N] = null; return result; } public Iterator<T> iterator () { return new ReverseArrayIterator (); } public class ReverseArrayIterator implements Iterator<T> { private int i; public ReverseArrayIterator() { int numOccupied = N; this.i = numOccupied - 1; } public boolean hasNext () { return i >= 0; } public T next () { T result = a[i]; i--; return result; } } public static void main (String[] args) { //Trace.showBuiltInObjects (true); //Trace.drawStepsOfMethod ("main"); //Trace.drawStepsOfMethod ("next"); //Trace.drawSteps(); //Trace.run (); XFixedCapacityIterableStack<Integer> s1 = new XFixedCapacityIterableStack<> (5); XFixedCapacityIterableStack<String> s2 = new XFixedCapacityIterableStack<> (3); s1.push (11); s1.push (21); s1.push (31); s2.push ("duck"); s2.push ("goose"); // Here's a nicer version StdOut.print ("What's on the stack: "); for (Integer k : s1) { StdOut.print (k + " "); } StdOut.println (); } }

What does the machine memory look like when you see a picture like this:

To fully answer this question, you need to take the systems classes. But it is useful to have an idea of the memory, even if the details are not exactly correct.

Above, I show two parts of memory. On the left is storage for method calls (commonly called the stack), on the right is storage for objects (commonly called the heap). Arrays are objects in java. Machine addresses are shown as hexadecimal numbers beginning with the prefix 0x.

Each entry includes some overhead.

• For methods, the overhead includes the return address. This tells the machine what code should be executed when the method returns. If you are interested, you can read more.
• For objects, the overhead indicates the runtime type of the object. This is used to implement runtime type queries, such as the getClass() method. If you are interested, you can read more.

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.

Note: Static fields and methods, generic classes, and interfaces are not covered on exams.
Tracing code, as we covered in class last week, MAY be on the exam.
We are talking about these topics to help you read the code.
They will be revisited in SE350/SE450, CSC347/CSC447 and CSC373/CSC406/CSC407.