I. Overview of Data Structures
   A. General issues
      1. Data structure + algorithms
         a. the relationship between data structures and algorithms is one of 
            information and transformation, similar to that between algebraic 
            structures and their operations, classes and their methods, nouns 
            and verbs, etc.
      2. Structures as collections
         a. the data structures we study will generally be collections of 
            components, akin to sets in set theory, but with extra structure 
            that reflects relationships between components and the intended use 
            of the collection as a whole
      3. Structural shape (linear, etc.)
         a. many of these structures have a natural ordering or shape imposed on 
            the collection; examples are linear (lists, stacks, queues),  
            hierarchical (various types of trees) or  tabular (hash tables and 
            dictionaries)
      4. Access to structures
         a. sometimes we purposely restrict access to the components of a structure, 
            in order to take advantage of more efficient representations or to 
            reflect a natural restriction in the problem domain
   B. Stacks
      1. General description of stacks
         a. linear structure
         b. limited access: last in, first out
      2. Operations on stacks
         a. boolean isEmpty()
         b. void makeEmpty()
         c. void push(Object)
         d. void pop()
         e. Object top()
         f. Object Topandpop()
      3. Weiss' Java interface for stacks
         a. the on-line interface for stacks used by the textbook can be found at:
         b. http://www.cs.fiu.edu/~weiss/dsj/code/DataStructures/Stack.java
      4. Applications I
         a. matching brackets (or other delimiting program constructs)
      5. Applications II
         a. stack implementations of recursive function calls
      6. Applications II
         a. evaluation of arithmetic expressions
   C. Queues
      1. General description of queues
         a. linear structure
         b. limited access: last in, first out
      2. Operations on queues
         a. boolean isEmpty( )
         b. void makeEmpty( )
         c. void  enqueue( Object X )
         d. Object dequeue( ) throws Underflow
         e. Object getFront( ) throws Underflow
      3. Weiss' Java interface for queues
         a. the on-line interface for queues used by the textbook can be found at:
         b. http://www.cs.fiu.edu/~weiss/dsj/code/DataStructures/Queue.java
   D. Linked lists
      1. General description of linked lists
         a. linear structure
         b. arbitrary access (via iterator)
      2. Linked lists versus arrays
      3. Iteration through lists
      4. List iterator interface (p. 153)
         a. void insert(Object x)
         b. boolean find (Object x)
         c. void remove (Object x)
         d. boolean isInList
         e. Object retrieve()
         f. void zeroth()
         g. void first()
         h. void advance()
      5. List iterator example (p. 154)
   E. General trees
      1. Definition of trees
         a. Nodes and edges with dist. root; all others have unique parent; 
            unique path from root to any other node
      2. Properties of trees
         a. nonlinear structure (hierarchical)
         b. arbitrary access (via iterator)
      3. Derived concepts and terminology
         a. leaf, grandparent, sibling, cousin, etc.
      4. Applications I
         a. file and directory structure
      5. Applications II
         a. expression trees
      6. Tree iterator interface (p. 156)
         a. void insert(Object x)
         b. boolean find(Object x)
         c. void remove(Object x)
         d. void gotoRoot()
         e. void firstChild()
         f. boolean isValid()
         g. Object retrieve()
      7. Tree traversals
   F. Extra notes/Errata
      1. Problem with queue interface
         a. in fact, does not access input end of queue (back) at all
      2. Tree iterator
         a. the "find" should probably not be in the interface at all (p. 156)
   G. Binary search trees
      1. Binary trees
         a. at most two children (and if one, often has sense of left or right)
      2. requires Comparable objects
   H. Hash tables
      1. Requires Hashable objects
      2. add a find method
         a. if not found, throws exception
   I. Priority queues
      1. (not yet filled in)
   J. Review of exceptions
      1. Basic syntax
         a. try
              { }
            catch (Exception e)
              { }
      2. The finally clause
         a. see page 43
      3. Explicit throwing
      4. Throws clause
         a. indicates that a method may throw an exception of a certain type