CSC300 / CSC402: Abstract Data Types and Data Structures

Contents [0/9]

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

(Click here for one slide per page)


Abstract Data Type (ADT) [1/9]

An Abstract Data Type (ADT) specifies

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

ADTs in Java [2/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(); }

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.

Data structure [3/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:

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

Fields and methods [4/9]

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 ());
    }
  }
}
XFixedCapacityStackOfStrings_pop_25

Static fields and methods [5/9]

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 ());
    }
  }
}
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
XFixedCapacityStackOfStringsWithStaticMember_stackId_7

Generic classes [6/9]

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

Interfaces [7/9]

Some language features use special interfaces, such as Iterable.

An Iterator is a design pattern.

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

What is memory? [8/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.

Summary: Data structures in Java [9/9]

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.