Week 4: Notes

Here are the classes that we wrote in the lecture and lab.

Stack

// A fixed-size stack of integers.
class Stack {
  int[] a;
  protected int count;
  
  public Stack(int maxSize) {
    a = new int[maxSize];
  }
  
  public virtual void push(int i) {
    a[count] = i;
    ++count;
  }
  
  public virtual int pop() {
    --count;
    return a[count];
  }
  
  public bool isEmpty {
    get {
      return (count == 0);
    }
  }
}

AvgStack

// An AvgStack is like a Stack, but has an additional method avg() that
// returns the average of all stack values in O(1) time.
class AvgStack : Stack {
  int sum;
  
  public AvgStack(int maxSize) : base(maxSize) {
  }
  
  public override void push(int i) {
    base.push(i);
    sum += i;
  }
  
  public override int pop() {
    int i = base.pop();
    sum -= i;
    return i;
  }
  
  public double avg() {
    return (double) sum / count;
  }
}

LinkedStack

class Node {
  public int i;
  public Node next;
  
  public Node(int i, Node next) {
    this.i = i; this.next = next;
  }
}

// A stack of integers, implemented using a linked list.
class LinkedStack {
  Node head;
  
  public void push(int i) {
    head = new Node(i, head);
  }
  
  public int pop() {
    int i = head.i;
    head = head.next;
    return i;
  }
  
  public bool isEmpty {
    get {
      return (head == null);
    }
  }
}

UniqueStack

// A UniqueStack is like a LinkedStack, but ignores any attempt to push
// the same value that is at the top of the stack.
class UniqueStack : LinkedStack {
  public override void push(int i) {
    if (isEmpty || i != head.i)
      base.push(i);
  }
}

DynArray

class DynArray {
  int[] a;
  int count;
  
  // Create a new DynArray with the given initial length.
  // All elements will initially be set to val.
  public DynArray(int length, int val) {
    a = new int[Max(length, 10)];   // create array with at least 10 elements initially
    count = length;
    
    for (int i = 0 ; i < length ; ++i)
      a[i] = val;
  }
  
  // Create a new DynArray with the given initial length. All elements will be 0.
  public DynArray(int length) : this(length, 0) { }
  
  // Create a new DynArray that is initially empty.
  public DynArray() : this(0) { }
  
  // Retrieve the value at the given index, which must be less than the current array length.
  public int get(int i) => a[i];
  
  // Set the value at the given index, which must be less than the current array length.
  public void set(int i, int val) { a[i] = val; }
  
  // Get or set the length of the array. When growing the array, all new elements will be 0.
  public int length {
    get => count;
    
    set {
      if (value <= a.Length)  // growing or shrinking within array bounds
        for (int i = count ; i < value ; ++i)
          a[i] = 0;
      else {
        int[] b = new int[Max(value, 2 * a.Length)];  // double the array size at least
        for (int i = 0 ; i < count ; ++i)
          b[i] = a[i];
        a = b;
      }

      count = value;
    }
  }
  
  // Append a new element to the array, growing its length by 1.
  public void add(int i) {
    length = length + 1;
    a[length - 1] = i;
  }
}