Show Menu
Cheatography

Push

public void push(T newEntry) {
        // Add to beginning of chain:
        try {
            LinkedStack.Node newNode = new LinkedStack.Node(newEntry);

            newNode.next = firstNode; // Make new node reference rest of chain

            // (firstNode is null if chain is empty)
            firstNode = newNode; // New node is at beginning of chain
            numberOfEntries++;
        } catch (OutOfMemoryError e) {
            throw new IllegalStateException();
        }
        //return true;
    }

Pop

@Override
    public T pop() {
        T result = null;

        if (firstNode != null) {
            result = firstNode.data;
            firstNode = firstNode.next; // Remove first node from chain
            numberOfEntries--;
        } else {
            throw new NoSuchElementException();
        }
        return result;
    }

Top

public T top() {
        if (firstNode != null) {
            return firstNode.data;
        }
        throw new NoSuchElementException("Stack is Empty");
    }
 

Induction Proofs

Recursive Fern

public void drawFern(double x, double y, double angle, double size) {
if (size > 1.0) { // STOP if size <= 1.0!
double[] end;
double length = size * 0.5;
end = drawStem(x, y, angle, length); // private method
double smaller = size * 0.5; // SMALLER!
drawFern(end[0], end[1], angle+60, smaller);
drawFern(end[0], end[1], angle, smaller);
drawFern(end[0], end[1], angle-60, smaller);
}
}

Recursive Binary

public static <T> int binaryFind(Comparable<T> item, T[] v, int lo, int hi) {
        if (lo > hi) { return -1; }
        int mid = lo + (hi - lo) / 2;
        if (item.compareTo(v[mid]) < 0) {
            return binaryFind(item, v, lo, mid - 1);
        } else if (item.compareTo(v[mid]) > 0) {
            return binaryFind(item, v, mid+1, hi);
        } else { return mid; } // found it!
    }
 

Selection Sort

public static <T extends Comparable<? super T>>
            void selectionSort(T[] a) {
        for (int i = 0; i < a.length - 1; ++i) {
            int minPos = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j].compareTo(a[minPos]) < 0) {
                    minPos = j;
                }
            }
                T temp = a[minPos];
                a[minPos] = a[i];
                a[i] = temp;
        }
    }

Shell Sort

public static <T extends Comparable<? super T>>
    void shellSort(T[] a) {
        int gap = a.length / 2;
        while (gap >= 1) {
            if (gap % 2 == 0) ++gap;
            for (int i = gap; i < a.length; ++i) {
                int p = i;
                T temp = a[p];
         while (p >= gap && a[p-gap].compareTo(temp) > 0) {
                   a[p] = a[p-gap];
                    p -= gap;
                }
                a[p] = temp;
            }
            gap /= 2;
        }
    }

Insertion

public static <T extends Comparable<? super T>>
    void insertionSort(T[] a) {
        for (int i = 0; i < a.length - 1; ++i) {
            int p = i + 1;
            T temp = a[p];
            while (p > 0 && a[p-1].compareTo(temp) > 0) {
                a[p] = a[p-1];
                --p;
            }
            if (p > 0) // count the last a[p-1] comparison
            a[p] = temp;
        }
    }

Help Us Go Positive!

We offset our carbon usage with Ecologi. Click the link below to help us!

We offset our carbon footprint via Ecologi
 

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.