CSC300: Abstract Data Types and Data Structures

(Click here for one slide per page)

In several parts.

Only the first video will be covered on exams. The rest is for orientation, so that you can read the code. These topics will be revisited in SE350, CSC347 and CSC373.

00:00 Abstract Data Types and Data Structures
03:40 First example: main method 
07:18 The representation of Strings
08:50 The meaning of arrows
11:31 Constructors and this
15:31 Push
18:34 IsEmpty and pop

00:00 Static fields
03:23 Static methods

00:00 Generic class parameters
02:26 Generics and array creation
04:47 Generic type enforcement
05:34 Iterators
12:29 The Iterable interface and forall loops

An Abstract Data Type (ADT) specifies

• A set of operations (syntax)
• 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(); }

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 apart, with links to connect them

Data storage affects performance of all the operations

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

file:XFixedCapacityStackOfStrings.java [source] [doc-public] [doc-private]

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] [doc-public] [doc-private]

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] [doc-public] [doc-private]

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.

file:XFixedCapacityIterableStack.java [source] [doc-public] [doc-private]

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.

Revised: 2008/03/17 13:01