Week 3: Notes

Stack class

Here's the Stack class that we wrote in the lecture, and also discussed in the tutorial:

using static System.Console;

// stack with a fixed size limit
class Stack {
    int[] a;
    int count;
    
    public Stack(int limit) {
        a = new int[limit];
        count = 0;
    }
    
    public bool isEmpty() => count == 0;
    
    public bool push(int k) {
        if (count == a.Length)
            return false;   // stack is full

        a[count++] = k;
        return true;
    }
    
    public int pop() {
        return a[--count];
    }
}

class Program {
    static void Main(string[] args) {
        Stack s = new Stack(50);
        for (int i = 1 ; i <= 10 ; ++i)
            s.push(i * i);
        
        while (!s.isEmpty())
            WriteLine(s.pop());
    }
}

Binary tree class

Here's the binary tree class that we wrote in the tutorial:

using static System.Console;

class Node {
    public int val;
    public Node left, right;

    public Node(Node left, int val, Node right) {
        this.left = left;
        this.val = val;
        this.right = right;
    }
}

class BinaryTree {
    Node root;

    public BinaryTree() {
        root = null;
    }

    public bool contains(int i) {
        Node n = root;

        while (n != null) {
            if (i < n.val)
                n = n.left;
            else if (i > n.val)
                n = n.right;
            else
                return true;  // we found it
        }

        return false;
    }
    
    public void insert(int i) {
        // We didn't implement this.  Writing this yourself would be a good exercise.
    }

    // Return the total number of nodes in n and its children (recursively).
    int count(Node n) {
        if (n == null)
            return 0;
        
        return 1 + count(n.left) + count(n.right);
    }

    // Return the total number of nodes in the tree.
    int nodes() => count(root);

    // Store all values in node n and its children, in ascending order.
    void store(int[] a, ref int pos, Node n) {
        if (n == null)
            return;
        
        store(a, ref pos, n.left);
        a[pos++] = n.val;
        store(a, ref pos, n.right);
    }

    public int[] toArray() {
        int[] a = new int[nodes()];
        int pos = 0;
        store(a, ref pos, root);
        return a;
    }
}