SUNY Geneseo Department of Computer Science

Stack Implementations, Tree Insertion

Previous Lecture

Misc

Learning center closes for Thanksgiving starting Tuesday

Questions?

Implementing Stacks

Stack class contains a List member variable

    class Stack

        private List items

        // push, pop, constructor,isEmpty
        // work by sending messages to items
        // and changing items

        Object pop ()
            Object temp = items.first()
            items = items.rest()
            return temp

• Adaptor Pattern

Stack is a subclass of List

    class Stack extends List

        // push, pop, etc. work by sending List
        // messages to "this"

        Object pop()
            Object temp = this.first()
            this = this.rest()
            return temp

Stack class contains an array as member variable

    class Stack

        private Object[] items

        // push,pop, etc. put things into or take
        // out of array

Inserting into a Binary Search Tree

    BinaryTree insert( x )
        if this.isEmpty()
            return new BinaryTree( x, new BinaryTree(), new BinaryTree() )
        else
            if x less than root
                this.setLeft( this.left().insert(x) )
                return this
            else //x >= root
                recursion on right subtree

Allowing duplicates requires simple change to searches

• Or you could disallow duplicates in insert

Next - Optimality

Recall the Towers of Hanoi puzzle

Algorithm to move n disks from pole "source" to pole "dest", via pole "spare"

    solve( n, source, dest, spare )
        if n > 0
            solve( n-1, source, spare, dest )
            move 1 disk from source to dest
            solve( n-1, spare, dest, source )

This runs in Theta(2ⁿ) time

• (Because it does 2ⁿ -1 moves of disks)
• ... which is intolerable

Can you find a faster algorithm? (Mini-assignment)

Next Lecture