CSC300: Abstract Data Types and Data Structures

Contents [0/9]

Video [1/9]
Abstract Data Type (ADT) [2/9]
ADTs in Java [3/9]
Data structure [4/9]
Fields and methods [5/9]
Static fields and methods [6/9]
Generic classes [7/9]
Interfaces [8/9]
What is memory? [9/9]

(Click here for one slide per page)


Video [1/9]

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.

Open Playlist

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

Open Playlist

00:00 Static fields
03:23 Static methods

Open Playlist

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

Open Playlist

Open Playlist

Abstract Data Type (ADT) [2/9]

An Abstract Data Type (ADT) specifies

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

ADTs in Java [3/9]

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

01
02
03
04
05
06
07
package algs13;
public class StackOfStrings {
  public StackOfStrings          { /* ... */ }
  public boolean isEmpty ()      { /* ... */ }
  public void push (String item) { /* ... */ }
  public String pop ()           { /* ... */ }
}

We use the ADT as follows:

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

Data structure [4/9]

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:

Data storage affects performance of all the operations

Fields and methods [5/9]

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
package algs13;
import stdlib.*;
public class XFixedCapacityStackOfStrings {
  private String[] a; // holds the items
  private int N;      // number of items in stack
  // 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.showBuiltInObjectsVerbose (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 ());
    }
  }
}
XFixedCapacityStackOfStrings_pop_24

Static fields and methods [6/9]

The keyword static changes the meaning of fields and methods.

file:XFixedCapacityStackOfStrings2.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
package algs13;
import stdlib.*;
public class XFixedCapacityStackOfStrings2 {
  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
  // a[0]..a[N-1] are non null
  // a[N]..a[a.length-1] are null
  public XFixedCapacityStackOfStrings2 (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 ();
    XFixedCapacityStackOfStrings2 stack1 = new XFixedCapacityStackOfStrings2 (7);
    XFixedCapacityStackOfStrings2 stack2 = new XFixedCapacityStackOfStrings2 (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 (XFixedCapacityStackOfStrings2 s) {
    int id = s.stackId();
    int num = XFixedCapacityStackOfStrings2.numStacks();
    StdOut.printf("Stack %d of %d:\n", id, num);
    while (!s.isEmpty()) {
      StdOut.println (s.pop ());
    }
  }
}
Storage Where stored? When allocated?
staticstored with classwhen class loaded
nonstaticstored with objectwhen object allocated (with new)
local variablestored with method invocationwhen method called
Method Has "this"?
staticno
nonstaticyes
XFixedCapacityStackOfStrings2_stackId_7

Generic classes [7/9]

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");
  }
}
XFixedCapacityStack_main_46

Interfaces [8/9]

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 ();
  }
}
Nonstatic Static
fieldstored with objectstored with class
methodhas "this"does not have "this"
classhas "this$0"does not have "this$0"
ReverseArrayIterator_next_33

What is memory? [9/9]

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

memory-layout-numFives

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.

Method calls (Stack) Objects (Heap)
Address Value Description
0xbeef0098??@1.overhead
0xbeef00900xface0000@1.args
0xbeef00880xface0010@1.list

0xbeef0080??@2.overhead
0xbeef00780xface0010@2.a
0xbeef00703@2.i
0xbeef00682@2.result
Address Value Description
0xface00385.0Array.data[3]
0xface00305.0Array.data[2]
0xface002811.0Array.data[1]
0xface00205.0Array.data[0]
0xface00184Array.length
0xface0010??Array.overhead

0xface00080Array.length
0xface0000??Array.overhead

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.


Revised: 2008/03/17 13:01